Premium
Almost all graphs with high girth and suitable density have high chromatic number
Author(s) -
Osthus Deryk,
Prömel Hans Jürgen,
Taraz Anusch
Publication year - 2001
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.1017
Subject(s) - mathematics , combinatorics , girth (graph theory) , odd graph , chromatic scale , brooks' theorem , discrete mathematics , graph , triangle free graph , chordal graph , 1 planar graph
Erdös proved that there exist graphs of arbitrarily high girth and arbitrarily high chromatic number. We give a different proof (but also using the probabilistic method) that also yields the following result on the typical asymptotic structure of graphs of high girth: for all ℓ ≥ 3 and k ∈ ℕ there exist constants C 1 and C 2 so that almost all graphs on n vertices and m edges whose girth is greater than ℓ have chromatic number at least k , provided that $C_{1}n\,\leq\, m\,\leq\, C_{2}n^{\ell /(\ell -1)}$ . © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 220–226, 2001