Note on robust critical graphs with large odd girth

E. Nǎstase, V. Rödl, M. Siggers

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 languageEnglish
Pages (from-to)499-504
Number of pages6
JournalDiscrete Mathematics
Volume310
Issue number3
DOIs
StatePublished - 6 Feb 2010

Keywords

  • Colour critical
  • Graph
  • Odd girth

Fingerprint

Dive into the research topics of 'Note on robust critical graphs with large odd girth'. Together they form a unique fingerprint.

Cite this