Clique-perfectness of complements of line graphs

Mostrar todas las versiones(4)

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, F., Durán, G., Safe, M.D., Wagler, A.K.
Formato:	JOUR
Materias:	Clique-perfect graphs Edge-coloring Line graphs Maximal matchings
Acceso en línea:	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	todo:paper_15710653_v37_nC_p327_Bonomo
record_format	dspace
spelling	todo:paper_15710653_v37_nC_p327_Bonomo2023-10-03T16:27:06Z Clique-perfectness of complements of line graphs Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, F. Durán, G. Safe, M.D. Wagler, A.K. 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.
format	JOUR
author	Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K.
author_facet	Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K.
author_sort	Bonomo, F.
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
url	http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p327_Bonomo
work_keys_str_mv	AT bonomof cliqueperfectnessofcomplementsoflinegraphs AT durang cliqueperfectnessofcomplementsoflinegraphs AT safemd cliqueperfectnessofcomplementsoflinegraphs AT waglerak cliqueperfectnessofcomplementsoflinegraphs
_version_	1807315959893983232

Clique-perfectness of complements of line graphs

Ejemplares similares