Fast 3-coloring triangle-free planar graphs

DOI10.1007/s00453-009-9295-2zbMath1200.05230OpenAlexW1989431443MaRDI QIDQ1957652

Łukasz Kowalik

Publication date: 27 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.5116

zbMATH Keywords

ColoringGraph algorithmsEfficient algorithmGrötzsch's theoremTriangle-free planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ Vertex-Coloring with Star-Defects ⋮ Backbone coloring of graphs with galaxy backbones ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• A sufficient condition for planar graphs to be 3-colorable
• A short list color proof of Grötzsch's theorem
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Oracles for bounded-length shortest paths in planar graphs
• A linear 5-coloring algorithm of planar graphs
• Coloring graphs with fixed genus and girth
• Coloring Triangle-Free Graphs on Surfaces
• Algorithms – ESA 2004