Artículo

Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K. "Clique-perfectness of complements of line graphs" (2011) Electronic Notes in Discrete Mathematics. 37(C):327-332
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. © 2011 Elsevier B.V.

Registro:

Documento: Artículo
Título:Clique-perfectness of complements of line graphs
Autor:Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K.
Filiación:CONICET, Argentina
Depto. de Computación, FCEN, Universidad de Buenos Aires, Argentina
Depto. de Matemática, FCEN, Universidad de Buenos Aires, Argentina
Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Chile
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina
ISIMA-CNRS, Université Clermont-Ferrand II (Blaise Pascal), France
Palabras clave:Clique-perfect graphs; Edge-coloring; Line graphs; Maximal matchings
Año:2011
Volumen:37
Número:C
Página de inicio:327
Página de fin:332
DOI: http://dx.doi.org/10.1016/j.endm.2011.05.056
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p327_Bonomo

Referencias:

  • Balachandran, V., Nagavamsi, P., Rangan, C.P., Clique transversal and clique independence on comparability graphs (1996) Inform. Process. Lett., 58, pp. 181-184
  • Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth (1992), Technical report RUU-CS-92-27, Utrecht University; Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs (2008) Discrete Appl. Math., 156, pp. 1058-1082
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs (2009) Discrete Math., 309, pp. 3485-3499
  • Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs (2009) Discrete Appl. Math., 157, pp. 3511-3518
  • Borie, R.B., Parker, R.G., Tovey, C.A., Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families (1992) Algorithmica, 7, pp. 555-581
  • Brandstädt, A., Chepoi, V.D., Dragan, F.F., Clique r-domination and clique r-packing problems on dually chordal graphs (1997) SIAM J. Discrete Math., 10, pp. 109-127
  • Cariolaro, D., Cariolaro, G., Colouring the petals of a graph (2003) Electron. J. Combin., 10. , #R6
  • Courcelle, B., Graph Structure and Monadic Second-Order Logic http://www.labri.fr/perso/courcell/Book/CourGGBook.pdf, book to be published by Cambridge University Press. URL ; Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs (1990) Inf. Comput., 85, pp. 12-75
  • Guruswami, V., Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl. Math., 100, pp. 183-202
  • Hilton, A.J.W., Zhao, C., The chromatic index of a graph whose core has maximum degree two (1992) Discrete Math., 101, pp. 135-147
  • Hoyler, I., The NP-completeness of Edge-Coloring (1981) SIAM J. Comput., 10, pp. 718-720
  • Lee, C.-M., Chang, M.-S., Distance-hereditary graphs are clique-perfect (2006) Discrete Appl. Math., 154, pp. 525-536
  • Lehot, P.G.H., An optimal algorithm to detect a line graph and output its root graph (1974) J. ACM, 21, pp. 569-575
  • Robertson, N., Seymour, P.D., Graph minors. I. Excluding a forest (1983) J. Comb. Theory Ser. B, 35, pp. 39-61
  • Vizing, V.G., On an estimate of the chromatic class of a p-graph (1964) Diskret. Analiz., 3, pp. 25-30

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Safe, M.D. & Wagler, A.K. (2011) . Clique-perfectness of complements of line graphs. Electronic Notes in Discrete Mathematics, 37(C), 327-332.
http://dx.doi.org/10.1016/j.endm.2011.05.056
---------- CHICAGO ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Clique-perfectness of complements of line graphs" . Electronic Notes in Discrete Mathematics 37, no. C (2011) : 327-332.
http://dx.doi.org/10.1016/j.endm.2011.05.056
---------- MLA ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Clique-perfectness of complements of line graphs" . Electronic Notes in Discrete Mathematics, vol. 37, no. C, 2011, pp. 327-332.
http://dx.doi.org/10.1016/j.endm.2011.05.056
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. Clique-perfectness of complements of line graphs. Electron. Notes Discrete Math. 2011;37(C):327-332.
http://dx.doi.org/10.1016/j.endm.2011.05.056