Coloring Meyniel graphs in linear time

2005/10/01 by Benjamin Lévêque, Frédéric Maffray · 1 citation
Computer Science · Decision Sciences · #Advanced Graph Theory Research #Computer science #Graph Labeling and Dimension Problems #Scheduling and Timetabling Solutions

paper · doi:10.1016/j.endm.2005.06.005

published in Electronic Notes in Discrete Mathematics 22, 25-28 (Elsevier BV)

crossref issued 2005/10/01 · crossref published 2005/10/01 · crossref published-print 2005/10/01 · openalex publication_date 2005/10/01 · crossref created 2005/10/19 · crossref deposited 2019/01/21 · crossref indexed 2024/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

• Polynomial Algorithm to Recognize a Meyniel Graph
• On a conjecture of Meyniel
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A fast algorithm for coloring Meyniel graphs
• An O(n2) algorithm to color Meyniel graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• New methods to color the vertices of a graph

Cited by

• Greedy coloring [wikipedia]