Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm

DOI10.1016/J.JCTB.2021.07.002MaRDI QIDQ2664564zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Daniel Král', Robin Thomas

Publication date 17 November 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

coloringsurfacestriangle-free

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices.

Review text

This paper deals with 3-colorability of triangle-free graphs embedded in a fixed surface. More precisely, it is the last work of a series from the same authors on this topic. In this paper, the authors provide a linear-time algorithm to decide 3-colorability; in case of a positive answer, a quadratic-time algorithm can be used to output a 3-coloring. Such algorithms also allow to set the coloring of a bounded number of vertices in the given graph. \par For Part VI see [the authors, ``Three-coloring triangle-free graphs on surfaces. VI. 3-colorability of quadrangulations, Preprint, \url{arXiv:1509.01013}].

Recommendations

• Coloring triangle-free graphs on surfaces
• Three-coloring triangle-free planar graphs in linear time
• Three-coloring triangle-free planar graphs in linear time
• Fast 3-coloring triangle-free planar graphs
• Algorithms – ESA 2004

Cites work

• 4-chromatic projective graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• A separator theorem for graphs of bounded genus
• Fine structure of 4-critical triangle-free graphs. III: General surfaces
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The chromatic number of a graph of girth 5 on a fixed surface
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Three-coloring triangle-free planar graphs in linear time

Cited in

(24)

• 3-colouring AT-free graphs in polynomial time
• Fast 3-coloring triangle-free planar graphs
• 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
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Characterization of 4-critical triangle-free toroidal graphs
• 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?)
• Coloring triangle-free graphs on surfaces
• Three-coloring triangle-free planar graphs in linear time
• Triangulating Three-Colored Graphs in Linear Time and Linear Space
• A simple linear time algorithm for triangulating three-colored graphs
• scientific article; zbMATH DE number 7145382 (Why is no real title available?)
• Large independent sets in triangle-free planar graphs
• Coloring Triangle-Free Graphs on Surfaces
• Algorithms – ESA 2004
• Flexibility of triangle‐free planar graphs
• Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations
• Precoloring extension in planar near-Eulerian-triangulations
• Precoloring extension in planar near-Eulerian-triangulations
• Precoloring extension in planar near-Eulerian-triangulations (extended abstract)

This page was built for publication: Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm

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