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

girth; clique number; triangle-free graph; orientable surface; double torus; triangle-free projective graphs; chormatic number

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

Related Items

Color-critical graphs on a fixed surface

Cites Work

• 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
• A 4-Color Theorem for Toroidal Graphs
• Sur le coloriage des graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item