Counting critical subgraphs in k-critical graphs

DOI10.1007/S00493-020-4255-1MaRDI QIDQ2064752zbMATH OpenOpenAlexFDO

Authors Jie Ma, Tianchi Yang

Publication date 6 January 2022

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.09598

zbMATH Keywords

critical graphscritical subgraphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Abstract: Gallai asked in 1984 if any $k$-critical graph on $n$ vertices contains at least $n$ distinct $(k-1)$-critical subgraphs. The answer is trivial for $kleq3$. Improving a result of Stiebitz, Abbott and Zhou proved in 1995 that for all $kgeq4$, such graph contains $Omega(n^{1/(k-1)})$ distinct $(k-1)$-critical subgraphs. Since then no progress had been made until very recently, Hare resolved the case $k=4$ by showing that any $4$-critical graph on $n$ vertices contains at least $(8n-29)/3$ odd cycles. In this paper, we mainly focus on 4-critical graphs and develop some novel tools for counting cycles of specified parity. Our main result shows that any $4$-critical graph on $n$ vertices contains $Omega(n^2)$ odd cycles, which is tight up to a constant factor by infinite many graphs. As a crucial step, we prove the same bound for 3-connected non-bipartite graphs, which may be of independent interest. Using the tools, we also give a very short proof for the case $k=4$. Moreover, we improve the longstanding lower bound of Abbott and Zhou to $Omega(n^{1/(k-2)})$ for the general case $kgeq5$. We will also discuss some related problems on $k$-critical graphs in the final section.

Recommendations

• Tools for counting odd cycles in graphs
• On a conjecture of Gallai concerning complete subgraphs of \(k\)-critical graphs
• On the edge-density of 4-critical graphs
• Colour-critical graphs with few edges

Cites work

• Color-critical graphs have logarithmic circumference
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• On the structure of 5- and 6-chromatic abstract graphs.
• Ore's conjecture for k=4 and Grötzsch's theorem
• Removable cycles in non-bipartite graphs
• Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs
• Special subdivisions of \(K_4\) and 4-chromatic graphs
• Subgraphs of colour-critical graphs
• The structure of k-chromatic graphs
• Tools for counting odd cycles in graphs

Cited in

(1)

• scientific article; zbMATH DE number 3979084 (Why is no real title available?)

This page was built for publication: Counting critical subgraphs in \(k\)-critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2064752)