Uniquely Colourable Graphs with Large Girth
Béla Bollobás, Norbert W. Sauer · Canadian Journal of Mathematics · 1976
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.