Three-coloring triangle-free planar graphs in linear time

DOI10.1145/2000807.2000809zbMath1295.05231arXiv1302.5121OpenAlexW2127059580MaRDI QIDQ3189025

Robin Thomas, Ken-ichi Kawarabayashi, Zdeněk Dvořák

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.5121

zbMATH Keywords

graph coloringplanar graphstriangle-free graphs

Mathematics Subject Classification ID

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

Related Items (13)

Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. ⋮ Do triangle-free planar graphs have exponentially many 3-colorings? ⋮ Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm ⋮ Fractional coloring of triangle-free planar graphs ⋮ Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$ ⋮ 5-list coloring toroidal 6-regular triangulations in linear time ⋮ Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five ⋮ Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk ⋮ Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies ⋮ Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ On rectangle intersection graphs with stab number at most two ⋮ Some of My Favorite Coloring Problems for Graphs and Digraphs

This page was built for publication: Three-coloring triangle-free planar graphs in linear time