A simple algorithm for 4-coloring 3-colorable planar graphs

DOI10.1016/j.tcs.2010.02.015zbMath1209.05088OpenAlexW2109639734MaRDI QIDQ974757

Kenta Ozeki, Ken-ichi Kawarabayashi

Publication date: 7 June 2010

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

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

zbMATH Keywords

3-colorable graphthe four color theorem

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

A heuristic for the coloring of planar graphs ⋮ Additive non-approximability of chromatic number in proper minor-closed classes

Cites Work

• Unnamed Item
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Zero knowledge and the chromatic number
• The four-colour theorem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Conditional hardness for approximate coloring
• Improving the performance guarantee for approximate graph coloring
• Approximate graph coloring by semidefinite programming
• Efficient Planarity Testing
• New approximation algorithms for graph coloring
• Subgraph Isomorphism in Planar Graphs and Related Problems