Coloring Artemis graphs

DOI10.1016/j.tcs.2009.02.012zbMath1165.05027OpenAlexW2056768472MaRDI QIDQ1019741

Nicolas Trotignon, Benjamin Lévêque, Frédéric Maffray, Bruce A. Reed

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.012

zbMATH Keywords

algorithmgraphperfect graphcoloringeven pair

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Coloring square-free Berge graphs, Graph transformations preserving the stability number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• Weakly triangulated graphs
• Perfectly contractile graphs
• The strong perfect graph theorem
• On the complexity of recognizing perfectly orderable graphs
• Precoloring extension of co-Meyniel graphs
• Even pairs in Berge graphs
• On the perfect graph conjecture
• Meyniel weakly triangulated graphs. II: A theorem of Dirac
• A class of perfectly contractile graphs
• Improved algorithms for weakly chordal graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• Robust algorithms for restricted domains
• Algorithms for Perfectly Contractile Graphs
• An \(O(n^2)\) algorithm to color Meyniel graphs