Back to Search Start Over

Structure in sparse k-critical graphs.

Authors :
Gould, Ronald J.
Larsen, Victor
Postle, Luke
Source :
Journal of Combinatorial Theory - Series B. Sep2022, Vol. 156, p194-222. 29p.
Publication Year :
2022

Abstract

Recently, Kostochka and Yancey [7] proved that a conjecture of Ore is asymptotically true by showing that every k -critical graph satisfies | E (G) | ≥ ⌈ (k 2 − 1 k − 1) | V (G) | − k (k − 3) 2 (k − 1) ⌉. They also characterized [8] the class of graphs that attain this bound and showed that it is equivalent to the set of k -Ore graphs. We show that for any k ≥ 33 there exists an ε > 0 so that if G is a k -critical graph, then | E (G) | ≥ (k 2 − 1 k − 1 + ε) | V (G) | − k (k − 3) 2 (k − 1) − (k − 1) ε T (G) , where T (G) is a measure of the number of disjoint K k − 1 and K k − 2 subgraphs in G. This also proves for k ≥ 33 the following conjecture of Postle [12] regarding the asymptotic density: For every k ≥ 4 there exists an ε k > 0 such that if G is a k -critical K k − 2 -free graph, then | E (G) | ≥ (k 2 − 1 k − 1 + ε k) | V (G) | − k (k − 3) 2 (k − 1). As a corollary, our result shows that the number of disjoint K k − 2 subgraphs in a k -Ore graph scales linearly with the number of vertices and, further, that the same is true for graphs whose number of edges is close to Kostochka and Yancey's bound. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00958956
Volume :
156
Database :
Academic Search Index
Journal :
Journal of Combinatorial Theory - Series B
Publication Type :
Academic Journal
Accession number :
157302591
Full Text :
https://doi.org/10.1016/j.jctb.2022.04.004