Coloring triangle-free graphs on surfaces

MaRDI QIDQ4633818zbMATH OpenFDO

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

Publication date 6 May 2019

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

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 graphs on surfaces. VII. A linear-time algorithm
• A class of three-colorable triangle-free graphs
• 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

Cited in

(28)

• Three-coloring graphs embedded on surfaces with all faces even-sided
• 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
• Building a maximal independent set for the vertex-coloring problem on planar graphs
• A heuristic for the coloring of planar graphs
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• 3-list-coloring graphs of girth at least five on surfaces
• Coloring near-quadrangulations of the cylinder and the torus
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Characterization of 4-critical triangle-free toroidal graphs
• Economic 3-colored subdivision of triangulations
• Coloring of Triangle-Free Graphs on the Double Torus
• The disjoint paths problem in quadratic time
• Hyperbolic families and coloring graphs on surfaces
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• scientific article; zbMATH DE number 7145382 (Why is no real title available?)
• scientific article; zbMATH DE number 6433827 (Why is no real title available?)
• Large independent sets in triangle-free planar graphs
• Coloring parameters for graphs on surfaces
• Coloring Triangle-Free Graphs on Surfaces
• Algorithms – ESA 2004
• Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations
• 5‐Coloring reconfiguration of planar graphs with no short odd cycles
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• Coloring vertices and faces of maps on surfaces
• Planar 4-critical graphs with four triangles

This page was built for publication: Coloring triangle-free graphs on surfaces

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