Coloring Triangle-Free Graphs on Surfaces

DOI10.1007/978-3-540-77120-3_2zbMath1193.05075OpenAlexW1529115029MaRDI QIDQ5387740

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

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

Related Items

Fast 3-coloring triangle-free planar graphs ⋮ A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The non-existence of colorings
• Color-critical graphs on a fixed surface
• The chromatic number of a graph of girth 5 on a fixed surface
• Coloring graphs with fixed genus and girth
• Subgraph Isomorphism in Planar Graphs and Related Problems