Coloring graphs with fixed genus and girth

DOI10.1090/S0002-9947-97-01926-0zbMath0884.05039MaRDI QIDQ4372592

Carsten Thomassen, John G. Gimbel

Publication date: 16 December 1997

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

girthclique numbertriangle-free graphorientable surfacedouble torustriangle-free projective graphschormatic number

Mathematics Subject Classification ID

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

Related Items (50)

On the dichromatic number of surfaces ⋮ Further extensions of the Grötzsch theorem ⋮ Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces ⋮ Three-coloring Klein bottle graphs of girth five ⋮ Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. ⋮ Triangle-free planar graphs with small independence number ⋮ Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains ⋮ Unnamed Item ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Color-critical graphs on a fixed surface ⋮ On the location of roots of independence polynomials ⋮ Many 3-colorings of triangle-free planar graphs ⋮ Partitions of graphs into cographs ⋮ Characterization of 4-critical triangle-free toroidal graphs ⋮ 3-coloring triangle-free planar graphs with a precolored 9-cycle ⋮ Coloring Eulerian triangulations of the Klein bottle ⋮ 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle ⋮ Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles ⋮ A step towards the strong version of Havel's three color conjecture ⋮ A density bound for triangle‐free 4‐critical graphs ⋮ The chromatic number of a graph of girth 5 on a fixed surface ⋮ Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces ⋮ Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations ⋮ Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five ⋮ Schrijver Graphs and Projective Quadrangulations ⋮ Subcolorings and the subchromatic number of a graph ⋮ From the plane to higher surfaces ⋮ Fast 3-coloring triangle-free planar graphs ⋮ On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges ⋮ Coloring Triangle-Free Graphs on Surfaces ⋮ Coloring near-quadrangulations of the cylinder and the torus ⋮ Coloring even-faced graphs in the torus and the Klein bottle ⋮ Chromatic numbers of quadrangulations on closed surfaces ⋮ Online coloring graphs with high girth and high odd girth ⋮ What is on his mind? ⋮ Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable ⋮ Irreducible 4-critical triangle-free toroidal graphs ⋮ Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk ⋮ 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 ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Coloring-flow duality of embedded graphs ⋮ Planar 4-critical graphs with four triangles ⋮ Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable ⋮ Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quadrangulations and 4-color-critical graphs ⋮ Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor ⋮ Fractional cocoloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on Ramsey numbers
• A dense infinite Sidon sequence
• Unsolved problems in geometry
• Chromatic number and girth
• Some simplified NP-complete graph problems
• Coloring graphs without short non-bounding cycles
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Color-critical graphs on a fixed surface
• Graph Theory and Probability
• Graph Theory and Probability. II
• Some extremal results in cochromatic and dichromatic theory
• Cochromatic Number and the Genus of a Graph
• Note on the cochromatic number of several surfaces
• The Ramsey number R(3, t) has order of magnitude t²/log t
• 4-chromatic projective graphs
• A 4-Color Theorem for Toroidal Graphs
• Sur le coloriage des graphs

This page was built for publication: Coloring graphs with fixed genus and girth