Partial characterizations of coordinated graphs: Line graphs and complements of forests

DOI10.1007/s00186-008-0257-2zbMath1161.05321OpenAlexW2145081731MaRDI QIDQ1014303

Guillermo Durán, Francisco J. Soulignac, Gabriel Sueiro, Flavia Bonomo-Braberman

Publication date: 27 April 2009

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00186-008-0257-2

zbMATH Keywords

perfect graphsline graphscoordinated graphscomplements of forests

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items (4)

NP-hardness of the recognition of coordinated graphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-hardness of the recognition of coordinated graphs
• The strong perfect graph theorem
• Kernels in perfect line-graphs
• Algorithmic graph theory and perfect graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Recognizing Berge graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Line perfect graphs
• On line perfect graphs

This page was built for publication: Partial characterizations of coordinated graphs: Line graphs and complements of forests