Tight Bounds Towards a Conjecture of Gallai

Abstract

We prove that for $n>k\ge 3$, if G is an n-vertex graph with chromatic number k but any of its proper subgraphs has smaller chromatic number, then G contains at most $n-k+3$ copies of a clique of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai.

1 Introduction

A graph G is called k-critical if its chromatic number is k but any proper subgraph of G has chromatic number less than k. This important notion was first introduced by Dirac (see [2]) and has been extensively studied over the past decades.

Throughout this paper, for a graph G and a positive integer $\ell$, let $t_\ell (G)$ denote the number of copies of the clique $K_\ell$ on $\ell$ vertices contained in G. Gallai (see [3, 6]) conjectured that every k-critical graph G on n vertices satisfies that $t_{k-1}(G)\le n$.

This holds trivially for $k\le 3$ (note that the only 3-critical graphs are odd cycles). Using an elegant argument of linear algebra, Stiebitz [6] confirmed this for 4-critical graphs G by showing $t_3(G)\le n$. On the other hand, he [6] proved that for any $k\ge 4$, there exist some constant $c_k>0$ and arbitrarily large k-critical graphs G on n vertices such that $t_\ell (G)\ge c_k n^\ell$ holds for each $\ell \in \{2,3,...,k-2\}$. Koester [5] provided an improvement for 4-critical planar graphs G by showing that if G has $n\ge 6$ vertices, then $t_3(G)\le n-1$. The cases $k\ge 5$ of Gallai’s conjecture were resolved completely by Abbott and Zhou [1], who extended Stiebitz’s arguments and proved that any k-critical graph G on n vertices has $t_{k-1}(G)\le n$ with equality only if $n=k$ and $G\cong K_n$. They [1] also showed that for any 4-critical graph G on n vertices, if G is not an odd wheel¹, then $t_3(G)\le n-2$. For integers $\ell , d\ge 2$, let $W(\ell ,d)$ denote the graph obtained from a disjoint union of a clique $K_d$ on d vertices and a cycle $C_\ell$ of length $\ell$ by joining each vertex of $K_d$ to each vertex of $C_\ell$. Observe that if $n-k+3$ is odd, then $W(n-k+3,k-3)$ is an n-vertex k-critical graph with exactly $n-k+3$ copies of $K_{k-1}$. Abbott and Zhou [1] posed the following problem, which was stated as a conjecture in Kézdy and Snevily [4].

Conjecture (Abbott and Zhou [1]) Let G be an n-vertex k-critical graph with $n>k\ge 4$. Then $t_{k-1}(G)\le n-k+3$.

This (if true) would be tight for infinitely many integers n as indicated by the above graph $W(n-k+3,k-3)$. The aforementioned result of Abbott and Zhou [1] on 4-critical graphs implies the case $k=4$, and the cases $k\le 7$ were confirmed by Su [7, 8]. The current best bound for the general case was obtained by Kezdy and Snevily [4] as follows.

Theorem 1

(Kézdy and Snevily [4]) Let G be an n-vertex k-critical graph with $n>k\ge 4$. Then $t_{k-1}(G)< n-3k/5+2$.

The proof of this theorem uses linear algebra as well as some careful analysis from structural graph theory. We mention that the above problems and results are discussed in detail in Sect. 5.9 of the book of Jensen and Toft [1] (see its page 103).

In this paper, we confirm the conjecture of Abbott and Zhou by proving the following.

Theorem 2

Let $n>k\ge 4$. Any n-vertex k-critical graph G has $t_{k-1}(G)\le n-k+3$.

Our proof uses linear algebra arguments, which originate from Stiebitz [6] and appear in the subsequent works [1, 4]. We would like to emphasize that the core part of our proof is different from [4], which we will elaborate in Sect. 2.

2 The Proof

To present the proof of Theorem 2, we will first need to introduce some notation and several existing results. Let G be an n-vertex graph with vertex set $V(G)=\{v_1,v_2,..., v_n\}$. For a subset $S\subseteq V(G)$, we define its incidence vector to be a 0-1 vector $\textbf{u}_S= (u_1,u_2,...,u_n)$, where $u_i=1$ if $v_i\in S$ and $u_i=0$ otherwise. The first lemma we need is given by Stiebitz [6], which reveals the special role of the graph $W(\ell ,k-3)$ in k-critical graphs.

Lemma 3

(Stiebitz [6]) Let $k\ge 4$. If G is a k-critical graph containing some $W(\ell , k-3)$ as a subgraph, then $G\cong W(\ell , k-3)$ and $\ell$ is an odd integer.

The following lemma is a direct consequence of a result of Abbott and Zhou [1].

Lemma 4

(Abbott and Zhou [1], see its Lemma 2) Let $k\ge 4$ and G be a k-critical graph that does not contain any $W(\ell , k-3)$ as a subgraph. Let $\textbf{x}_1,\textbf{x}_2,...,\textbf{x}_r$ be incidence vectors of all cliques $K_{k-1}$ in G. Then $\textbf{x}_1,\textbf{x}_2,...,\textbf{x}_r$ are linearly independent over GF(2).

The following nice lemma relates the total number of cliques in a k-critical graph to the number of cliques containing any fixed edge. The cases $d\in \{0,1\}$ were first obtained by Su [8] and the general case was later proved by Kezdy and Snevily [4]. We shall mention that our proof will only need the case $d=0$.

Lemma 5

(Kezdy and Snevily [4]) Let G be an n-vertex k-critical graph. If there is an edge in G that is contained in exactly d copies of $K_{k-1}$, then $t_{k-1}(G)\le n-(k-2-d)$.

We are ready to present the proof of our result Theorem 2.

Proof of Theorem 2

Let $n>k\ge 4$ be integers and let G be any k-critical graph on n vertices. We aim to show that $t_{k-1}(G)\le n-k+3$.

If G contains some $W(\ell , k-3)$, then by Lemma 3, $G\cong W(\ell , k-3)$ and $\ell =n-k+3\ge 4$ is odd, from which the desired conclusion $t_{k-1}(G)=n-k+3$ holds. Hence we may assume that there is no copy of $W(\ell , k-3)$ in G. In particular there is no $K_k$ in G and $G\not \cong K_k$, so by the result of Abbott and Zhou [1], we have $t_{k-1}(G)\le n-1$. For any $x\in V(G)$, let $t_{k-1}(x,G)$ denote the number of cliques $K_{k-1}$ in G containing x. Then we have

$$\begin{aligned} \sum _{x\in V(G)} t_{k-1}(x,G) = (k-1)\cdot t_{k-1}(G) \le (k-1)(n-1). \end{aligned}$$

Let u be the vertex minimizing $t_{k-1}(u,G)$ among all vertices in G. By the above inequality, we see that $t_{k-1}(u,G)\le k-2$.

Suppose that the neighborhood N(u) of the vertex u induces a complete subgraph of G. In this case, as G does not contain any copy of $K_k$, we see $|N(u)|\le k-2$. This is a contradiction, as the minimum degree of a k-critical graph is at least $k-1$.

Therefore, there exist two vertices $v,x\in N(u)$ such that v, x are not adjacent in G. For any edge $e\in E(G)$, we denote $t_{k-1}(e,G)$ to be the number of copies of $K_{k-1}$ in G that contain e. We may assume that $t_{k-1}(e,G)\ge 1$, i.e., any edge e is contained in at least one copy of $K_{k-1}$ (as otherwise Lemma 5 implies that $t_{k-1}(G) \le n-k+2$).

Since v, x are not adjacent, the set of all cliques $K_{k-1}$ containing uv is disjoint from the set of all cliques $K_{k-1}$ containing ux. So we have

$$\begin{aligned} t_{k-1}(uv,G)+t_{k-1}(ux,G)\le t_{k-1}(u,G)\le k-2. \end{aligned}$$

Because $t_{k-1}(ux,G)\ge 1$, we see that

$$\begin{aligned} t_{k-1}(uv,G)\le k-3. \end{aligned}$$

(1)

$\square$

Claim 1

There exists a clique $A=\{a_1,a_2,...,a_{k-1}\}$ of size $k-1$ such that $x\in A$ and $A\cap \{u,v\}= \emptyset$.

Proof

First we have by the minimality of $t_{k-1}(u,G)$ that $t_{k-1}(x,G) \ge t_{k-1}(u,G)$. There also exists a clique $K_{k-1}$ containing uv, that, in particular, contains u but not x. These two facts together indicate that there exists a clique A of size $k-1$, that contains x but not u. As $xv\notin E(G)$, this clique A cannot contain v as well, proving the claim. $\square$

Because G is k-critical, the subgraph $G-uv$ is $(k-1)$-colorable and thus there exists a proper coloring $\phi :V(G)\rightarrow \{1,2,..., k-1\}$ of $G-uv$ such that u and v are assigned the same color, say the color $k-1$. We now prove the following claim.

Claim 2

There exists a color $c\in \{1,2,...,k-2\}$ such that every clique $K_{k-1}$ in G contains a vertex that is colored by c under $\phi$. We may assume $c=k-2$.

Proof

To see this, we first note that each of the cliques $K_{k-1}$ in G not containing the edge uv must use all colors in $\{1,2,..., k-1\}$ under $\phi$. For any clique $K_{k-1}$ in G containing the edge uv, it uses exactly $k-3$ colors in $\{1,2,...,k-2\}$ under $\phi$, for which one color needs to be removed from the list $\{1,2,...,k-2\}$ for this claim. By (1), there are at most $k-3$ such cliques $K_{k-1}$, which together will remove at most $k-3$ colors from the list $\{1,2,...,k-2\}$ for this claim. This leaves at least one color $c\in \{1,2,...,k-2\}$ such that every clique in G witnesses the color c under $\phi$. $\square$

For each $1\le i\le k-1$, let

$$\begin{aligned} C_i=\{x\in V(G): \phi (x)=i\}. \end{aligned}$$

For the clique $A=\{a_1,a_2,...,a_{k-1}\}$ from Claim 1, we may assume that $a_i\in C_i$. Let us recall the properties of A and it will be crucial for us to notice that

$$\begin{aligned} a_{k-1}\in C_{k-1}\backslash \{u,v\}. \end{aligned}$$

(2)

Let $r= t_{k-1}(G)$ and let $T_1,T_2,\cdots ,T_r$ be all cliques $K_{k-1}$ in G. For each $1\le i\le r$, we use $\textbf{x}_i$ to denote the incidence vector of $T_i$, and for each $1\le j\le k-3$, we use $\textbf{y}_j$ to denote the incidence vector of the single-vertex set $\{a_j\}$.²

The rest of the proof will be devoted to show the statement that

$$\begin{aligned} \text{ the } \text{ vectors } \textbf{x}_1,\textbf{x}_2,...,\textbf{x}_r,\textbf{y}_1,\textbf{y}_2,...,\textbf{y}_{k-3} \text{ are } \text{ linearly } \text{ independent } \text{ over } \text{ GF(2). } \end{aligned}$$

Note that all these vectors are defined in an n-dimensional linear space over GF(2). If this statement is proved to be true, then we have $r+(k-3)\le n$, from which the conclusion of Theorem 2 that $t_{k-1}(G)=r\le n-k+3$ holds.

Suppose for a contradiction that there exist $\textbf{x}_{q_1},...,\textbf{x}_{q_s},\textbf{y}_{p_1},...,\textbf{y}_{p_m}$ such that

$$\begin{aligned} \textbf{x}_{q_1}+\textbf{x}_{q_2}+\cdots +\textbf{x}_{q_s}+\textbf{y}_{p_1}+\textbf{y}_{p_2}+\cdots +\textbf{y}_{p_m}=\textbf{0} \end{aligned}$$

(3)

over GF(2), where $1\le q_i \le r$ and $1\le p_j\le k-3$ for all possible $1\le i\le s$ and $1\le j\le m$. We may assume $q_i =i$ and $p_j =j$ for all i and j. By Lemma 4, $\textbf{x}_1,\textbf{x}_2,...,\textbf{x}_r$ are linearly independent over GF(2), so $m\ge 1$. Since the $\mathbf {y_i}$ are independent as well, we have $s\ge 1$.

Let $\mathcal {G} = \{T_1,T_2,\cdots ,T_s\}$. For any vertex $w\in V(G)$ and any pair $e\in \left( {\begin{array}{c}V(G)\\ 2\end{array}}\right)$, let $t(w,\mathcal {G})$ and $t(e,\mathcal {G})$ denote the number of cliques in $\mathcal {G}$ containing w and e, respectively.³ We observe from (3) that for any vertex $w\in V(G)$,

$$\begin{aligned} t(w,\mathcal {G}) \text{ is } \text{ odd } \text{ if } \text{ and } \text{ only } \text{ if } w\in \{a_1,a_2,...,a_m\}\text{. } \end{aligned}$$

(4)

As $1\le m\le k-3$, we get that $\{a_1,a_2,...,a_m\}\cap (C_{k-2}\cup C_{k-1})=\emptyset$, showing that $t(w,\mathcal {G})$ for all $w\in C_{k-2}\cup C_{k-1}$ are even (in particular, $t(a_{k-1},\mathcal {G})$ is even). By Claim 2, every clique in $\mathcal {G}$ contains exactly one vertex in $C_{k-2}$, so we derive that

$$\begin{aligned} |\mathcal {G}|=|\{(w,T_j): w\in C_{k-2}\cap T_j \text{ and } T_j\in \mathcal {G}\}|=\sum _{w\in C_{k-2}} t(w,\mathcal {G}) \text{ is } \text{ even. } \end{aligned}$$

(5)

We have seen from (4) that $t(a_{k-1},\mathcal {G})$ is even. To reach the final contradiction, we want to estimate the parity of $t(a_{k-1},\mathcal {G})$ using a different approach, i.e., by looking at the contributions of all edges between $a_{k-1}$ and $C_1$. This will be done in the coming claim.

Claim 3

$t(a_1a_{k-1},\mathcal {G})$ is odd, and for any $w\in C_1\backslash \{a_1\}$, $t(wa_{k-1},\mathcal {G})$ is even.

Proof

Let $w\in C_1$ be any vertex. If $wa_{k-1}\notin E(G)$, then it is clear that $w\ne a_1$ and $t(wa_{k-1},\mathcal {G})=0$ that is even. So from now on we may assume $wa_{k-1}\in G$. Then there exists a proper coloring $\chi _w: V(G)\rightarrow \{1,2,..., k-1\}$ of $G-wa_{k-1}$ such that w and $a_{k-1}$ are assigned the same color, say the color $k-1$. It is easy to see that every clique $K_{k-1}$ containing the edge $wa_{k-1}$ has exactly two vertices (i.e., w and $a_{k-1}$) with the color $k-1$ under $\chi _w$, while every other clique $K_{k-1}$ not containing $wa_{k-1}$ has exactly one vertex with the color $k-1$ under $\chi _w$; let us call this property $(\star )$.

Suppose that $w\in C_1\backslash \{a_1\}$. For any vertex z with $\chi _w(z) = k-1$, we have $z=a_{k-1}$, or $z=w\in C_1\backslash \{a_1\}$, or z is not adjacent to $a_{k-1}$. However in any case, such z is not contained in $\{a_1,a_2,...,a_m\}$. By (4), we see that $t(z,\mathcal {G})$ is even for any vertex z with $\chi _w(z) = k-1$. Let $\Lambda$ denote the number of pairs $(z,T_j)$ satisfying $z\in T_j\in \mathcal {G}$ and $\chi _w(z) = k-1$. By the above fact and the property $(\star )$, we get that

$$\begin{aligned} |\mathcal {G}|+t(wa_{k-1},\mathcal {G})=\Lambda =\sum _{z:~\chi _w(z) = k-1} t(z,\mathcal {G}) \text{ is } \text{ even. } \end{aligned}$$

As $|\mathcal {G}|$ is even (i.e., (5)), we then derive that $t(wa_{k-1},\mathcal {G})$ is even for any $w\in C_1\backslash \{a_1\}$.

It remains to consider $w=a_1$. By similar analysis, for any vertex $z\ne w$ with $\chi _w(z) = k-1$, we get that $t(z,\mathcal {G})$ is even. This together with the fact that $t(w,\mathcal {G})$ is odd imply that

$$\begin{aligned} |\mathcal {G}|+t(wa_{k-1},\mathcal {G}) = \sum _{z:~\chi _w(z) =k-1} t(z,\mathcal {G}) \text{ is } \text{ odd. } \end{aligned}$$

Thus $t(a_1a_{k-1},\mathcal {G})=t(wa_{k-1},\mathcal {G})$ is odd. This finishes the proof of Claim 3. $\square$

By fact (2), every clique K of size $k-1$ in G containing $a_{k-1}$ does not contain the edge uv, so we have $|K\cap C_i|=1$ for each $i\in \{1,2,...,k-1\}$. This shows that

$$\begin{aligned}t(a_{k-1},\mathcal {G}) = \sum _{w\in C_{1}} t(wa_{k-1},\mathcal {G}),\end{aligned}$$

which together with Claim 3 imply that $t(a_{k-1},\mathcal {G})$ is odd. But this is a contradiction to (4) as it oppositely says that $t(a_{k-1},\mathcal {G})$ is even. The proof of Theorem 2 now is complete. $\square$

It would be very interesting to determine all n-vertex k-critical graphs G with $t_{k-1}(G)=n-k+3$ for $n>k\ge 4$. For the case $k=4$, it is known from the result of Abbott and Zhou [1] that such 4-critical graphs can only be odd wheels. For $k\ge 5$, it seems to be challenging to say something about the structure of these k-critical graphs from the proof presented here. We tend to believe that in case $n-k+3$ is odd, the graph $G=W(n-k+3, k-3)$ is the only extremal graph for Theorem 2 satisfying that $t_{k-1}(G)=n-k+3$.

There also is a related conjecture proposed by Su [8], which states that any k-critical graph of order $n>k$ has an edge that is contained in at most one clique $K_{k-1}$ on $k-1$ vertices. Su proved that this conjecture would imply Theorem 2, and this proof was extended by Kézdy and Snevily [4] to Lemma 5. The cases $4\le k\le 7$ were verified by Su [8]. It is interesting to have an alternative proof of Theorem 2 via this conjecture.