Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T06:53:40.952Z Has data issue: false hasContentIssue false

Uniquely Colourable Graphs with Large Girth

Published online by Cambridge University Press:  20 November 2018

Béla Bollobás
Affiliation:
University of Cambridge, Cambridge, England
Norbert Sauer
Affiliation:
University of Calgary, Calgary, Alberta
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1976