Back to Search
Start Over
Structure in sparse k-critical graphs.
- 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