Note on robust critical graphs with large odd girth

作者：Nastase E^*; Rodl V; Siggers M

来源：Discrete Mathematics, 2010, 310(3): 499-504.

DOI：10.1016/j.disc.2009.03.030

• Graph
• Colour critical
• Odd girth

A graph G is (k + 1)-critical if it is not k-colourable but G - e is k-colourable for any edge e is an element of E(G). In this paper we show that for any integers k >= 3 and l >= 5 there exists a constant c = c(k, 1) > 0, such that for all (n) over tilde, there exists a (k + 1)-critical graph G on n vertices with n > (n) over tilde and odd girth at least l, which can be made (k - 1)-colourable only by the omission of at least cn(2) edges.

• 出版日期2010-2-6