Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations

DOI10.1016/J.JCTB.2023.11.001MaRDI QIDQ6184892zbMATH OpenOpenAlexFDO

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

Publication date 29 January 2024

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

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

zbMATH Keywords

coloringquadrangulationssurfaces

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: We give a linear-time algorithm to decide 3-colorability (and find a 3-coloring, if it exists) of quadrangulations of a fixed surface. The algorithm also allows to prescribe the coloring for a bounded number of vertices.

Recommendations

• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Coloring triangle-free graphs on surfaces
• Three-coloring triangle-free planar graphs in linear time
• Three-coloring triangle-free planar graphs in linear time
• Coloring near-quadrangulations of the cylinder and the torus

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• A guide to the classification theorem for compact surfaces
• Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces
• Coloring graphs with fixed genus and girth
• Coloring locally bipartite graphs on surfaces.
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Graph minors. VII: Disjoint paths on a surface
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Testing first-order properties for subclasses of sparse graphs
• Three-coloring graphs embedded on surfaces with all faces even-sided
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm

Cited in

(2)

• Precoloring extension in planar near-Eulerian-triangulations
• Precoloring extension in planar near-Eulerian-triangulations

This page was built for publication: Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations

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