Record number :
Title of article :
Clique-perfectness of complements of line graphs
Author/Authors :
Bonomo، نويسنده , , Flavia and Durلn، نويسنده , , Guillermo and Safe، نويسنده , , Martيn D. and Wagler، نويسنده , , Annegret K.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
From page :
To page :
Abstract :
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.
Keywords :
Clique-perfect graphs , Edge-coloring , Line graphs , maximal matchings
Journal title :
Electronic Notes in Discrete Mathematics
Link To Document :