Note on robust critical graphs with large odd girth |
| |
Authors: | E N?stase V Rödl |
| |
Institution: | a Xavier University, Cincinnati, OH, USA b Emory University, Atlanta, GA, USA c Kyungpook National University, Taegu, Republic of Korea |
| |
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 , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn2 edges. |
| |
Keywords: | Graph Colour critical Odd girth |
本文献已被 ScienceDirect 等数据库收录! |
|