| We give a new proof of the classical Erdos theorem on the existence of graphs with arbitrarily high chromatic number and girth. Rather than considering random graphs where the edges are chosen with some carefully adjusted probability, we use a simple counting argument on a set of graphs with bounded degree. |
Keywords
girth, chromatic number
Math Review Classification
Primary 05C99
Last Updated
22/12/2004
Length
4 pages
Availability
This article is available in: