Coloring Triangle-Free Graphs on Surfaces

DOI10.1007/978-3-540-77120-3_2MaRDI QIDQ5387740zbMATH OpenOpenAlexFDO

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

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_2

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Coloring triangle-free graphs on surfaces
• Colouring graphs on surfaces
• Colouring graphs on surfaces
• scientific article; zbMATH DE number 7145382
• Coloring parameters for graphs on surfaces
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• On acyclic colorings of graphs on surfaces
• Triad colorings of triangulations on closed surfaces
• Colouring vertices of triangle-free graphs
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• Color-critical graphs on a fixed surface
• Coloring graphs with fixed genus and girth
• Graph theory with applications
• Graphs on surfaces
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The chromatic number of a graph of girth 5 on a fixed surface
• The non-existence of colorings

Cited in

(11)

• Coloring parameters for graphs on surfaces
• Coloring vertices and faces of maps on surfaces
• Three-coloring graphs embedded on surfaces with all faces even-sided
• A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
• 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
• Fast 3-coloring triangle-free planar graphs
• scientific article; zbMATH DE number 6433827 (Why is no real title available?)
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
• Coloring of Triangle-Free Graphs on the Double Torus
• scientific article; zbMATH DE number 7145382 (Why is no real title available?)

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 Q5387740)