Extremal Regular Graphs of Given Chromatic Number

1. Introduction

An $r$-regular graph is a simple finite graph such that each of its vertices has degree $r$. Regular graphs are one of the most studied classes of graphs; especially those with symmetries such as Cayley graphs. Let $\mathrm{\Gamma }$ be a finite group and let $X=\{x_1,x_2,\dots ,x_t\}$ a generating set for $\mathrm{\Gamma }$ such that $X=X^{-1}$ with $1_{\mathrm{\Gamma }}\notin X$; a Cayley graph $Cay(\mathrm{\Gamma },X)$ has vertex set consisting of the elements of $\mathrm{\Gamma }$ and two vertices $g$ and $h$ are adjacent if $g{x}_i=h$ for some $1\le i\le t$. Cayley graphs are regular but there exist non-Cayley vertex-transitive graphs. The Petersen graph is a classic example of this fact.

The girth of a graph is the size of its shortest cycle. An $(r,g)$-graph is an $r$-regular graph of girth $g$. An $(r,g)$-cage is an $(r,g)$-graph of smallest possible order. The diameter of a graph is the largest length between shortest paths of any two vertices. An $(r;D)$-graph is an $r$-regular graph of diameter $D$.

While the cage problem asks for the constructions of cages, the degree-diameter problem asks for the construction of $(r;D)$-graphs of maximum order. Both of them are open and active problems (see ) in which, frequently, it is considered the restriction to Cayley graphs, see .

In this paper, we study a similar problem using a well-known parameter of coloration instead of girth or diameter. A $k$-coloring of a graph $G$ is a partition of its vertices into $k$ independent sets. The chromatic number $\chi (G)$ of $G$ is the smallest number $k$ for which there exists a $k$-coloring of $G$.

We define an $(r|\chi )$-graph as an $r$-regular graph of chromatic number $\chi$. In this work, we investigate the $(r|\chi )$-graphs of minimum order. We also consider the case of Cayley $(r|\chi )$-graphs.

The remainder of this paper is organized as follows: In Section 2 we show the existence of $(r|\chi )$-graphs, we define $n(r|\chi )$ as the order of the smallest $(r|\chi )$-graph, and similarly, we define $c(r|\chi )$ as the order of the smallest Cayley $(r|\chi )$-graph. We also exhibit lower and upper bounds on the orders of the extremal graphs. We show that the Turán graphs $T_{ak,k}$, antihole graphs (the complements of cycles) and $K_k\times K_2$ are Cayley $(r|\chi )$-graphs of order $n(r|\chi )$ for some $r$ and $\chi$. To prove that $K_k\times K_2$ are extremal we use instances of the Reed’s Conjecture for which it is true. In Section 3 we only consider non-Cayley graphs. We give another upper bound for $n(r|\chi )$ and we exhibit two families of $(r|\chi )$-graphs with a few number of vertices which are extremal for some values of $r$ and $\chi$. Finally, in Section 4 we study the small values $2\le r\le 10$ and $2\le \chi \le 6$. We obtain a full table of extremal $(r|\chi )$-graphs except for the pair $(6|6)$.

2. Cayley $(r|\chi )$-graphs

It is known that for any graph $G$, $1\le \chi (G)\le \mathrm{\Delta }+1$ where $\mathrm{\Delta }$ is the maximum degree of $G$. Therefore, for any $(r|\chi )$-graph we have that $$1\le \chi \le r+1.$$

Suppose that $G$ is a $(r|1)$-graph. Hence $G$ is the empty graph, then $r=0$. Therefore, the extremal graph is the trivial graph. We can assume that $2\le \chi \le r+1$.

Next, we prove that for any $r$ and $\chi$ such that $2\le \chi \le r+1$, there exists a Cayley $(r|\chi )$-graph $G$.

We recall that the $(n,k)$-Turán graph $T_{n,k}$ is the complete $k$-partite graph on $n$ vertices whose partite sets are as nearly equal in cardinality as possible, i.e., it is formed by partitioning a set of $n=ak+b$ vertices (with $0\le b<k$) into the partition of independent sets $(V_1,V_2,\dots ,V_b,V_{b+1},\dots ,V_k)$ with order $|V_i|=a+1$ if $1\le i\le b$ and $|V_i|=a$ if $b+1\le i\le k$. Every vertex in $V_i$ has degree $a(k-1)+b-1$ for $1\le i\le b$ and every vertex in $V_i$ has degree $a(k-1)+b$ for $b+1\le i\le k$. The $(n,k)$-Turán graph has chromatic number $k$, and size (see ) $$\lfloor \frac{(k-1)n^2}{2k}\rfloor .$$

Before to continue, we recall some definitions. Given two graphs $H_1$ and $H_2$, the cartesian product $H_1\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{H}_2$ is defined as the graph with vertex set $V(H_1)\times V(H_2)$ and two vertices $(u,u^{\prime })$ and $(v,v^{\prime })$ are adjacent if either $u=v$ and $u^{\prime }$ is adjacent with $v^{\prime }$ in $H_2$, or $u^{\prime }=v^{\prime }$ and $u$ is adjacent with $v$ in $H_1$. The following proposition appears in .

On the other hand, the chromatic number of $H_1\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{H}_2$ is the maximum between $\chi (H_1)$ and $\chi (H_2)$, see . Now we can prove the following theorem.

Now, we define $n(r|\chi )$ as the order of the smallest $(r|\chi )$-graph and $c(r|\chi )$ as the order of the smallest Cayley $(r|\chi )$-graph. Hence, $$r+1\le n(r|\chi )\le c(r|\chi )\le a\chi (b+1)$$ where $r=a(\chi -1)+b$ with $a\ge 1$ and $0\le b<\chi -1$.

To improve the lower bound we consider the $(n,\chi )$-Turán graph $T_{n,\chi }$. Suppose $G$ is an $(r|\chi )$-graph. Let $\varsigma$ be a $\chi$-coloring of $G$ resulting in the partition $(V_1,V_2,\dots ,V_{\chi })$ with $|V_i|=a_i$ for $1\le i\le \chi$. Then the largest possible size of $G$ occurs when $G$ is a complete $\chi$-partite graph with partite sets $(V_1,V_2,\dots ,V_{\chi })$ and the cardinalities of these partite sets are as equal as possible. This implies that $$\frac{nr}{2}\le \lfloor \frac{(\chi -1)n^2}{2\chi }\rfloor \le \frac{(\chi -1)n^2}{2\chi },$$ since $G$ has size $rn/2$. After some calculations we get that $$\frac{r\chi }{\chi -1}\le n.$$

An $(r|\chi )$-graph $G$ of $n(r|\chi )$ vertices is called extremal $(r|\chi )$-graph. Similarly, a Cayley $(r|\chi )$-graph $G$ of $c(r|\chi )$ vertices is called extremal Cayley $(r|\chi )$-graph. When $\chi -1|r$ the lower bound and the upper bound of Theorem 1 are equal. We have the following corollary.

In the remainder of this paper we exclusively work with $b\ne 0$, that is, when $\chi -1$ is not a divisor of $r$.

2.1. Antihole graphs

A hole graph is a cycle of length at least four. An antihole graph is the complement $G^c$ of a hole graph $G$. Note that a hole graph and its antihole graph are both connected if and only if their orders are at least five. In this subsection we prove that antihole graphs of order $n$ are extremal $(r|\chi )$-graphs for any $n$ at least six. There are two cases depending of the number of vertices.

1. $G=C_n^c$ for $n=2k$ and $k\ge 3$.

   The graph $G$ has regularity $r=2k-3$ and chromatic number $\chi =k$. Any $(2k-3|k)$-graph has an even number of vertices and at least $\frac{r\chi }{\chi -1}=\frac{(2k-3)k}{k-1}=2k-\frac{k}{k-1}$ vertices.

   If $k>2$, then $\frac{k}{k-1}<2$. Therefore we have the following result:

   $$n(2k-3,k)=c(2k-3,k)=2k$$ for all $k\ge 3$.

2. $G=C_n^c$ for $n=2k-1$ and $k\ge 4$.

   The graph $G$ has regularity $r=2k-4$ and chromatic number $\chi =k$. Any $(2k-4|k)$-graph has at least $\frac{r\chi }{\chi -1}=\frac{(2k-4)k}{k-1}=2k-2-\frac{2}{k-1}$ vertices.

   If $k-1>2$, we have that $\frac{2}{k-1}<1$. Therefore $$2k-2\le n(2k-4,k)\le c(2k-4,k)\le 2k-1$$ for all $k\ge 4$.

   Suppose that $G$ is a $(2k-4|k)$-graph of $2k-2$ vertices. Then $G=((k-1)K_2{)}^c$, i.e., $G$ is the complement of a matching of $k-1$ edges. Then $\chi (G)=k-1$, a contradiction. Therefore $$n(2k-4,k)=c(2k-4,k)=2k-1$$ for all $k\ge 4$.

Therefore, we have the following theorem.

A hole graph is also considered a $2$-factor since is a spanning $2$-regular graph. For short, we denote the disjoint union of $j$ cycles of lenght $i$ as $j{C}_i$.

Let $G$ be an union of cycles $$a_3{C}_3\cup a_4{C}_4\cup \dots \cup a_{2t}{C}_{2t}$$ for $a_i\ge 0$ with $i\in \{3,4,\dots ,2t\}$. Note that the complement $G^c$ of $G$ is the join of the complement of cycles.

Moreover, we have the following results.

For instance, there are three extremal $(5,4)$-graphs, namely, $C_8^c$, $(2C_4{)}^c$ and $(C_3\cup C_5{)}^c$. See also Table 1.

2.2. The case of $r=\chi$

In this subsection, we discuss the case of $r=\chi =k$, i.e., the $(k|k)$-graphs of minimum order. We have the following bounds so far: $$\lceil \frac{k^2}{k-1}\rceil =k+1\le n(k|k)\le 2k.$$

We prove that the upper bound is correct except for $k=4$ and maybe for $k=6,8,10,12$. To achieve it, we assume that there exist $(k|k)$-graphs of order $n\le 2k-2$, that is $$\lceil \frac{n}{2}\rceil <k=\chi .$$ Now, we use a bound for the chromatic number arising from the Reed’s Conjecture, see . We recall the clique number $\omega (G)$ of a graph $G$ is the largest $k$ for which $G$ has a complete subgraph of order $k$.

It is known that the conjecture is true for graphs satisfying Equation [Equation1], see . It follows that $k\le \omega (G)+1$ for any $(k|k)$-graph $G$ of order $n\le 2k-2$, that is, $\omega (G)=k$ or $\omega (G)=k-1$.

1. $\omega (G)=k$.

   Let $H_1$ be a clique of $G$ and $H_2=G\setminus V(H_1)$. There is a set of $k$ edges from $V(H_1)$ and $V(H_2)$. Therefore, if $t=n-k\le k-2$ is the order of $H_2$ and $m=(kt-k)/2$ is the number of edges in $H_2$, then $$m\le (\genfrac{}{}{0ex}{}{t}{2}).$$ We obtain that $k\le t$, a contradiction.

2. $\omega (G)=k-1$.

   Let $H_1$ be a clique of $G$ and $H_2=G\setminus V(H_1)$. There is a set of $2(k-1)$ edges from $V(H_1)$ to $V(H_2)$. Therefore, if $t=n-(k-1)\le k-1$ is the order of $H_2$ and $m=(kt-2(k-1))/2$ is the number of edges in $H_2$, then $$m\le (\genfrac{}{}{0ex}{}{t}{2}).$$ We obtain that $k\le t+1$, hence, $k=t+1$ and $n$ has to be $2k-2$. Since every vertex $v$ in $V(H_2)$ has degree $k$ in $G$, $v$ has at least two neighbours in $H_1$. By symmetry, $G$ is the union of two complete graphs $K_{k-1}$ with the addition of two perfect matchings between them. Its complement is a $(k-3)$-regular bipartite graph. Any perfect matching of $G^c$ induce a $(k-1)$-coloring in $G$, a contradiction.

We have the following results.

If $k$ is odd then the order of any $k$-regular graph is even, therefore:

We have that $C_7^c$ is the extremal $(4|4)$-graph. Next, assume that $k\ge 6$ is an even number and there exists a $(k|k)$-graph $G$ of $n=2k-1$ vertices. Owing to the fact that $\chi (G)\le n-\alpha (G)+1$ where $\alpha (G)$ is the independence number of $G$, we get that $\alpha (G)\le k$.

In was proved that the Reed’s conjecture holds for graphs of order $n$ satisfying $\chi >\frac{n+3-\alpha }{2}$. In the case of the graph $G$, we have that $$\frac{n+3-\alpha (G)}{2}\le \frac{k}{2}+1<k.$$ It follows that $\omega (G)\le k\le \omega (G)+1$. Newly, we have two cases:

1. $\omega (G)=k$.

   As we saw before, let $H_1$ be a clique of $G$ and $H_2=G\setminus V(H_1)$. There is a set of $k$ edges from $V(H_1)$ and $V(H_2)$. Therefore, if $t=k-1$ is the order of $H_2$ and $m=(kt-k)/2$ is the number of edges in $H_2$, then $$m\le (\genfrac{}{}{0ex}{}{t}{2}).$$ We obtain that $k\le t$, a contradiction.

2. $\omega (G)=k-1$.

   In was proved that every graph satisfies $$\chi \le \{\omega ,\mathrm{\Delta }-1,\lceil \frac{15+\sqrt{48n+73}}{4}\rceil \}.$$ Hence, for the graph $G$ we have that $k\le \lceil \frac{15+\sqrt{96k+25}}{4}\rceil .$ After some calculations we get that $k=6,8,10,12$, otherwise, $k>\lceil \frac{15+\sqrt{96k+25}}{4}\rceil .$

Finally, we have the following theorem.

We point out that if there exists an extremal $(k|k)$-graph $G$ of $2k-1$ vertices for $k\in \{6,8,10,12\}$, then $G$ has clique number $\omega =k-1$, a clique $H_1$ of order $\omega$ for which $G\setminus V(H_1)$ has $\frac{k}{2}-1$ edges, $G$ is Hamiltonian-connected and it has independence number $\alpha (G)$ such that $\alpha (G)\in \{k/4,\dots ,k/2+1\}$, see .

3. Non-Cayley constructions

In this section we improve the upper bound of $n(r|\chi )$ given on Theorem 1 by exhibiting a construction of graphs not necessarily Cayley. We assume that $r$ is not a multiple of $\chi -1$, therefore $2\le \chi \le r$. Additionally, we show two more constructions which are tight for some values.

3.1. Upper bound

To begin with, take the Turán graph $T_{n,\chi }$, for $n=a\chi +b$, $0<b<\chi$ with $r=a(\chi -1)+b$ and the partition $(V_1,V_2,\dots ,V_b,V_{b+1},\dots ,V_{\chi })$ such that $|V_i|=a+1$ if $1\le i\le b$ and $|V_i|=a$ if $b+1\le i\le \chi$. Every vertex in $V_i$ for $1\le i\le b$ has degree $r-1$ and every vertex in $V_i$ for $b+1\le i\le \chi$ has degree $r$.

Next, we define the graph $G_{n,\chi }$ as the graph formed by two copies $G_1$ and $G_2$ of $T_{n,\chi }$ with the addition of a matching between the vertices of degree $r-1$ of $G_1$ and the vertices of degree $r-1$ of $G_2$ in the natural way. In consequence, the graph $G_{n,\chi }$ is an $r$-regular graph of order $2n$ and chromatic number $\chi$. To obtain its chromatic number, suppose that $T_{n,\chi }$ has the vertex partition $V_i$, then the vertices of $V_i$ have the color $i$ in $G_1$ and the vertices of $V_i$ are colored $i+1$ mod $\chi$ in $G_2$. Hence $\chi =\chi (G_1)\le \chi (G_{n,\chi })\le \chi$ and then $\chi (G_{n,\chi })=\chi$.

3.2. The graph $T_{n,\chi }^{\ast }$

In this subsection we give a better construction for some values of $r$ and $\chi$. Consider the $(a\chi +b,\chi )$-Turán graph $T_{a\chi +b,\chi }$ such that $\chi >b\ge 0$ and partition $(V_1,\dots ,V_{\chi -b},\dots ,V_{\chi })$ for $\chi \ge 3$, $|V_i|=a_i=a\ge 2$ with $i\in \{1,\dots ,\chi -b\}$ and $|V_i|=a_i=a+1\ge 3$ with $i\in \{\chi -b+1,\dots ,\chi \}$.

We claim that $a$ is even or $\chi -b$ is even. To prove it, assume that $a$ and $\chi -b$ are odd. Hence, if $b$ is even, then $\chi$ is odd, $n=a\chi +b$ is odd and $r$ is odd, a contradiction. If $b$ is odd, then $\chi$ is even, $n=a\chi +b$ is odd and $r$ is odd, newly, a contradiction.

Now, we define the graph $T_{n,\chi }^{\ast }$ of regularity $r=a(\chi -1)+b-1$ as follows: If $\chi -b$ is even, the removal of a perfect matching between $X_i$ and $X_{i+1}$ for all $i\in \{1,3,\dots ,\chi -b-1\}$ of $T_{n,\chi }$ produces $T_{n,\chi }^{\ast }$. If $\chi -b\ge 3$ is odd then $a$ is even, therefore, the removal of a perfect matching between $X_i$ and $X_{i+1}$ for all $i\in \{4,6\dots ,\chi -b-1\}$ and a perfect matching between $V_1^{\prime }$ and $V_2^{″}$, $V_2^{\prime }$ and $V_3^{″}$, and $V_3^{\prime }$ and $V_1^{″}$ where $V_i\setminus V_i^{\prime }=V_i^{″}$ is a set of $a/2$ vertices for $i\in \{1,2,3\}$, of $T_{n,\chi }$ produces $T_{n,\chi }^{\ast }$.

The graphs $T_{n,\chi }^{\ast }$ improve the upper bound given in Theorem 1 for some numbers $n$ and $\chi$: $$\frac{r\chi }{\chi -1}=a\chi +b-\frac{\chi -b}{\chi -1}\le a\chi +b.$$ Hence, if $\frac{\chi -b}{\chi -1}<1$, the construction gives extremal graphs, that is, when $$1<b.$$

3.3. The graph $G_{a,c,t}$

Consider the $(at,t)$-Turán graph $T_{at,t}$ with partition $(V_1,\dots ,V_t)$. Now, we define the graph $G_{a,c,t}$ with $1\le c<a$ as follows: consider two parts of $(V_1,\dots ,V_t)$, e.g. $V_1$ and $V_2$, and $c$ vertices of these two parts $\{u_1,\dots ,u_c\}\subseteq V_1$ and $\{v_1,\dots ,v_c\}\subseteq V_2$.

The removal of the edges $u_i{v}_j$ for $i,j\in \{1,\dots ,c\}$ when $i\ne j$ (all the edges between $\{u_1,\dots ,u_c\}$ and $\{v_1,\dots ,v_c\}$ except for a matching) and the addition of the edges $u_i{u}_j$ and $v_i{v}_j$ for $i,j\in \{1,\dots ,c\}$ when $i\ne j$ (all the edges between the vertices $u_i$ and all the edges between the vertices $v_i$) results in the graph $G_{a,c,t}$.

The graph $G_{a,c,t}$ is a $a(t-1)$-regular graph of order $at$. Its chromatic number is $t+c-1$ because the partition $$(V_1\setminus \{u_2,\dots ,u_c\},V_2\setminus \{v_1,\dots ,v_{c-1}\},V_2,\dots ,V_t,\{u_2,v_1\},\dots ,\{u_c,v_{c-1}\})$$ is a proper coloring with $t+c-1$ colors. Moreover, the graph $G_{a,c,t}$ has a clique of $t+c-1$ vertices, namely, the vertices $\{u_1,\dots ,u_c,x_2,\dots ,x_t\}$ where $x_i\in V_i$ for $i\in \{3,\dots ,t\}$ and $x_2\in V_2\setminus \{v_1\dots ,v_c\}$.

The graphs $G_{a,c,t}$ improve the upper bound given in Theorem 1: $$\frac{t+c-1}{t+c-2}a(t-1)=at-a\frac{c-1}{t+c-2}\le at.$$ Hence, if $a\frac{c-1}{t+c-2}<1$, the construction gives extremal graphs, that is, when $$(a-1)(c-1)<t-1.$$

4. Small values

In this section we exhibit extremal $(r|\chi )$-graphs of small orders. These exclude the extremal graphs given before. Table 1 shows the extremal $(r|\chi )$-graphs for $2\le r\le 10$ and $2\le \chi \le 6$.

4.1. Extremal $(5|3)$-graph

Suppose that $G$ is an extremal $(5|3)$-graph of order $8$, i.e., its order equals the lower bound given in Theorem 1. Then its complement is $2$ regular. That is, $G^c$ is $C_8$ or $C_5\cup C_3$ or $C_4\cup C_4$. By Theorem 1, the complement of $C_8$ or $C_5\cup C_3$ or $C_4\cup C_4$ has chromatic number $4$. Since $G$ is $5$-regular, a $(5|3)$-graph of order $9$ does not exist and therefore $10$ is the best possible. The graph $G_{5,2,2}$ is an extremal $(5|3)$-graph with $10$ vertices.

4.2. Extremal $(7|\chi )$-graphs for $\chi =3,6$

Let $G$ be an extremal $(7|3)$-graph. Its order is at least $11$. Since its degree is odd, its order is at least $12$. The graph $T_{12,3}^{\ast }$ is an extremal $(7|3)$-graph.

Now, suppose that $G$ is an extremal $(7|6)$-graph. $G$ has at least $9$ vertices. Newly, because it has an odd regularity, $G$ has at least $10$ vertices. If this is the case, its complement is a $2$ regular graph. The graph $(2C_5{)}^c$ has chromatic number $6$. It is unique and it is Cayley.

4.3. Extremal $(9|3)$-graph

Any $(9|3)$-graph has $14$ vertices, i.e., its order equals the lower bound given in Theorem 2. Suppose that there exist at least one of degree $14$. Let $(V_1,V_2,V_3)$ a partition by independent sets. Some of the parts, $V_1$, has at least five vertices. Since the graph is $9$-regular, $V_1$ has exactly $5$ vertices. The induced graph of $V_2$ and $V_3$ is a bipartite regular graph of an odd number of vertices, a contradiction. Then, any $(9|3)$-graph has at least $16$ vertices.

Consider the graph $T_{16,3}$ with partition $(U,V,W)$ and the sets partition are $U=\{u_1,u_2,u_3,u_4,u_5\}$, $V=\{v_1,v_2,v_3,v_4,v_5\}$, $W=\{w_1,w_2,w_3,w_4,w_5,w_6\}$. The removal of the edges $$\{w_1{v}_1,v_1{u}_1,u_1{w}_4,w_2{v}_2,v_2{u}_2,u_2{w}_5,w_3{v}_3,v_3{u}_3,u_3{w}_6,u_4{v}_4,v_4{u}_5,u_5{v}_5,v_5{u}_4\}$$ is the graph $T_{16,3}^{\ast \ast }$ which is the extremal $(9|3)$-graph.

Acknowledgment

We thank Robert Jajcay for useful discussions. C. Rubio-Montiel was partially supported by PAIDI grant 007/19. The authors wish to thank the anonymous referees of this paper for their suggestions and remarks.

Conflict of Interest

The author declares no conflict of interests.