Clique-perfectness of complements of line graphs

DOI10.1016/j.endm.2011.05.056zbMath1268.05145OpenAlexW2048932473MaRDI QIDQ5891101

Martín D. Safe, Guillermo Durán, Annegret K. Wagler, Flavia Bonomo-Braberman

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2011.05.056

zbMATH Keywords

edge-coloringline graphsminimal forbidden induced subgraphsmaximal matchingsclique-transversal numberclique-perfect graphsclique-independence number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Clique-perfectness and balancedness of some graph classes ⋮ Clique-perfectness of complements of line graphs

Cites Work

• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
• Graph minors. I. Excluding a forest
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The chromatic index of a graph whose core has maximum degree two
• Colouring the petals of a graph
• Algorithmic aspects of clique-transversal and clique-independent sets
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Distance-hereditary graphs are clique-perfect
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• The NP-Completeness of Edge-Coloring
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

This page was built for publication: Clique-perfectness of complements of line graphs