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

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