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:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Pizaña, Miguel, Ravenna, Gabriela Susana
Formato: Articulo
Lenguaje:Inglés
Publicado: 2017
Materias:
Matemática
Helly property
Clique-Helly graphs
Clique graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/102977
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-102977
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Helly property
Clique-Helly graphs
Clique graphs
spellingShingle Matemática
Helly property
Clique-Helly graphs
Clique graphs
Alcón, Liliana Graciela
Pizaña, Miguel
Ravenna, Gabriela Susana
On the Existence of Critical Clique-Helly Graphs
topic_facet Matemática
Helly property
Clique-Helly graphs
Clique graphs
description 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.
format Articulo
Articulo
author Alcón, Liliana Graciela
Pizaña, Miguel
Ravenna, Gabriela Susana
author_facet Alcón, Liliana Graciela
Pizaña, Miguel
Ravenna, Gabriela Susana
author_sort Alcón, Liliana Graciela
title On the Existence of Critical Clique-Helly Graphs
title_short On the Existence of Critical Clique-Helly Graphs
title_full On the Existence of Critical Clique-Helly Graphs
title_fullStr On the Existence of Critical Clique-Helly Graphs
title_full_unstemmed On the Existence of Critical Clique-Helly Graphs
title_sort on the existence of critical clique-helly graphs
publishDate 2017
url http://sedici.unlp.edu.ar/handle/10915/102977
work_keys_str_mv AT alconlilianagraciela ontheexistenceofcriticalcliquehellygraphs
AT pizanamiguel ontheexistenceofcriticalcliquehellygraphs
AT ravennagabrielasusana ontheexistenceofcriticalcliquehellygraphs
bdutipo_str Repositorios
_version_ 1764820440915640321

Ejemplares similares