Abstract
A graph G is (k + 1)-critical if it is not k-colourable but G - e is k-colourable for any edge e ∈ E (G). In this paper we show that for any integers k ≥ 3 and l ≥ 5 there exists a constant c = c (k, l) > 0, such that for all over(n, ̃), there exists a (k + 1)-critical graph G on n vertices with n > over(n, ̃) and odd girth at least ℓ, which can be made (k - 1)-colourable only by the omission of at least c n2 edges.
Original language | English |
---|---|
Pages (from-to) | 499-504 |
Number of pages | 6 |
Journal | Discrete Mathematics |
Volume | 310 |
Issue number | 3 |
DOIs | |
State | Published - 6 Feb 2010 |
Keywords
- Colour critical
- Graph
- Odd girth