Three-coloring triangle-free planar graphs in linear time

MaRDI QIDQ4633932zbMATH OpenFDO

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

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496897

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) Analysis of algorithms (68W40)

Recommendations

• Three-coloring triangle-free planar graphs in linear time
• Fast 3-coloring triangle-free planar graphs
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Algorithms – ESA 2004
• A simple algorithm for 4-coloring 3-colorable planar graphs

Cited in

(24)

• Fast 3-coloring triangle-free planar graphs
• A linear-time algorithm for clique-coloring planar graphs
• Do triangle-free planar graphs have exponentially many 3-colorings?
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Triangle-free planar graphs with at most \(64^{n^{0.731}}\) 3-colorings
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Three-coloring triangle-free planar graphs in linear time
• scientific article; zbMATH DE number 1953089 (Why is no real title available?)
• scientific article; zbMATH DE number 1982186 (Why is no real title available?)
• Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count
• Coloring triangle-free graphs on surfaces
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• Finding disjoint paths in split graphs
• Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
• An introduction to the discharging method via graph coloring
• A simple linear time algorithm for triangulating three-colored graphs
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
• Algorithms – ESA 2004
• Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations
• Simpler multicoloring of triangle-free hexagonal graphs
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• Many 3-colorings of triangle-free planar graphs

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

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