Uniquely Colourable Graphs with Large Girth

Abstract

Tutte [ 1 ], writing under a pseudonym, was the first to prove that a graph with a large chromatic number need not contain a triangle. The result was rediscovered by Zykov [ 5 ] and Mycielski [ 4 ]. Erdös [ 2 ] proved the much stronger result that for every k ≧ 2 and g there exist a k -chromatic graph whose girth is at least g.