Coloring Meyniel graphs in linear time

DOI10.1016/J.ENDM.2005.06.005MaRDI QIDQ3439304zbMATH OpenOpenAlexFDO

Authors Benjamin Lévêque, Frédéric Maffray

Publication date 29 May 2007

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

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

zbMATH Keywords

algorithmcoloringMeyniel graphsperfect graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An O(n^2) algorithm to color Meyniel graphs
• scientific article; zbMATH DE number 52166
• A fast algorithm for coloring Meyniel graphs
• scientific article; zbMATH DE number 3889583
• Holes and dominoes in Meyniel graphs

Cites work

• A fast algorithm for coloring Meyniel graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An O(n^2) algorithm to color Meyniel graphs
• Connected sequential colourings
• Even pairs
• Holes and dominoes in Meyniel graphs
• scientific article; zbMATH DE number 3878985 (Why is no real title available?)
• scientific article; zbMATH DE number 3904622 (Why is no real title available?)
• scientific article; zbMATH DE number 3556145 (Why is no real title available?)
• New methods to color the vertices of a graph
• On a conjecture of Meyniel
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

Cited in

(9)

• Coloring Artemis graphs
• On a conjecture of Meyniel
• A fast algorithm for coloring Meyniel graphs
• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 3878985 (Why is no real title available?)
• Coloring vertices of a graph or finding a Meyniel obstruction
• Holes and dominoes in Meyniel graphs
• An O(n^2) algorithm to color Meyniel graphs
• Erratum : MCColor is not optimal on Meyniel graphs

This page was built for publication: Coloring Meyniel graphs in linear time

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