Color-critical graphs have logarithmic circumference
From MaRDI portal
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 log n/(100log k), improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that the bound cannot be improved to exceed 2(k-1)log n/log(k-2). 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.
Recommendations
Cites work
- Circuits in critical graphs
- scientific article; zbMATH DE number 3685495 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 3195967 (Why is no real title available?)
- Long cycles in critical graphs
- Maximal Circuits in Critical Graphs
- On six problems posed by Jarik Nešetřil
- On the structure of 5- and 6-chromatic abstract graphs.
- Paths and Circuits in Critical Graphs
- Relative lengths of paths and cycles in 3-connected graphs
- Some Theorems on Abstract Graphs
Cited in
(5)- Long cycles in graphs with no subgraphs of minimal degree 3
- Counting critical subgraphs in \(k\)-critical graphs
- scientific article; zbMATH DE number 1186107 (Why is no real title available?)
- Subdivisions in dicritical digraphs with large order or digirth
- An analogue of Dirac's theorem on circular super-critical graphs
This page was built for publication: Color-critical graphs have logarithmic circumference
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q550393)
