Three-coloring triangle-free planar graphs in linear time

zbMATH Open1423.05064MaRDI QIDQ4633932FDOQ4633932

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

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

Mathematics Subject Classification ID

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

Cited In (23)

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

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)