Clique-perfectness of complements of line graphs

DOI10.1016/J.ENDM.2011.05.056MaRDI QIDQ5891101zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Clique-perfectness of complements of line graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Clique-perfectness of claw-free planar graphs
• On clique-transversals and clique-independent sets
• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs

Cites work

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

Cited in

(7)

• On clique-perfect and K-perfect graphs
• scientific article; zbMATH DE number 1539532 (Why is no real title available?)
• Characterization and recognition of Helly circular-arc clique-perfect graphs
• Clique-perfectness of complements of line graphs
• The clique structure of a graph
• Clique-perfectness and balancedness of some graph classes
• On clique-transversals and clique-independent sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891101)