Color-critical graphs have logarithmic circumference |
| |
Authors: | Asaf Shapira Robin Thomas |
| |
Institution: | aSchool of Mathematics and School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, United States;bSchool of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, United States |
| |
Abstract: | A graph G is k-critical if every proper subgraph of G is (k−1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least , improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that the bound cannot be improved to exceed . We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly in 1954. |
| |
Keywords: | Critical graphs Long cycles Connectivity |
本文献已被 ScienceDirect 等数据库收录! |
|