Coloring graphs with fixed genus and girth

DOI10.1090/S0002-9947-97-01926-0MaRDI QIDQ4372592zbMATH OpenFDO

Authors Carsten Thomassen, John Gimbel

Publication date 16 December 1997

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

zbMATH Keywords

clique numbergirthtriangle-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)

Recommendations

• Coloring triangle-free graphs with fixed size
• Coloring of Triangle-Free Graphs on the Double Torus
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• The chromatic number of a graph of girth 5 on a fixed surface

Cites work

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

Cited in

(56)

• Hyperbolic families and coloring graphs on surfaces
• Subcolorings and the subchromatic number of a graph
• Further extensions of the Grötzsch theorem
• Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces
• Coloring near-quadrangulations of the cylinder and the torus
• Fractional colorings of partial t-trees with no large clique
• On the location of roots of independence polynomials
• Coloring Triangle-Free Graphs on Surfaces
• Fractional cocoloring of graphs
• Online coloring graphs with high girth and high odd girth
• scientific article; zbMATH DE number 2230325 (Why is no real title available?)
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• From the plane to higher surfaces
• Color-critical graphs on a fixed surface
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• Quadrangulations and 4-color-critical graphs
• Coloring-flow duality of embedded graphs
• Fine structure of 4-critical triangle-free graphs. II: Planar triangle-free graphs with two precolored 4-cycles
• Fractional coloring methods with applications to degenerate graphs and graphs on surfaces
• A 4-Color Theorem for Surfaces of Genus g
• Chromatic numbers of simplicial manifolds
• Planar 4-critical graphs with four triangles
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• Coloring of locally planar graphs with one color class small
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations
• Fine structure of 4-critical triangle-free graphs. III: General surfaces
• The choice number versus the chromatic number for graphs embeddable on orientable surfaces
• The chromatic number of a graph of girth 5 on a fixed surface
• Coloring Eulerian triangulations of the Klein bottle
• Fast 3-coloring triangle-free planar graphs
• Realizing the chromatic numbers of triangulations of surfaces
• Characterization of 4-critical triangle-free toroidal graphs
• 3-coloring triangle-free planar graphs with a precolored 9-cycle
• A density bound for triangle‐free 4‐critical graphs
• Three-coloring Klein bottle graphs of girth five
• What is on his mind?
• scientific article; zbMATH DE number 2230307 (Why is no real title available?)
• Triangle-free planar graphs with small independence number
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• Many 3-colorings of triangle-free planar graphs
• On the dichromatic number of surfaces
• Large independent sets in triangle-free planar graphs
• A step towards the strong version of Havel's three color conjecture
• Partitions of graphs into cographs
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
• Chromatic numbers of quadrangulations on closed surfaces
• 7-critical graphs of bounded genus
• Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
• Schrijver graphs and projective quadrangulations
• Coloring even-faced graphs in the torus and the Klein bottle
• scientific article; zbMATH DE number 7145382 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4372592)