Clique-perfectness of complements of line graphs |
| |
| Institution: | 1. CONICET, Argentina;2. Depto. de Computación, FCEN, Universidad de Buenos Aires, Argentina;3. Depto. de Matemática, FCEN, Universidad de Buenos Aires, Argentina;4. Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Chile;5. Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina;6. ISIMA-CNRS, Université Clermont-Ferrand II (Blaise Pascal), France;1. UFPA, Rua Augusto Correa, No 01, Campus Universitário do Guamá, Belem, 66075110, Brazil;2. University of Florida, 553 Engeniring Bulding, Gainesville, 32611, United States;3. Moscow Institute of Electronics and Mathematics, National Research University Higher School of Economics, Moscow, Russia;1. Department of Industrial Engineering, University of Padova, Padova 35131, Italy;2. Advanced Power and Energy Center, ECE Department, KUST, Abu Dhabi, United Arab Emirates;3. Advanced High Voltage Engineering Research Centre, Cardiff University, Cardiff, UK |
| |
| 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: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
