/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
[Er69b] Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph
Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), 27-35.
PDF
[Er93] Erdős, P., Some of my favorite solved and unsolved problems in graph theory.
Quaestiones Math. 16 (1993), 333-350.
[Di52] Dirac, G. A., A property of $4$-chromatic graphs and some remarks on critical graphs.
J. London Math. Soc. 27 (1952), 85-92.
[To70] Toft, B., On the maximal number of edges of critical $k$-chromatic graphs. Studia Sci.
Math. Hungar. 5 (1970), 461-470.
[St87] Stiebitz, M., Subgraphs of colour-critical graphs. Combinatorica 7 (1987), 303-312.
[LMY23] Luo, C., Ma, J. and Yang, T., On the maximum number of edges in $k$-critical graphs.
Combin. Probab. Comput. 32 (2023), 900-911.
arXiv:2301.01656
A graph G is k-critical if it has chromatic number k and every proper subgraph has
chromatic number less than k. For a finite graph a proper subgraph misses a vertex or an edge, so
this holds iff G.IsCritical k (deleting any vertex lowers the chromatic number) and deleting any
edge lowers the chromatic number.
The definition of Dirac quoted in [Er69b] uses only the edge condition. That would allow isolated
vertices, and then $f_k(n)$ below would be a running maximum. We use the standard notion, which is
also the one in [LMY23].
$f_k(n)$ is the largest number of edges of a k-critical graph on n vertices. A graph on n
vertices has at most $\binom{n}{2}$ edges, so the sSup is a maximum whenever such a graph exists.
If there is none (for example if $n < k$), the value is 0.
The conjectured value $\frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2$ of $f_k(n)$
for $k \geq 6$. It is also used for $k = 3$ in erdos_917.variants.erdos_three_dvd, where it is
$0$.
The constant $\delta_k$ of the constructions below: $\delta_k = 0$ if $k \equiv 0 \pmod 3$,
$\delta_k = 1/7$ if $k \equiv 1 \pmod 3$ and $\delta_k = 24/69$ if $k \equiv 2 \pmod 3$.
Let $k\geq 4$ and $f_k(n)$ be the largest number of edges in a graph on $n$ vertices which has
chromatic number $k$ and is critical (i.e. deleting any edge reduces the chromatic number).
Is it true that
$$f_k(n) \gg_k n^2?$$
This is the first part. It was proved by Toft [To70]. We read $\gg_k$ as: for each $k$ there is
$c > 0$ with $f_k(n) \geq cn^2$ for all large $n$.
Let $k\geq 4$ and $f_k(n)$ be the largest number of edges in a graph on $n$ vertices which has
chromatic number $k$ and is critical (i.e. deleting any edge reduces the chromatic number).
Let $k\geq 4$ and $f_k(n)$ be the largest number of edges in a graph on $n$ vertices which has
chromatic number $k$ and is critical (i.e. deleting any edge reduces the chromatic number).
More generally, is it true that, for $k\geq 6$,
$$f_k(n) \sim \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2?$$
This is the third part. It has a negative answer: the constructions in
erdos_917.variants.lower_construction disprove it for $k \not\equiv 0 \pmod 3$
(see erdos_917.variants.not_asymptotic).
Constructions of Stiebitz [St87] show that, for $k\geq 6$, there exist infinitely many values of
$n$ such that
$$f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor+\delta_k}\right)n^2$$
where $\delta_k=0$ if $k\equiv 0\pmod{3}$, $\delta_k=1/7$ if $k\equiv 1\pmod{3}$, and
$\delta_k = 24/69$ if $k\equiv 2\pmod{3}$.
[LMY23] state the same bound in the form $(\frac12-\frac{3}{2k-\delta_k'})n^2$ with
$\delta_k'=0,8/7,44/23$, and credit the constructions to Toft [To70].
The remaining case of the third question: is it true that, for $k\geq 6$ with $3 \mid k$,
$$f_k(n) \sim \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2?$$
For $k = 6$ this is erdos_917.parts.ii.
Erdős [Er69b] observed that Dirac's construction generalises to show that, if $3\mid k$, there are
infinitely many values of $n$ (those of the shape $mk/3$ where $m$ is odd) such that
$$f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{k/3}\right)n^2 + n.$$
We take $m \geq 3$, so that the cycle $C_m$ exists.
Luo, Ma, and Yang [LMY23] have improved this upper bound to
$$f_k(n) \leq \frac{1}{2}\left(1-\frac{1}{k-2}-\frac{1}{36(k-1)^2}+o(1)\right)n^2.$$
[LMY23, Theorem 1.1] proves the stronger bound
$f_k(n) \leq \mathrm{ex}(n;K_{k-1}) - \frac{n^2}{36(k-1)^2}$ for $k \geq 4$ and all large $n$, where
$\mathrm{ex}(n;K_{k-1})$ is the number of edges of the Turán graph $T_{k-2}(n)$. We state this form.