On the Existence of Critical Clique-Helly Graphs
A graph is clique-Helly if any family of mutually intersecting cliques has non-empty intersection. Dourado, Protti and Szwarcfiter conjectured that every clique-Helly graph contains a vertex whose removal maintains it a clique-Helly graph. We will present a counterexample to this conjecture.
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/102977 |
| Aporte de: |
| Sumario: | A graph is clique-Helly if any family of mutually intersecting cliques has non-empty intersection. Dourado, Protti and Szwarcfiter conjectured that every clique-Helly graph contains a vertex whose removal maintains it a clique-Helly graph. We will present a counterexample to this conjecture. |
|---|