On split clique graphs

A complete set of a graph G is a subset of VG whose elements are pairwise adjacent. A clique is a maximal complete set. The clique graph of G, denoted by K(G), is the intersection graph of the family of cliques of G. The clique graph recognition problem asks whether a given graph is a clique graph....

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Faria, Luerbio, Miraglia Herrera De Figueiredo, Celina, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2010
Materias:
Ciencias Exactas
Matemática
clique graphs
split graphs
recognition problems
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/162604
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-162604
record_format dspace
spelling I19-R120-10915-1626042024-02-15T04:07:11Z http://sedici.unlp.edu.ar/handle/10915/162604 On split clique graphs Alcón, Liliana Graciela Faria, Luerbio Miraglia Herrera De Figueiredo, Celina Gutiérrez, Marisa 2010 2024-02-14T12:47:24Z en Ciencias Exactas Matemática clique graphs split graphs recognition problems A complete set of a graph G is a subset of VG whose elements are pairwise adjacent. A clique is a maximal complete set. The clique graph of G, denoted by K(G), is the intersection graph of the family of cliques of G. The clique graph recognition problem asks whether a given graph is a clique graph. This problem was classified recently as NP-complete after being open for 30 years. The complexity of this decision problem is open for very structured and well studied classes of graphs such as planar graphs and chordal graphs. We propose the study of split clique graphs. Facultad de Ciencias Exactas Departamento de Matemática Articulo Articulo http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 85-91
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Matemática
clique graphs
split graphs
recognition problems
spellingShingle Ciencias Exactas
Matemática
clique graphs
split graphs
recognition problems
Alcón, Liliana Graciela
Faria, Luerbio
Miraglia Herrera De Figueiredo, Celina
Gutiérrez, Marisa
On split clique graphs
topic_facet Ciencias Exactas
Matemática
clique graphs
split graphs
recognition problems
description A complete set of a graph G is a subset of VG whose elements are pairwise adjacent. A clique is a maximal complete set. The clique graph of G, denoted by K(G), is the intersection graph of the family of cliques of G. The clique graph recognition problem asks whether a given graph is a clique graph. This problem was classified recently as NP-complete after being open for 30 years. The complexity of this decision problem is open for very structured and well studied classes of graphs such as planar graphs and chordal graphs. We propose the study of split clique graphs.
format Articulo
Articulo
author Alcón, Liliana Graciela
Faria, Luerbio
Miraglia Herrera De Figueiredo, Celina
Gutiérrez, Marisa
author_facet Alcón, Liliana Graciela
Faria, Luerbio
Miraglia Herrera De Figueiredo, Celina
Gutiérrez, Marisa
author_sort Alcón, Liliana Graciela
title On split clique graphs
title_short On split clique graphs
title_full On split clique graphs
title_fullStr On split clique graphs
title_full_unstemmed On split clique graphs
title_sort on split clique graphs
publishDate 2010
url http://sedici.unlp.edu.ar/handle/10915/162604
work_keys_str_mv AT alconlilianagraciela onsplitcliquegraphs
AT farialuerbio onsplitcliquegraphs
AT miragliaherreradefigueiredocelina onsplitcliquegraphs
AT gutierrezmarisa onsplitcliquegraphs
_version_ 1807222411708334080

Ejemplares similares