On the Existence of Critical Clique-Helly Graphs

Alcón, Liliana Graciela; Pizaña, Miguel; Ravenna, Gabriela Susana

info:eu-repo/semantics/publishedVersion

Fecha

2017

Registro en:

On the Existence of Critical Clique-Helly Graphs; LAGOS'17 – IX Latin and American Algorithms, Graphs and Optimization Symposium; Marsella; Francia; 2017; 231-236

1571-0653

http://hdl.handle.net/11336/140936

CONICET Digital

CONICET

https://repositorioslatinoamericanos.uchile.cl/handle/2250/4371465

Autor

Alcón, Liliana Graciela

Pizaña, Miguel

Ravenna, Gabriela Susana

Institución

Consejo Nacional de Investigaciones Científicas y Tecnológicas (Argentina)

Resumen

A graph is clique-Helly if any family of pairwise intersecting (maximal) cliques has non-empty total intersection. Dourado, Protti and Szwarcfiter conjectured that every clique-Helly graph contains a vertex whose removal maintains it as a clique-Helly graph. We present here an infinite family of counterexamples to this conjecture

Materias

Helly property

clique-Helly graphs

clique graphs

Mostrar el registro completo del ítem