Clique-perfectness of complements of line graphs

The clique-transversal number τc(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number αc(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subg...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Durán, Guillermo A., Safe, Martín Darío
Publicado: 2011
Materias:
Clique-perfect graphs
Edge-coloring
Line graphs
Maximal matchings
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p327_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p327_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v37_nC_p327_Bonomo
record_format dspace
spelling paper:paper_15710653_v37_nC_p327_Bonomo2023-06-08T16:24:27Z Clique-perfectness of complements of line graphs Bonomo, Flavia Durán, Guillermo A. Safe, Martín Darío Clique-perfect graphs Edge-coloring Line graphs Maximal matchings The clique-transversal number τc(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number αc(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation nor is a characterization by forbidden induced subgraphs known. Nevertheless, partial results in this direction have been obtained. For instance, in [Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discrete Appl. Math. 156 (2008), pp. 1058-1082], a characterization of those line graphs that are clique-perfect is given in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect, also by means of minimal forbidden induced subgraphs. This implies an O(n2) time algorithm for deciding the clique-perfectness of complements of line graphs and, for those that are clique-perfect, finding αc and τc. © 2011 Elsevier B.V. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p327_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p327_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Clique-perfect graphs
Edge-coloring
Line graphs
Maximal matchings
spellingShingle Clique-perfect graphs
Edge-coloring
Line graphs
Maximal matchings
Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
Clique-perfectness of complements of line graphs
topic_facet Clique-perfect graphs
Edge-coloring
Line graphs
Maximal matchings
description The clique-transversal number τc(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number αc(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation nor is a characterization by forbidden induced subgraphs known. Nevertheless, partial results in this direction have been obtained. For instance, in [Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discrete Appl. Math. 156 (2008), pp. 1058-1082], a characterization of those line graphs that are clique-perfect is given in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect, also by means of minimal forbidden induced subgraphs. This implies an O(n2) time algorithm for deciding the clique-perfectness of complements of line graphs and, for those that are clique-perfect, finding αc and τc. © 2011 Elsevier B.V.
author Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
author_facet Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
author_sort Bonomo, Flavia
title Clique-perfectness of complements of line graphs
title_short Clique-perfectness of complements of line graphs
title_full Clique-perfectness of complements of line graphs
title_fullStr Clique-perfectness of complements of line graphs
title_full_unstemmed Clique-perfectness of complements of line graphs
title_sort clique-perfectness of complements of line graphs
publishDate 2011
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p327_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p327_Bonomo
work_keys_str_mv AT bonomoflavia cliqueperfectnessofcomplementsoflinegraphs
AT duranguillermoa cliqueperfectnessofcomplementsoflinegraphs
AT safemartindario cliqueperfectnessofcomplementsoflinegraphs
_version_ 1768544520857714688

Ejemplares similares