Critical edge sets in vertex-critical graphs
Ema Skottova, Raphael Steiner · 2025
Read Critical edge sets in vertex-critical graphs by Ema Skottova, Raphael Steiner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08703.txt.
Introduction
Skottova and Steiner wrote a pure mathematics paper in twenty twenty-five about critical edge sets in vertex-critical graphs. A graph needs a certain number of colors so that linked points differ. It is called vertex-critical when removing any single point lowers that number, and a set of edges is critical when removing those edges does the same.
Back in nineteen seventy, Dirac guessed that for every color count of four or more, some vertex-critical graph has no critical edges at all. A stronger guess by Erdős asked how large a set of edges can avoid being critical as graphs grow. The authors settle that stronger question for all color counts above four, with a matching weaker bound along an endless run of sizes. They also give the first real upper bound for every case. Only the four-color case stays open.
Catalog record
| CREATOR | Ema Skottova, Raphael Steiner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-08703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Critical edge sets in vertex-critical graphs Thanks: E.S.: Department of Mathematics, ETH Zürich, Switzerland. Thanks: [email protected] Thanks: R.S.: Department of Mathematics, ETH Zürich, Switzerland. Thanks: [email protected] . Thanks: The research of R.S. was funded by the SNSF Ambizione Grant No. 216071 of the Swiss National Science Foundation. Ema Skottova, Raphael Steiner Abstract . 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 k -vertex-critical ( k k -edge-critical) if it has chromatic number k k but the removal of any vertex (edge) lowers the chromatic number to k − 1 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 ≥ 4 k\geq 4 there exists a k k -vertex-critical graph that does not have any critical edges. This conjecture was proved for k ≥ 5 k\geq 5 by Jensen in 2002 and remains open only for k = 4 k=4 . A much stronger version of Dirac’s conjecture was proposed by Erdős in 1985: Let k ≥ 4 k\geq 4 be fixed, and let f k ( n ) f_{k}(n) denote the largest integer such that there exists a k k -vertex-critical graph of order n n in which no set of at most f k ( n ) f_{k}(n) edges is critical. Is it true that f k ( n ) → ∞ f_{k}(n)\rightarrow\infty for n → ∞ n\rightarrow\infty ? Strengthening previous partial results, we solve this problem affirmatively for all k > 4 k>4 , proving that f k ( n ) = Ω ( n 1 / 3 ) . f_{k}(n)=\Omega(n^{1/3}). This leaves only the case k = 4 k=4 open. We also show that the stronger lower bound f k ( n ) ≥ Ω ( n 1 / 2 ) f_{k}(n)\geq\Omega(n^{1/2}) holds along an infinite sequence of numbers n n . Finally, we provide a first non-trivial upper bound on the functions f k f_{k} by proving that f k ( n ) = O ( n ( log n ) Ω ( 1 ) ) f_{k}(n)=O\left(\frac{n}{(\log n)^{\Omega(1)}}\right) for every k ≥ 4 k\geq 4 . Our proof of the lower bound on f k ( n ) 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. 1. Introduction The chromatic number \chi(G) of a graph G is one of the most fundamental and well-studied graph parameters with applications in combinatorics, scheduling and optimization, whose study dates back at least to 1852 when Francis Guthrie posed his nowadays famous Four-Color-Problem . Despite tremendous amounts of effort put into understanding this parameter by graph theorists throughout the last century, many basic questions and conjectures about its properties still remain open today. We refer to the recent surveys of Norin and Scott [ 18 , 20 ] for summaries of some selected seminal work and open problems on the chromatic number. In many of these open problems, one is given a particular graph class \mathcal{G} and aims to prove that the chromatic number of all graphs in \mathcal{G} is less than some constant k\in\mathbb{N} . Typically, in these problems the class \mathcal{G} is hereditary , i.e., closed under taking induced subgraphs. In such cases, a powerful general approach towards proving the desired upper bound for the chromatic number of graphs in \mathcal{G} is to go by contradiction: Consider a supposed smallest counterexample G\in\mathcal{G} , i.e. a smallest graph in the class satisfying \chi(G)\geq k , and prove so many properties about this smallest counterexample that eventually a contradiction is reached, concluding the proof. One easily checks that every such smallest counterexample G must have the property that \chi(G)=k , but for every vertex v of G , the graph G-v obtained from G by removing v results in a (k-1) -colorable graph. If the graph class \mathcal{G} is additionally closed under taking arbitrary subgraphs, then one even knows that any graph obtained from G by removing an edge is (k-1) -colorable. Motivated by this, the notion of critical graphs has emerged and has been continually studied in graph theory since the early 1950s (see [ 6 ] for one of the first papers on critical graphs and [ 12 , 15 , 22 ] for surveys and books on the subject), with applications beyond pure graph coloring problems such as to Turán numbers, see [ 21 ] for an example. A vertex, edge or set of edges in a graph G is called critical if its removal from G creates a graph with smaller chromatic number than G . Given an integer k\geq 1 , we say that a graph G with \chi(G)=k is k -vertex-critical if every vertex of it is critical, and we say that it is k -edge-critical if every edge is critical. Finally, it is called k -critical if it is both k -vertex- and k -edge-critical. Several fundamental problems concerning these notions remain open, one of which is the degree to which they relate to each other. While it is easy to see that every k -edge-critical graph without isolated vertices is also k -vertex-critical, it is not too difficult to construct examples where the converse does not hold. In 1970, Dirac (cf. [ 16 , 7 ] ) put forth a striking conjecture that claims an even stronger distinction between the notions: He conjectured that for every integer k\geq 4 there exists a graph that is k -vertex-critical, but at the same time none of its edges is critical, i.e., removing any edge from the graph does not alter the chromatic number. We remark that the condition k\geq 4 in Dirac’s conjecture is necessary: For k=3 one can easily show that the only 3 -vertex-critical graphs are the odd cycles, and these also have critical edges (in fact, they are also edge-critical). For a long time, not even a single vertex-critical graph was known that does not have critical edges. The first construction of such a graph, resolving the k=5 case of Dirac’s conjecture, was provided by Brown [ 2 ] in 1992. It took 10 more years for further cases of Dirac’s conjecture to be resolved: First, Lattanzio [ 16 ] proved an affirmative answer to Dirac’s conjecture for all integers k\geq 4 such that k-1 is not a prime number. Independently, Jensen [ 9 ] managed to prove the conjecture for all k\geq 5 . Jensen’s result remains the state of the art on Dirac’s conjecture, notably with the intriguing case k=4 still left open after more than 50 years. The only partial result addressing this case in the literature is due to Jensen and Siggers [ 11