1. Introduction
All graphs we consider are finite and simple. A graph
$G$
is
$k$
-colorable if we can assign
$k$
colours to its vertices such that no adjacent vertices receive the same colour. We say a graph
$G$
is
$k$
-chromatic if it is
$k$
-colorable but not
$(k-1)$
-colorable. A graph
$G$
is called
$k$
-critical if
$G$
is
$k$
-chromatic but each of its proper subgraphs is
$(k-1)$
-colorable. For
$k\in \{1,2\}$
the only
$k$
-critical graph is
$K_k$
, and the family of 3-critical graphs is precisely the family of odd cycles. In this paper, we consider
$k$
-critical graphs for
$k\ge 4$
.
A central problem in graph theory asks to determine the maximum number of edges
$f_k(n)$
in an
$n$
-vertex
$k$
-critical graph (see [Reference Jensen and Toft6]). Before we discuss the literature on
$f_k(n)$
, we point out a relevant yet easy fact that the Turán graph
$T_k(n)$
(that is, the
$n$
-vertex balanced complete
$k$
-partite graph) has the maximum number of edges among all
$n$
-vertex
$k$
-chromatic graphs. Dirac [Reference Dirac2] gave
$f_6(n)\ge \frac 14 n^2+n$
by considering the graphs obtained by joining two vertex-disjoint odd cycles with the same number of vertices. Toft [Reference Toft12] proved that for every
$k\ge 4$
, there exists a positive constant
$c_k$
such that
$f_k(n)\ge c_k n^2$
holds for all integers
$n\ge k$
(except
$n=k+1$
). In the most basic and interesting cases
$k=4,5$
, the constants are given by
\begin{equation*}c_4\geq \frac {1}{16}=0.0625 \mbox { and } c_5\geq \frac {4}{31}\geq 0.129.\end{equation*}
In the general case when
$k\geq 6$
, explicit constructions in [Reference Toft12] show that there exist infinitely many values of
$n$
such that
\begin{equation*}f_k(n)\geq \left (\frac 12-\frac {3}{2k-\delta _k}\right )n^2,\end{equation*}
where
$\delta _k=0$
if
$k\equiv 0 \pmod 3$
,
$\delta _k=8/7$
if
$k\equiv 1 \pmod 3$
, and
$\delta _k=44/23$
if
$k\equiv 2 \pmod 3$
. To our best knowledge, no construction for giving better constants
$f_k(n)/n^2$
has been found since. It is also an open question if
$\lim _{n\to \infty } \frac{f_k(n)}{n^2}$
exists for each
$k\geq 4$
. In 2013, Pegden [Reference Pegden8] considered dense triangle-free
$k$
-critical graphs. He constructed infinitely many
$n$
-vertex triangle-free 4-critical graphs with at least
$\left (\frac{1}{16}-o(1)\right )n^2$
edges, triangle-free 5-critical graphs with at least
$\left (\frac{4}{31}-o(1)\right )n^2$
edges, and triangle-free
$k$
-critical graphs with at least
$\left (\frac{1}{4}-o(1)\right )n^2$
edges for every
$k\geq 6$
. The last bound is asymptotically best possible by Turán’s theorem. He also showed the existence of dense
$k$
-critical graphs without any odd cycle of length at most
$\ell$
for any
$\ell$
, which is again asymptotically tight for
$k\ge 6$
.
Turning to the upper bound of
$f_k(n)$
, since any
$n$
-vertex
$k$
-critical graph with
$n>k$
does not contain
$K_k$
as a subgraph, by Turán’s theorem one can easily obtain that
$f_k(n)< e(T_{k-1}(n))$
for any
$n>k\geq 4$
. Using a characterisation of Greenwell and Lovász [Reference Greenwell and Lovász5] for subgraphs of
$k$
-critical graphs and a classical theorem of Simonovits [Reference Simonovits10], Stiebitz [Reference Stiebitz11] improved this trivial bound in 1987 by showing that
\begin{equation} f_k(n) < e(T_{k-2}(n)) \mbox{ for sufficiently large integer } n. \end{equation}
It has been 35 years since then and as far as we are aware, this remains the best upper bound.
There is a natural relation between
$f_k(n)$
and the problem of determining the maximum number of copies of
$K_{k-1}$
in
$k$
-critical graphs. Abbott and Zhou [Reference Abbott and Zhou1] generalised an earlier result of Stiebitz [Reference Stiebitz11] on 4-critical graphs and showed that for each
$k\geq 4$
every
$k$
-critical graph on
$n$
vertices contains at most
$n$
copies of
$K_{k-1}$
. The bound was further improved in [Reference Kézdy and Snevily7]. Recently, Gao and Ma [Reference Gao and Ma4] proved a sharp result that for each
$n>k\geq 4$
, every
$k$
-critical graph on
$n$
vertices contains at most
$n-k+3$
copies of
$K_{k-1}$
. If we delete one edge for every
$K_{k-1}$
in a
$k$
-critical graph on
$n$
vertices, then this can result in a graph without containing
$K_{k-1}$
. Using Turán’s theorem and the above result of [Reference Gao and Ma4], we can derive that
\begin{equation*}f_k(n)\le e(T_{k-2}(n))+n-k+3 \mbox { for any } n > k\geq 4.\end{equation*}
In this paper, we focus on the upper bound of
$f_k(n)$
. Our first result improves the long-standing upper bound (1) of Stiebitz [Reference Stiebitz11].
Theorem 1.1.
For every integer
$k\ge 4$
there exist constants
$n_k$
and
$c_k\geq \frac{1}{36(k-1)^2}$
such that if
$n\ge n_k$
then
$f_k(n)\leq e(T_{k-2}(n))-c_k n^2$
.
Our second result considers 4-critical graphs. A better upper bound for
$f_4(n)$
than Theorem 1.1 is obtained in the following.
Theorem 1.2.
There exists a constant
$n_4$
such that if
$n\ge n_4$
then
$f_4(n)<0.164 n^{2} $
The proofs of both theorems rely on arguments from extremal graph theory (such as the stability lemma of Füredi [Reference Füredi3]) and a structural lemma (Lemma 2.1) given in the coming section. Lemma 2.1 indicates a partial structure in dense critical graphs (under certain constraints), which can be witnessed in many classical constructions of dense critical graphs (see the discussion at the beginning of Section 2). For that, we would like to give a full construction for the well-known Toft graph (see Figure 1 or [Reference Toft12]). The vertex set of the Toft graph is formed by 4 disjoint sets
$A,B,C,D$
with the same odd size, where
$A$
and
$D$
are odd cycles,
$B$
and
$C$
are independent sets, the edges between
$B$
and
$C$
form a complete bipartite graph, and both of the edges in
$(A,B)$
and in
$(C,D)$
form perfect matchings. It is easy to check that the
$n$
-vertex Toft graph is 4-critical and has
$\frac{1}{16}n^2+n$
edges. We remark that the Toft graph remains the best construction for dense 4-critical graphs.
Toft graph:
$|A|=|B|=|C|=|D|=5$
.
We use standard notation in graph theory. Let
$\overline{G}$
denote the complement of the graph
$G$
. For a vertex
$v$
in a graph
$G$
, let
$N_G(v)$
denote the neighbourhood of
$v$
in
$G$
, and let
$d_G(v)\,:\!=\,|N_G(v)|$
denote the degree of
$v$
in
$G$
. When
$G$
is clear from the context, we often drop the subscript. Let
$d(G)$
denote the average degree of the graph
$G$
. Also, for any
$S\subseteq V(G)$
, let
$G[S]$
denote the induced subgraph of
$G$
on the vertex set
$S$
. For any disjoint sets
$A,B\subseteq V(G)$
, let
$G[A,B]$
denote the induced bipartite subgraph of
$G$
with bipartition
$(A,B)$
.
The rest of the paper is organised as follows. In Section 2, we prove a lemma which is key for the coming proofs. Then we prove Theorem 1.1 in Section 3 and Theorem 1.2 in Section 4.
2. Key lemma
In this section, we prove our key lemma, which roughly says that if a
$k$
-critical graph
$G$
contains certain
$t$
copies of
$K_{k-2}$
sharing
$k-3$
common vertices, then there exists an “induced” matching of size
$t$
in
$G$
which are connected to these cliques (see Figure 2). This indicates a substructure similar to the Toft graph (and many other examples of
$k$
-critical graphs). In particular, it reveals that the structure of
$k$
-critical graphs cannot be close to the Turán graph
$T_{k-2}(n)$
and thus the inequality (1) should not be tight.
The red shading indicates
$W\subseteq N(x_1)\cap \ldots \cap N(x_{k-3})$
, and the blue shading indicates
$W\subseteq N(u)$
. Note that
$W^{\prime}$
and
$W$
may intersect when
$|W|\le 2$
.
Lemma 2.1.
Let
$k\ge 4$
and let
$G$
be a
$k$
-critical graph. Suppose that
$G\left [\{x_1,x_2,\ldots, x_{k-3}\}\right ]$
forms a copy of
$K_{k-3}$
and there exists a set
$W\subseteq N(x_1)\cap \ldots \cap N(x_{k-3})\cap N(u)$
for some vertex
$u\notin \{x_1,x_2,\ldots, x_{k-3}\}$
. Then there exist a set
$W^{\prime}$
and a bijection
$\varphi \,:\, W\rightarrow W^{\prime}$
such that
$N(\varphi (w))\cap W=\{w\}$
and
$N(w)\cap W^{\prime}=\{\varphi (w)\}$
hold for each
$w\in W$
. Moreover, if
$|W|\ge 3$
, then
$W$
is an independent set in
$G$
, and
$W^{\prime}\cap W=\emptyset$
.
Proof. For each vertex
$w\in W$
, by deleting the edge
$uw$
from the
$k$
-critical graph
$G$
, we can get a
$(k-1)$
-chromatic graph
$G^{\prime}$
. We denote the colour classes of
$G^{\prime}$
by
$\mathcal{C}_1,\mathcal{C}_2,\ldots,\mathcal{C}_{k-1}$
. It is easy to see the vertices
$u$
and
$w$
are in the same colour class. Since
$G[\{x_1,x_2,\ldots, x_{k-3},w\}]$
is a
$(k-2)$
-clique, we can assume
$x_1\in \mathcal{C}_1$
,
$x_2\in \mathcal{C}_2$
,…,
$x_{k-3}\in \mathcal{C}_{k-3}$
, and
$u,w\in \mathcal{C}_{k-2}$
. The fact
$W\subseteq N(x_1)\cap \ldots \cap N(x_{k-3})\cap N(u)$
tells us that the set
$W\backslash \{w\}$
(if not empty) must be contained in
$\mathcal{C}_{k-1}$
, and thus
$W\backslash \{w\}$
is an independent set in
$G$
. We claim
$N(w)\cap \mathcal{C}_{k-1}$
must contain a vertex, say
$\varphi (w)$
. Since otherwise
$\mathcal{C}_{1}, \ldots,\mathcal{C}_{k-3},\mathcal{C}_{k-2}-\{w\},\mathcal{C}_{k-1}\cup \{w\}$
can be a
$(k-1)$
-coloring of
$G$
, which contradicts the fact that
$G$
is
$k$
-critical. Besides,
$\{\varphi (w)\}\cup (W\backslash \{w\})\subseteq \mathcal{C}_{k-1}$
tells us that
$N(\varphi (w))\cap W=\{w\}$
. Now we define
$W^{\prime}\,:\!=\,\{\varphi (w)\,:\,w\in W\}$
. As we have shown that
$N(\varphi (w))\cap W=\{w\}$
holds for each
$w\in W$
, it is easy to see
$|W^{\prime}|=|W|$
,
$\varphi \,:\,W\rightarrow W^{\prime}$
is a bijection, and
$N(w)\cap W^{\prime}=\{\varphi (w)\}$
holds for each
$w\in W$
.
Moreover, if
$|W|\ge 3$
, then
$W$
is an independent set in
$G$
(since
$W\backslash \{v\}$
is an independent set in
$G$
for each vertex
$v\in W$
). By the fact that the edges between
$W^{\prime}$
and
$W$
precisely form a matching, we can see
$W^{\prime}\cap W=\emptyset$
in this case.
It would be very interesting to see if this lemma (or its proof) can be extended further.
3. The general case:
$\textit{k}$
-critical
Providing a simple and new proof of the stability for the Turán number ex
$(n,K_{r+1})$
, Füredi [Reference Füredi3] showed that if an
$n$
-vertex graph
$G$
is
$K_{r+1}$
-free and has at least
$e(T_{r}(n))-t$
edges where
$0\le t<e(T_{r}(n))<n^2$
, then there exists a partition
$V_1,\ldots, V_r$
of
$V(G)$
such that
$\sum _{i=1}^r e(G[V_i])\le t$
. The statement following Corollary 3 in [Reference Füredi3] also suggests that the partition
$V_1,\ldots, V_r$
is approximately balanced. We summarise this observation in the following lemma.
Lemma 3.1 (Füredi [Reference Füredi3]). Suppose that
$G$
is an
$n$
-vertex
$K_{r+1}$
-free graph with
$e(G)\ge e(T_{r}(n))-t$
where
$0\le t<e(T_{r}(n))<n^2$
. Then there exists a complete
$r$
-chromatic graph
$K\,:\!=\,K(V_1,\ldots,V_r)$
with
$V(K)=V(G)$
such that
\begin{equation*}|E(K)\backslash E(G)|\le 2t,\end{equation*}
and
\begin{equation*}\sum _{i=1}^r\left (|V_i|-\frac {n}{r}\right )^2 < 4t+o(n^2).\end{equation*}
We are ready to use Lemmas 2.1 and 3.1 to prove Theorem 1.1.
Proof of Theorem
1.1
. Fix
$k\ge 4$
and let
$C=\frac{1}{36(k-1)^2}$
. Let
$G$
be a
$k$
-critical graph on
$n$
vertices with
$e(G)> e(T_{k-2}(n))-C n^2$
. In the rest of the proof, we will always assume that
$n$
is large enough, and we denote
$V(G)$
by
$V$
for convenience. The result in [Reference Abbott and Zhou1] tells us the number of copies of
$K_{k-1}$
in
$G$
is at most
$n$
. So by deleting at most
$n$
edges in
$G$
, we obtain a spanning subgraph
$G^{\prime}$
which is
$K_{k-1}$
-free. Obviously we have
$e(G^{\prime})\ge e(G)-n> e(T_{k-2}(n))-(C n^2+n)$
.
With the application of Lemma 3.1, we get a partition
$V_0,V_1,\ldots,V_{k-3}$
of
$V$
and a complete
$(k-2)$
-chromatic graph
$K\,:\!=\,K(V_0,\ldots,V_{k-3})$
such that
$|E(K)\backslash E(G^{\prime})|\le 2(C n^2+n)$
and
\begin{equation*}\Big ||V_i|-\frac {n}{k-2}\Big | < \sqrt {4C n^2+o(n^2)} < \frac {n}{3(k-1)}+o(n) \mbox { for each }0\le i\le k-3.\end{equation*}
Without loss of generality, we assume
$|V_0|\ge \ldots \ge |V_{k-3}|$
. Thus
$|V_0|\ge n/(k-2)$
, and
$|V_{i}|\ge \frac{n}{k-2}-\frac{n}{3(k-1)}-o(n)$
for each
$0\le i\le k-3$
. We call the edges in
$E(K)\backslash E(G^{\prime})$
missing edges. And the number of missing edges incident to the vertex
$v$
in
$K$
is called the missing degree of
$v$
. For each
$0\le i\le k-3$
, we define
$B_i$
to be the set of
$\left \lceil \frac{n}{3(k-1)}\right \rceil$
vertices in
$V_i$
satisfying that there exists some
$m_i$
such that the missing degree of any vertex in
$B_i$
is at least
$m_i$
, and the missing degree of any vertex in
$U_i\,:\!=\,V_i-B_i$
is at most
$m_i$
. Note that
$m_i$
is unique, while
$B_i$
may be not. Since there are at most
$ 2(C n^2+n)$
missing edges in total, we have
$\sum _{i=0}^{k-3} m_i |B_i| <4(C n^2+n)$
, and thus we can get
\begin{equation*}\sum _{i=0}^{k-3} m_i < 4(C n^2+n)\Big/\left \lceil \frac {n}{3(k-1)}\right \rceil \le \frac {n}{3(k-1)}+12(k-1).\end{equation*}
And we can check that for each
$0\le i\le k-3$
, we have
\begin{align} |U_i|=|V_i|-|B_i| > \frac{n}{k-2}-\frac{n}{3(k-1)}-\frac{n}{3(k-1)}-o(n) > \frac{n}{3(k-2)} > \sum _{i=0}^{k-3} m_i+2. \end{align}
Fix an arbitrary vertex
$x_0\in U_0$
and let
$Y\,:\!=\,N_{G^{\prime}}(x_0)\backslash V_0$
. It is clear that
\begin{equation*}|Y|\ge n-|V_0|-m_0.\end{equation*}
Next, we want to find a copy of
$K_{k-3}$
in
$G^{\prime}$
on vertices
$x_1,x_2,\ldots,x_{k-3}$
with
$x_i\in U_i\cap Y=U_i\cap N_{G^{\prime}}(x_0)$
by greedily choosing the vertex
$x_i\in U_i\cap N_{G^{\prime}}(x_0)\cap \ldots \cap N_{G^{\prime}}(x_{i-1})$
for
$1\le i\le k-3$
one by one. By the definition of
$U_j$
, we know each vertex
$x\in U_j$
has at most
$m_j$
missing degree, which means
$|S\backslash N_{G^{\prime}}(x)|\le m_i$
for any
$S\subseteq V\backslash V_j$
. Then in the
$i$
’th iteration, we have
$|U_i\cap N_{G^{\prime}}(x_0)\cap \ldots \cap N_{G^{\prime}}(x_{i-1})|\ge |U_i|-\sum _{j=0}^{i-1} |U_i\backslash N_{G^{\prime}}(x_j)|\ge |U_i|-\sum _{j=0}^{i-1} m_j>2$
choices of
$x_i$
, where the last inequality comes from (2). Thus this algorithm will give us a copy of
$K_{k-3}$
as desired.
Then, since
$|U_i|-m_{k-2}\ge |U_i|-\sum _{i=0}^{k-3} m_j>2$
holds for each
$1\le i\le k-3$
by (2), we can find a vertex
$u\in U_{i_0}\cap Y$
distinct from
$x_1,x_2,\ldots,x_{k-3}$
, where we choose
$i_0$
such that
$m_{i_0}=\min \{m_1,\ldots,m_{k-3}\}$
. Let
$W\,:\!=\,N_{G^{\prime}}(x_1)\cap \ldots \cap N_{G^{\prime}}(x_{k-3})\cap N_{G^{\prime}}(u)\cap V_{k-2}$
. We can see
$W\ni x_0$
,
$W\cap Y=\emptyset$
, and
\begin{equation*}|W|\ge |V_{k-2}|-\sum _{i=1}^{k-3} m_j-m_{i_0}\ge |V_{k-2}|-\left (1+\frac {1}{k-3}\right )\sum _{i=1}^{k-3} m_j.\end{equation*}
Then by using Lemma 2.1, we get a set
$W^{\prime}$
with
$|W^{\prime}|=|W|$
such that
$|N_G(w)\cap W^{\prime}|=1$
for each
$w\in W^{\prime}$
, and
$|W^{\prime}\cap W|\le 2$
. Note that all vertices in
$Y$
are adjacent to the vertex
$x_0\in W$
in
$G^{\prime}\subseteq G$
, so we can see
$|W^{\prime}\cap Y|\le 1$
.
As
$W\cap Y=\emptyset$
,
$|W^{\prime}\cap W|\le 2$
,
$|W^{\prime}\cap Y|\le 1$
, and
$|W^{\prime}|=|W|$
, we get
$n\ge |W\cup Y\cup W^{\prime}|\ge 2|W|+|Y|-3$
. Thus
\begin{equation*}2|W|+|Y|\le n+3.\end{equation*}
But on the other hand, we can check that
\begin{align*} 2|W|+|Y|&\ge 2\left (|V_0|-\left (1+\frac{1}{k-3}\right )\sum _{j=1}^{k-3} m_j\right )+ \left (n-|V_0|-m_0\right )\\ &\ge n+|V_0|-2\left (1+\frac{1}{k-3}\right )\sum _{j=0}^{k-3} m_j\\ &\ge n+\frac{n}{k-2}-2\left (1+\frac{1}{k-3}\right )\left (\frac{n}{3(k-1)}+12(k-1)\right ) > n+3. \end{align*}
This derives a contradiction. So we have
$f_k(n)\le e(T_{k-2}(n))-C n^2$
for
$n$
sufficiently large.
We would like to remark that the above proof relies on the existence of
$K_{k-2}$
. (Recall that in Lemma 2.1,
$G[\{w,x_1,x_2,\ldots,x_{k-3}\}]$
forms a copy of
$K_{k-2}$
for each vertex
$w\in W$
.) So using this approach, we will not be able to improve the upper bound to the following
\begin{equation*}e(G)\leq \mathrm {ex}(n,K_{k-2})=e(T_{k-3}(n))\leq e(T_{k-2}(n))-\frac {n^2}{2(k-2)(k-3)};\end{equation*}
that says we are not able to obtain a constant
$c_k$
better than the order of magnitude
$k^{-2}$
.
4. The 4-critical case
In this section, we consider 4-critical graphs and prove Theorem 1.2.
Before presenting the proof of Theorem 1.2, we give a short proof of a slightly weaker bound (see Theorem 4.1) than Theorem 1.2 to illustrate the proof ideas. In doing this, we study certain local structure based on 2-paths (i.e., a path of length two) in the proof of Theorem 4.1, while we consider 4-cycles (i.e., a cycle of length four) in place of 2-paths in the proof of Theorem 1.2.
4.1 A weaker upper bound
We first show the following result.
Theorem 4.1.
For any integer
$n\geq 4$
, it holds that
$f_4(n)<\frac{1}{6} n^2+10 n\leq 0.167n^2+10n$
.
We also need two lemmas as follows. For a graph
$G$
, we let
$t(G)$
be the number of triangles in
$G$
. Note that Stiebitz [Reference Stiebitz11] found out that
\begin{align} t(G)\le n \text{ holds for every 4-critical graph }G \text{ on }n\text{ vertices.} \end{align}
For a vertex
$v$
, let
$t_G(v)$
be the number of triangles containing the vertex
$v$
in
$G$
. When
$G$
is clear, we often drop the subscript.
Lemma 4.2.
Suppose
$G$
has at most
$n$
triangles and minimum degree of at least 3. Then
$G$
contains a 2-path
$xyz$
such that
\begin{equation*}d(x)+d(y)+d(z)-3t(x)-3t(z)\ge \frac {6e(G)}{n}-\frac {9n^2}{e(G)}.\end{equation*}
Proof. For some vertex
$v\in V(G)$
, write
$N(v)=\{v_1,v_2,\ldots,v_s\}$
for some
$s\geq 3$
. Let
\begin{equation*}\mathcal {P}_v\,:\!=\,\{v_1 v v_2,\ldots, v_{s-1} v v_{s},v_{s} v v_1\}\end{equation*}
be a family of 2-paths with centre
$v$
. We have
$|\mathcal{P}_v|=d(v)$
, and
\begin{equation*}\sum _{xyz\in \mathcal {P}_v} \left (d(x)+d(y)+d(z)\right )={d(v)}^2+2\sum _{u\in N(v)} d(u),\end{equation*}
\begin{equation*}\sum _{xyz\in \mathcal {P}_v} \left (t(x)+t(z)\right )=2\sum _{u\in N(v)} t(u).\end{equation*}
Then let
$\mathcal{P}\,:\!=\,\bigcup _{v\in V(G)}\mathcal{P}_v$
. We have
\begin{equation*}|\mathcal {P}|=\sum _{v\in V(G)}d(v)=2e(G).\end{equation*}
Using Jensen’s inequality, we get
\begin{align*} \sum _{xyz\in \mathcal{P}} (d(x)+d(y)+d(z)) & =\! \sum _{v\in V(G)}{d(v)}^2+2 \!\sum _{v\in V(G),u\in N(v)} d(u)= \!\sum _{v\in V(G)}{d(v)}^2+2 \!\sum _{u\in V(G),v\in N(u)} d(u)\\ &=\sum _{v\in V(G)}{d(v)}^2+2\sum _{u\in V(G)}{d(u)}^2=3\sum _{v\in V(G)}{d(v)}^2\ge 12 e(G)^2/n. \end{align*}
Since every vertex in
$G$
has degree at most
$n-1$
and
$\sum _{u\in V(G)} t(u)=3t(G)\le 3n$
, we get
\begin{equation*}\sum _{xyz\in \mathcal {P}} (t(x)+t(z))=2\sum _{v\in V(G)} \sum _{u\in N(v)} t(u)=2\sum _{u\in V(G)}d(u)t(u) \le 2n\sum _{u\in V(G)} t(u) \le 6n^2.\end{equation*}
So by picking a 2-path
$xyz$
in
$\mathcal{P}$
uniformly and randomly, we see
\begin{equation*}\mathbb {E}[d(x)+d(y)+d(z)-3t(x)-3t(z)]\ge \frac {12 e(G)^2/n-18n^2}{|\mathcal {P}|}= \frac {6e(G)}{n}-\frac {9n^2}{e(G)}.\end{equation*}
Thus, we can find a 2-path
$xyz$
as desired.
Lemma 4.3.
For any 2-path
$xyz$
in a 4-critical graph
$G$
, we have
\begin{equation*}d(x)+d(y)+d(z)-3t(x)-3t(z)\le n+1.\end{equation*}
Proof. Let
$X\,:\!=\,N(x)$
,
$Y\,:\!=\,N(y)$
,
$Z\,:\!=\,N(z)$
, and
$W\,:\!=\,X\cap Z$
. If
$u\in X\cap Y$
,
$uxy$
is a triangle. So
$|X\cap Y|\le t(x)$
. Similarly,
$|Z\cap Y|\le t(z)$
. Then we have
\begin{align*}|X\cup Y\cup Z| & \ge |X|+|Y|+|Z|-|X\cap Y|-|Z\cap Y|-|X\cap Z|\\ & \ge d(x)+d(y)+d(z)-t(x)-t(z)-|W|.\end{align*}
By Lemma 2.1, we can find a set
$W^{\prime}\subseteq V(G)$
and a bijection
$\varphi \,:\, W\rightarrow W^{\prime}$
such that
$W^{\prime}=\{\varphi (w)\,:\,w\in W^{\prime}\}$
, and for each
$w\in W$
, we have both
$N(\varphi (w))\cap W=\{w\}$
and
$N(w)\cap W^{\prime}=\{\varphi (w)\}$
.
We consider the size of
$W^{\prime}\cap (X\cup Y\cup Z)$
. Since both
$N(\varphi (w))\cap W=\{w\}$
and
$N(w)\cap W^{\prime}=\{\varphi (w)\}$
hold for each
$w\in W$
, and we know
$y\in W$
, we can see
$|W^{\prime}\cap Y|\le |W^{\prime}\cap N(y)|\le 1$
. Suppose
$v^{\prime}\in W^{\prime}\cap X$
. There is a vertex
$v\in W$
such that
$vv^{\prime}$
is an edge. Then we see
$xvv^{\prime}$
is a triangle. So
$|W^{\prime}\cap X|\le 2t(x)$
. Similarly,
$|W^{\prime}\cap Z|\le 2t(z)$
. Totally, we have
\begin{equation*}|W^{\prime}\cap (X\cup Y\cup Z)|\le |W^{\prime}\cap X|+|W^{\prime}\cap Y|+|W^{\prime}\cap Z|\le 2t(x)+2t(z)+1.\end{equation*}
Finally, we get
\begin{align*} n&\ge |X\cup Y\cup Z\cup W^{\prime}|=|X\cup Y\cup Z |+|W^{\prime}|-|W^{\prime}\cap (X\cup Y\cup Z)|\\ &\ge \left (d(x)+d(y)+d(z)-t(x)-t(z)-|W|\right )+|W|-(2t(x)+2t(z)+1)\\ &=d(x)+d(y)+d(z)-3t(x)-3t(z)-1, \end{align*}
completing the proof of this lemma.
Now we can finish the proof of this subsection.
Proof of Theorem
4.1
. Let
$G$
be an
$n$
-vertex 4-critical graph. It is easy to see that the minimum degree of
$G$
is at least 3. By (3),
$G$
contains at most
$n$
copies of triangles, so we can apply Lemma 4.2 to
$G$
and get a 2-path
$xyz$
with
\begin{equation*}d(x)+d(y)+d(z)-3t(x)-3t(z)\ge \frac {6e(G)}{n}-\frac {9n^2}{e(G)}.\end{equation*}
Together with Lemma 4.3, we have
\begin{equation*}\frac {6e(G)}{n}-\frac {9n^2}{e(G)}\le n+1.\end{equation*}
This implies that
$e(G)< n^2/6+10 n.$
4.2 The proof of Theorem 1.2
To show Theorem 1.2, we need some new lemmas. The coming lemma can be easily obtained by averaging, which says that every graph contains an edge such that the sum of the degrees of its two endpoints is at least twice the average degree of the graph.
Lemma 4.4.
Any graph
$G$
contains an edge
$xy$
such that
\begin{equation*}d(x)+d(y)\ge 2d(G).\end{equation*}
Proof. By Jensen’s inequality, we can get
\begin{equation*}\sum _{xy\in E}\left (d(x)+d(y)\right )=\sum _{v\in V}d(v)^2\ge n d(G)^2.\end{equation*}
Note that
$|E|=\left (n d(G)\right )/2$
. Thus there exists an edge
$xy\in E$
such that
\begin{equation*}d(x)+d(y)\ge \frac { n d(G)^2}{\left (n d(G)\right )/2}=2d(G),\end{equation*}
proving the lemma.
We now give the following lemma about 4-cycles, which can be viewed as a generalisation of the previous lemma. Recall the well-known result of Reiman [Reference Reiman9] that any
$n$
-vertex graph without containing 4-cycles has at most
$\frac n 4 (1+\sqrt{4n-3})<n^{\frac 32}$
edges.
Lemma 4.5.
Any
$n$
-vertex graph
$G$
with
$e(G)>\frac n 4 (1+\sqrt{4n-3})$
contains a 4-cycle
$v_1v_2v_3v_4$
such that
\begin{equation*}d(v_1)+d(v_2)+d(v_3)+d(v_4)\ge 4d(G)-O(n^{\frac 34}).\end{equation*}
Proof. Fix
$\epsilon \,:\!=\,9n^{-\frac 14}$
. Note that
$G$
must contain 4-cycles by the result of Reiman [Reference Reiman9]. Suppose to the contrary that any 4-cycle
$v_1v_2v_3v_4$
in
$G$
satisfies
$d(v_1)+d(v_2)+d(v_3)+d(v_4)< 4d(G)-4\epsilon n.$
Let
$A\,:\!=\,\{v\in V\,:\,d(v)<d(G)\}$
and
$B\,:\!=\,\{v\in V\,:\,d(v)\ge d(G)\}$
. Then
$A\cup B$
forms a partition of
$V(G)$
such that
$G[B]$
does not contain any 4-cycle.
For each
$1\le i\le d(G)/\epsilon n$
, let
$A_i\,:\!=\,\{v\in V\,:\,d(G)-i \epsilon n\le d(v)< d(G)-(i-1)\epsilon n\}$
. Then these
$A_i$
’s form a partition of
$A$
. For each
$1\le i\le \left (n-d(G)\right )/\epsilon n$
, let
$B_i\,:\!=\,\{v\in V\,:\,d(G)+(i-1) \epsilon n\le d(v)< d(G)+i\epsilon n\}$
. Then these
$B_i$
’s form a partition of
$B$
. It is not hard to check that
$G[A_1]$
does not contain any 4-cycle, and for each
$1\le i\le \left (n-d(G)\right )/\epsilon n$
,
$G\left [\bigsqcup _{j=1}^{i+1}A_j,B_i\right ]$
does not contain any 4-cycle.
We delete all edges in
$G[B]$
,
$G[A_1]$
and
$G\left [\bigsqcup _{j=1}^{i+1}A_j,B_i\right ]$
for each
$1\leq i\le \left (n-d(G)\right )/\epsilon n$
to get a spanning subgraph
$G^{\prime}$
of
$G$
. By the result of Reiman [Reference Reiman9], we can obtain
\begin{equation*}e(G^{\prime})\ge e(G)-\left (2+\left (n-d(G)\right )/\epsilon n\right ) n^{\frac 32}\ge e(G)-2n^{\frac 32}-\frac 19 n^{\frac 74}\ge e(G)-\frac {19}{9}n^{\frac 74}.\end{equation*}
Thus we have
\begin{equation*}d(G^{\prime})\ge d(G)-\frac {38}{9}n^{\frac 34}.\end{equation*}
Note that any edge of
$G^{\prime}$
is either contained in
$A$
, or between
$A_j$
and
$B_i$
for some
$j\ge i+2$
; moreover,
$e(G^{\prime}[A_1])=0$
. Let
$xy$
be an edge in
$G^{\prime}$
. If
$x,y\in A$
, as
$e(G^{\prime}[A_1])=0$
, we can assume that
$y\in A\backslash A_1$
, which tells us
$d_{G^{\prime}}(y)\le d(G)-\epsilon n$
, so we have
$d_{G^{\prime}}(x)+d_{G^{\prime}}(y)\le d(G)+ d(G)-\epsilon n=2d(G)-\epsilon n$
. If
$x\in A_j, y\in B_i$
for some
$j\ge i+2$
, then we have
$d_{G^{\prime}}(x)+d_{G^{\prime}}(y)\le d(G)-(j-1)\epsilon n + d(G)+i\epsilon n\le 2d(G)-\epsilon n$
. Thus, as
$n$
is large enough, for any edge
$xy$
in
$G^{\prime}$
,
\begin{equation*}d_{G^{\prime}}(x)+d_{G^{\prime}}(y) < 2d(G)-\epsilon n=2d(G)-9 n^{\frac 34} < 2d(G^{\prime}).\end{equation*}
The following lemma is derived from Lemma 2.1, which provides an essential structure to the proof of Theorem 1.2. To enhance comprehension of the lemma, referencing Figure 3 can be particularly helpful in gaining a better understanding of the concepts involved.
Lemma 4.6.
Let
$G$
be a 4-critical graph. Suppose
$v_1v_2v_3v_4$
is a 4-cycle in
$G$
, and
$V_1,V_2,V_3,V_4$
are four sets such that
$\{v_2,v_4\}\subseteq V_1\subseteq N(v_1)$
,
$\{v_1,v_3\}\subseteq V_2\subseteq N(v_2)$
,
$\{v_2,v_4\}\subseteq V_3\subseteq N(v_3)$
, and
$\{v_1,v_3\}\subseteq V_4\subseteq N(v_4)$
. Let
$X=V_1\cap V_3$
and
$Y=V_2\cap V_4$
. Then there exist sets
$X^{\prime\prime}$
and
$Y^{\prime\prime}$
such that
-
•
$X^{\prime\prime}\cap \left (V_1\cup V_2\cup V_3\cup V_4\right )=\emptyset =Y^{\prime\prime}\cap \left (V_1\cup V_2\cup V_3\cup V_4\right )$
, -
•
$e(G[X^{\prime\prime},X])\le |X|$
and
$e(G[Y^{\prime\prime},Y])\le |Y|$
, and
-
•
$|X^{\prime\prime}|\ge |X|-2t_G(v_1)-2t_G(v_3)-2$
and
$|Y^{\prime\prime}|\ge |Y|-2t_G(v_2)-2t_G(v_4)-2$
.
Proof. As
$X\subseteq N(v_1)\cap N(v_3)$
, by Lemma 2.1 for
$k=4$
, there exists a set
$X^{\prime}\subseteq V(G)$
and a bijection
$\varphi \,:\, X\rightarrow X^{\prime}$
such that
$X^{\prime}=\{\varphi (x)\,:\,x\in X\}$
, and for each
$x\in X$
, we have both
$N(\varphi (x))\cap X=\{x\}$
and
$N(x)\cap X^{\prime}=\{\varphi (x)\}$
. We define
$X^{\prime\prime}\,:\!=\,X^{\prime}\backslash \left (V_1\cup V_2\cup V_3\cup V_4\right )$
, then obviously
$X^{\prime\prime}\cap \left (V_1\cup V_2\cup V_3\cup V_4\right )=\emptyset$
and
$e(G[X^{\prime\prime},X])\le |X|$
.
As
$Y\subseteq N(v_2)\cap N(v_4)$
, by Lemma 2.1 for
$k=4$
, there exists a set
$Y^{\prime}\subseteq V(G)$
and a bijection
$\phi \,:\, Y\rightarrow Y^{\prime}$
such that
$Y^{\prime}=\{\phi (y)\,:\,y\in Y\}$
, and for each
$y\in Y$
, we have both
$N(\phi (y))\cap Y=\{y\}$
and
$N(y)\cap Y^{\prime}=\{\phi (y)\}$
. We define
$Y^{\prime\prime}\,:\!=\,Y^{\prime}\backslash \left (V_1\cup V_2\cup V_3\cup V_4\right )$
, then obviously
$Y^{\prime\prime}\cap \left (V_1\cup V_2\cup V_3\cup V_4\right )=\emptyset$
and
$e(G[Y^{\prime\prime},Y])\le |Y|$
.
Then we want to show the last property.
All vertices in
$V_2$
are adjacent to the vertex
$v_2\in X$
. Then we have
$|X^{\prime}\cap V_2|\le 1$
since
$|N(x)\cap X^{\prime}|=1$
for each
$x\in X$
. Similarly, we have
$|X^{\prime}\cap V_4|\le 1$
,
$|Y^{\prime}\cap V_1|\le 1$
, and
$|Y^{\prime}\cap V_3|\le 1$
.
All vertices in
$V_1$
are adjacent to the vertex
$v_1$
. Since each vertex in
$X^{\prime}$
has a neighbour in
$X\subseteq N(v_1)$
, we can check that
$|X^{\prime}\cap V_1|\le 2 t(v_1)$
. Similarly, we have
$|X^{\prime}\cap V_3|\le 2 t(v_3)$
,
$|Y^{\prime}\cap V_2|\le 2 t(v_2)$
,
$|Y^{\prime}\cap V_4|\le 2 t(v_4)$
. Therefore,
\begin{equation*}|X^{\prime\prime}|= |X^{\prime}|-|X^{\prime}\cap \left (V_1\cup V_2\cup V_3\cup V_4\right )|\ge |X|-2t(v_1)-2t(v_3)-2,\end{equation*}
and
\begin{equation*}|Y^{\prime\prime}|= |Y^{\prime}|-|Y^{\prime}\cap \left (V_1\cup V_2\cup V_3\cup V_4\right )|\ge |Y|-2t(v_2)-2t(v_4)-2,\end{equation*}
completing the proof.
Now we are ready to prove Theorem 1.2. It said that
$f_4(n)<0.164 n^{2}$
for
$n \geq n_4$
, where
$n_4$
is a constant.
Proof of Theorem
1.2
. Throughout this proof, we assume that
$n$
is sufficiently large, and the subscripts of the notation such as
$v_i$
’s and
$V_i$
’s are under module
$4$
. Suppose for a contradiction that there exists an
$n$
-vertex 4-critical graph
$G$
with
$e(G)\ge 0.164 n^2$
. By (3),
$t(G)\le n$
. Let
$V_0\,:\!=\,\{v\in V(G)\,:\, t_G(v)\ge \sqrt n\}$
. Then clearly we have
$|V_0|<3\sqrt n$
. Let
$G^{\prime}\,:\!=\,G[V(G)-V_0]$
. It is not hard to see
$e(G^{\prime})\ge e(G)-n |V_0|>e(G)-3n^{\frac 32}\ge 0.164 n^2-o(n^2)$
. Note that
$t(G^{\prime})\le t(G)\le n$
. Therefore, by deleting at most
$n$
edges from
$G^{\prime}$
, we can get a subgraph
$G^{\prime\prime}\subseteq G^{\prime}$
such that
$t(G^{\prime\prime})=0$
,
$e(G^{\prime\prime})\ge e(G^{\prime})-n\ge 0.164 n^2-o(n^2)$
, and
$t_{G}(v)<\sqrt n$
for each
$v\in V(G^{\prime\prime})=V(G)-V_0$
. By applying Lemma 4.5 to
$G^{\prime\prime}$
, we can get a 4-cycle
$v_1v_2v_3v_4$
in
$G^{\prime\prime}$
such that
\begin{align} |V_1|+|V_2|+|V_3|+|V_4|\ge 8e(G^{\prime\prime})/n-o(n)\ge 1.312 n-o(n), \end{align}
where
$V_i\,:\!=\,N_{G^{\prime\prime}}(v_i)$
for each
$1\le i\le 4$
. Note that for each
$1\le i\le 4$
, every vertex in
$V_i\cap V_{i+1}$
must form a triangle with the vertices
$v_i, v_{i+1}$
in
$G^{\prime\prime}$
, which contradicts the fact
$t(G^{\prime\prime})=0$
. So it is clear that
\begin{equation*}V_i \cap V_{i+1}=\emptyset \mbox { for each }1\le i\le 4.\end{equation*}
Also it is easy to check that
$\{v_{i-1},v_{i+1}\}\subseteq V_i\subseteq N_{G}(v_i)$
for each
$1\le i\le 4$
. Define
$X=V_1\cap V_3$
and
$Y=V_2\cap V_4$
. Applying Lemma 4.6, we can get two sets
$X^{\prime\prime},Y^{\prime\prime}$
satisfying the three properties of Lemma 4.6. Note that
$X^{\prime\prime}$
and
$Y^{\prime\prime}$
are disjoint from
$V_1\cup V_2\cup V_3\cup V_4$
,
$V_1\cap V_3=X$
,
$V_2\cap V_4=Y$
, and
$V_i\cap V_{i+1}=\emptyset$
for each
$1\le i\le 4$
. So we can see that
\begin{align} |V_1|+|V_2|+|V_3|+|V_4|-|X|-|Y|+|X^{\prime\prime}\cup Y^{\prime\prime}|\le n. \end{align}
Besides, by using the last property in Lemma 4.6, we have
\begin{align} |X^{\prime\prime}\cup Y^{\prime\prime}|\ge \max \{|X^{\prime\prime}|,|Y^{\prime\prime}|\}\ge \frac{|X^{\prime\prime}|+|Y^{\prime\prime}|}{2}\ge \frac{|X|+|Y|}{2}-O(\sqrt n). \end{align}
By substituting inequalities (4) and (6) into inequality (5), we get
\begin{align} \frac{|X|+|Y|}{2}\ge |V_1|+|V_2|+|V_3|+|V_4|-n-O(\sqrt n)\ge 0.312 n-o(n). \end{align}
Then we consider the non-edges of the graph
$G$
, i.e., the edges of the graph
$\overline{G}$
. First, since
$V_i= N_{G^{\prime\prime}}(v_i)\subseteq N_{G}(v_i)$
and
$v_i\in V(G^{\prime\prime})$
, we can see
$e(G[V_i])\le t_{G}(v_i)\le \sqrt n$
for each
$1\le i\le 4$
. So
\begin{equation*}e(\overline {G}[V_i])\ge \binom {|V_i|}{2}-o(n^2)=\frac 12 |V_i|^2-o(n^2) \mbox { for each }1\le i\le 4.\end{equation*}
Thus by noting
$V_1\cap V_3=X$
,
$V_2\cap V_4=Y$
, and
$V_i\cap V_{i+1}=\emptyset$
for each
$1\le i\le 4$
, we can get
\begin{align} \left |\bigcup _{i=1}^{4}E(\overline{G}[V_i])\right |\ge \sum _{i=1}^{4}e(\overline{G}[V_i])-\binom{|X|}{2}-\binom{|Y|}{2}\ge \frac 12 \left (\sum _{i=1}^{4}|V_i|^2-|X|^2-|Y|^2\right )-o(n^2). \end{align}
Next, since any
$m$
-vertex triangle-free graph has at most
$\frac 14 m^2$
edges, we can see
$e(G[X^{\prime\prime}\cup Y^{\prime\prime}])\le \frac 14 |X^{\prime\prime}\cup Y^{\prime\prime}|^2+n$
by (3), and thus
\begin{align} e(\overline{G}[X^{\prime\prime}\cup Y^{\prime\prime}])\ge \frac 14 |X^{\prime\prime}\cup Y^{\prime\prime}|^2-o(n^2). \end{align}
By properties of
$X^{\prime\prime}, Y^{\prime\prime}$
ensured by Lemma 4.6, we can obtain
\begin{equation} e(\overline{G}[X^{\prime\prime},X])\ge |X^{\prime\prime}| |X|-|X|\ge |X|^2-o(n^2), \end{equation}
\begin{equation} e(\overline{G}[Y^{\prime\prime},Y])\ge |Y^{\prime\prime}||Y|-|Y|\ge |Y|^2-o(n^2). \end{equation}
So we can deduce that
\begin{align*} e(G)&= \binom{n}{2}-e(\overline{G})\le \binom{n}{2}-\frac 12 \left (\sum _{i=1}^{4}|V_i|^2-|X|^2-|Y|^2\right )-\frac 14 |X^{\prime\prime}\cup Y^{\prime\prime}|^2-|X|^2-|Y|^2+o(n^2)\\ &\le \frac 12 n^2-\frac 18 \left (|V_1|+|V_2|+|V_3|+|V_4|\right )^2-\frac 14\left (\frac{|X|+|Y|}{2}\right )^2-\left (\frac{|X|+|Y|}{2}\right )^2+o(n^2)\\ &\le \frac 12 n^2-\frac 18 (1.312n)^2-\frac 54 (0.312n)^2+o(n^2) < 0.1632n^2+o(n^2). \end{align*}
The inequalities are derived as follows: the first inequality is obtained from inequalities (8) to (11); the second inequality is derived from inequality (6) and the convexity of the square; and the third inequality is based on inequalities (4) and (7). This contradicts the assumption that
$e(G)\ge 0.164n^2,$
completing the proof of Theorem 1.2.
Our understanding of the functions
$f_k(n)$
is generally poor, and it is not even known if
\begin{align} \mbox{$f_4(n) < f_5(n)$ holds for sufficiently large integers $n$.} \end{align}
So it seems to be a natural next step to pursue the question of whether
$f_4(n)\leq cn^2$
holds for some constant
$c<\frac{4}{31}$
and sufficiently large
$n$
. Note that if this is true, then it would imply (12).
Acknowledgements
The authors would like to thank Prof. Alexandr Kostochka for many valuable comments on a preliminary version of the manuscript.
Funding
JM: Research supported in part by the National Key R and D Programme of China 2020YFA0713100, National Natural Science Foundation of China grant 12125106, Innovation Programme for Quantum Science and Technology 2021ZD0302902, and Anhui Initiative in Quantum Information Technologies grant AHY150200. TY: Research supported in part by Professor Hao Huang’s start-up grant at NUS and a MOE Academic Research Fund (AcRF) Tier 1 grant.
