Record number :

1455722

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 :

6

From page :

327

To page :

332

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 :