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.