Critical edge sets in vertex-critical graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913985833467904 |
|---|---|
| author | Skottova, Ema Steiner, Raphael |
| author_facet | Skottova, Ema Steiner, Raphael |
| contents | Criticality is a fundamental notion in graph theory that has been studied continually since its introduction in the early 50s by Dirac. A graph is called $k$-vertex-critical ($k$-edge-critical) if it is $k$-chromatic but removing any vertex (edge) lowers the chromatic number to $k-1$. A set of edges in a graph is called critical if its removal reduces the chromatic number of the graph.
In 1970, Dirac conjectured a rather strong distinction between the notions of vertex- and edge-criticality, namely that for every $k\ge 4$ there exists a $k$-vertex-critical graph that does not have any critical edges. This conjecture was proved for $k\ge 5$ by Jensen in 2002 and remains open only for $k=4$. A much stronger version of Dirac's conjecture was proposed by Erdős in 1985: Let $k\ge 4$ be fixed, and let $f_k(n)$ denote the largest integer such that there exists a $k$-vertex-critical graph of order $n$ in which no set of at most $f_k(n)$ edges is critical. Is it true that $f_k(n)\rightarrow \infty$ for $n\rightarrow \infty$?
Strengthening previous partial results, we solve this problem affirmatively for all $k>4$, proving that $$f_k(n)=Ω(n^{1/3}).$$ This leaves only the case $k=4$ open. We also show that a stronger lower bound of order $\sqrt{n}$ holds along an infinite sequence of numbers $n$. Finally, we provide a first non-trivial upper bound on the functions $f_k$ by proving that $$f_k(n)=O\left(\frac{n}{(\log n)^{Ω(1)}}\right)$$ for every $k\ge 4$. Our proof of the lower bound on $f_k(n)$ involves an intricate analysis of the structure of proper colorings of a modification of an earlier construction due to Jensen, combined with a gluing operation that creates new vertex-critical graphs without small critical edge sets from given such graphs. The upper bound is obtained using a variant of Szemerédi's regularity lemma due to Conlon and Fox. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08703 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Critical edge sets in vertex-critical graphs Skottova, Ema Steiner, Raphael Combinatorics 05C15, 05C69, 05C70 Criticality is a fundamental notion in graph theory that has been studied continually since its introduction in the early 50s by Dirac. A graph is called $k$-vertex-critical ($k$-edge-critical) if it is $k$-chromatic but removing any vertex (edge) lowers the chromatic number to $k-1$. A set of edges in a graph is called critical if its removal reduces the chromatic number of the graph. In 1970, Dirac conjectured a rather strong distinction between the notions of vertex- and edge-criticality, namely that for every $k\ge 4$ there exists a $k$-vertex-critical graph that does not have any critical edges. This conjecture was proved for $k\ge 5$ by Jensen in 2002 and remains open only for $k=4$. A much stronger version of Dirac's conjecture was proposed by Erdős in 1985: Let $k\ge 4$ be fixed, and let $f_k(n)$ denote the largest integer such that there exists a $k$-vertex-critical graph of order $n$ in which no set of at most $f_k(n)$ edges is critical. Is it true that $f_k(n)\rightarrow \infty$ for $n\rightarrow \infty$? Strengthening previous partial results, we solve this problem affirmatively for all $k>4$, proving that $$f_k(n)=Ω(n^{1/3}).$$ This leaves only the case $k=4$ open. We also show that a stronger lower bound of order $\sqrt{n}$ holds along an infinite sequence of numbers $n$. Finally, we provide a first non-trivial upper bound on the functions $f_k$ by proving that $$f_k(n)=O\left(\frac{n}{(\log n)^{Ω(1)}}\right)$$ for every $k\ge 4$. Our proof of the lower bound on $f_k(n)$ involves an intricate analysis of the structure of proper colorings of a modification of an earlier construction due to Jensen, combined with a gluing operation that creates new vertex-critical graphs without small critical edge sets from given such graphs. The upper bound is obtained using a variant of Szemerédi's regularity lemma due to Conlon and Fox. |
| title | Critical edge sets in vertex-critical graphs |
| topic | Combinatorics 05C15, 05C69, 05C70 |
| url | https://arxiv.org/abs/2508.08703 |