Coloring Artemis graphs

DOI10.1016/J.TCS.2009.02.012MaRDI QIDQ1019741zbMATH OpenOpenAlexFDO

Authors Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon, Bruce 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

graphalgorithmperfect graphcoloringeven pair

Mathematics Subject Classification ID

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

Recommendations

• A class of perfectly contractile graphs
• Algorithms for Perfectly Contractile Graphs
• On the complexity of colouring antiprismatic graphs
• Coloring Meyniel graphs in linear time
• Coloring graphs with no \(\text{odd-}K_4\)

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 3556145 (Why is no real title available?)
• scientific article; zbMATH DE number 1445284 (Why is no real title available?)
• A class of perfectly contractile graphs
• Algorithms for Perfectly Contractile Graphs
• An \(O(n^2)\) algorithm to color Meyniel graphs
• Even pairs
• Even pairs in Berge graphs
• Improved algorithms for weakly chordal graphs
• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• Meyniel weakly triangulated graphs. II: A theorem of Dirac
• On the complexity of recognizing perfectly orderable graphs
• On the perfect graph conjecture
• Perfectly contractile graphs
• Precoloring extension of co-Meyniel graphs
• Robust algorithms for restricted domains
• The strong perfect graph theorem
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• Weakly triangulated graphs

Cited in

(4)

• Coloring square-free Berge graphs
• On the complexity of colouring antiprismatic graphs
• Algorithms for Perfectly Contractile Graphs
• Graph transformations preserving the stability number

This page was built for publication: Coloring Artemis graphs

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