Five-coloring graphs on the torus

DOI10.1006/jctb.1994.1052zbMath0805.05022OpenAlexW1979621311MaRDI QIDQ1333321

Carsten Thomassen

Publication date: 13 September 1994

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

Full work available at URL: https://doi.org/10.1006/jctb.1994.1052

zbMATH Keywords

toruspolynomial time algorithm5-coloringgraph imbeddable on the torus

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45)

Related Items

The choice number versus the chromatic number for graphs embeddable on orientable surfaces ⋮ Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. ⋮ Six-Critical Graphs on the Klein Bottle ⋮ The number of \(k\)-colorings of a graph on a fixed surface ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Color-critical graphs on a fixed surface ⋮ On low tree-depth decompositions ⋮ 5-list coloring toroidal 6-regular triangulations in linear time ⋮ 4-colorable 6-regular toroidal graphs. ⋮ The color space of a graph ⋮ Some remarks on Hajós' conjecture ⋮ Five-coloring graphs on the Klein bottle ⋮ Grünbaum colorings of toroidal triangulations ⋮ Choosability of toroidal graphs without short cycles ⋮ Irreducible 4-critical triangle-free toroidal graphs ⋮ Families of dot-product snarks on orientable surfaces of low genus ⋮ Triangulations and the Hajós conjecture ⋮ You can't paint yourself into a corner ⋮ Finite dualities and map-critical graphs on a fixed surface ⋮ Extended Gallai's Theorem ⋮ A map colour theorem for the union of graphs

This page was built for publication: Five-coloring graphs on the torus