An equitable vertex \(k\)-coloring of a graph \(G\) is a proper vertex coloring with \(k\) colors such that the size of any two color classes differ by at most one. It was conjectured by Meyer in 1973 that every graph other than the complete graph \(K_n\) or an odd cycle \(C_{2m+1}\) admits an equitable vertex coloring with at most \(\Delta(G)\) colors, where \(\Delta(G)\) is the maximum degree of a vertex in graph \(G\). We show that the conjecture is true for middle graphs of some cycle-based graphs.
An equitable vertex \(k\)-coloring of a graph \(G\) is a proper vertex coloring with \(k\) colors such that the size of any two color classes differ by at most one. The notion was introduced by Erdős [1] in the complementary form, who asked about a decomposition of \(H\) (which would be \(\overline{G}\), the complement of graph \(G\), in our terminology) into cliques whose sizes differ by at most one. In 1964 he posed the following conjecture, reformulated by Grünbaum [3] in 1968 into the coloring language:
Conjecture 1.1(Erdős 1964, Grünbaum 1968). Every graph \(G\) with maximum degree \(\Delta(G) < k\) has an equitable vertex \(k\)-coloring.
The conjecture was proved by Hajnal and Szemerédi [4] in 1969. It is worth noticing that in contrast to the usual coloring, where a proper \(k\)-colorability implies \((k+1)\)-colorability, this is not the case for equitable \(k\)-colorability. The smallest example is \(K_{3,3}\) which is properly 2-colorable and also equitably 2-colorable, but while it is properly 3-colorable, it is not equitably 3-colorable.
In this paper, we focus on finding the smallest number \(k\) of colors such that a graph \(G\) is equitably \(k\)-colorable. Formally speaking, the equitable chromatic number \(\chi_{_=}(G)\) of a graph \(G\) is the smallest \(k\) such that \(G\) is equitably \(k\)-colorable.
Meyer [6] in 1973 posed a conjecture similar to Brooks Theorem.
Conjecture 1.2(Meyer 1973).Every graph \(G\) with maximum degree \(\Delta(G)\) other than \(K_n\) or \(C_{2m+1}\) satisfies \(\chi_{_=}(G)\leq\Delta(G)\).
There have been hundreds of papers published on this topic. For a recent comprehensive survey, we refer the reader to a manuscript by Kierstead, Kostochka, and Xiang [5].
In [2], Froncek et al. studied the equitable chromatic number of certain classes of path-based middle graphs. We expand their results into classes of cycle-based middle graphs of the same graph families and show that all of them satisfy the conjecture. Middle graphs in general are an interesting graph family, combining properties of the underlying graphs and their line graphs. The classes studied in this paper have high symmetry and are just a small sample of the whole class of cycle-based middle graphs. It may be certainly interesting to find more general results for cycle-based middle graphs with chained cycles of arbitrary length.
In this section, we formally define the classes of graphs that we then study in Section 3. We also offer some elementary bounds for the equitable chromatic number.
We start with the definition of the middle graph. Loosely speaking, the middle graph \(M(G)\) arises from \(G\) by adding a new vertex to the middle of each edge of \(G\), and then two new “middle” vertices are joined by an edge if their corresponding original edges were adjacent. It can be also viewed as the line graph \(L(G)\) superimposed over \(G\).
Definition 2.1. Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). The middle graph \(M(G)\) of the graph \(G\) has vertex set \[V(M(G)) = V(G)\cup E(G),\] where two vertices in \(V(M(G))\) are adjacent if either they are adjacent edges in \(G\) or one of them is an edge in \(G\) and the other is an endvertex of that edge. More formally, \[\begin{aligned} E(M(G))=&\{e_i e_j| e_i=xy_i,e_j=xy_j\in E(G) \ \text{for some\ } x,y_i,y_j\in V(G)\}\\ &\cup\{ex| e=xy\in E(G) \ \text{for some\ } x,y\in V(G)\}. \end{aligned}\]
We will construct and color middle graphs of the following graph families. In all definitions we denote by \(C_n\) the cycle with vertices \(x_1,x_2,\dots,x_n\) and edges \(e_i=x_ix_{i+1}, i=1,2,\dots,n\), where the addition in the subscript is calculated modulo \(n\) and \(0\) is replaced by \(n\). In what follows we use the usual notation \([k,n]=\{k,k+1,\dots,n\}\) and \([n]=\{1,2,\dots,n\}\).
Definition 2.2. The triangular cycle graph \(TC_n\) is based on the cycle \(C_n\) with additional vertices \(y_i, i\in[n]\) and edges \(y_ix_i\) and \(y_ix_{i+1}\) for \(i\in[n]\).
A segment of \(TC_n\) and the corresponding segment of \(M(TC_n)\) are shown in Figure 1. The new vertices and edges joining them are in red color.
Definition 2.3. The alternate triangular cycle graph \(ATC_{2n}\) is based on the cycle \(C_{2n}\) with additional vertices \(y_{2i}, i\in[n]\) and edges \(y_{2i}x_{2i}\) and \(y_{2i}x_{2i+1}\) for \(i\in[n]\).
A segment of \(ATC_{2n}\) and the corresponding segment of \(M(ATC_{2n})\) are shown in Figure 2. The new vertices and edges joining them are in red color.
Definition 2.4. The diamond cycle graph \(DC_n\) is obtained from the cycle \(C_n\) by replacing each edge \(x_ix_{i+1}\) with two paths \(x_i,y_i,x_{i+1}\) and \(x_i,y'_i,x_{i+1}\) where \(\{y_i,y'_i\}\cap\{y_j,y'_j\}=\emptyset\) for \(i\neq j; i,j\in[n]\).
A segment of \(DC_n\) and the corresponding segment of \(M(DC_n)\) are shown in Figure 3. The new vertices and edges and edges joining them are in red color.
Definition 2.5. The alternate diamond cycle graph \(ADC_{2n}\) is obtained from the cycle \(C_{2n}\) by replacing every edge \(x_{2i}x_{2i+1}\) with two paths \(x_{2i},y_{2i},x_{2i+1}\) and \(x_{2i},y'_{2i},x_{2i+1}\) where \(\{y_i,y'_i\}\cap\{y_j,y'_j\}=\emptyset\) for \(i\neq j; i,j\in[n]\).
A segment of \(ADC_{2n}\) and the corresponding segment of \(M(ADC_{2n})\) are shown in Figure 4. The new vertices and edges and edges joining them are in red color.
Definition 2.6. The quadrilateral cycle graph \(QC_n\) is obtained from the cycle \(C_n\) by adding a path \(x_i,y_i,y'_i,x_{i+1}\) of length \(3\) for every \(i\in[n]\) where \(\{y_i,y'_i\}\cap\{y_j,y'_j\}=\emptyset\) for \(i\neq j; i,j\in[n]\).
A segment of \(QC_n\) and the corresponding segment of \(M(QC_n)\) are shown in Figure 5. The new vertices and edges and edges joining them are in red color.
Definition 2.7. The alternate quadrilateral cycle graph \(AQC_{2n}\) is obtained from the cycle \(C_{2n}\) by adding a path \(x_{2i},y_{2i},y'_{2i},x_{2i+1}\) of length \(3\) for every \(i\in[n]\) where \(\{y_{2i},y'_{2i}\}\cap\{y_{2j},y'_{2j}\}=\emptyset\) for \(i\neq j; i,j\in[n]\).
A segment of \(AQC_{2n}\) and the corresponding segment of \(M(AQC_{2n})\) are shown in Figure 6. The new vertices and edges and edges joining them are in red color.
Because every equitable coloring is a proper vertex coloring, the following is elementary. We denote by \(\chi{(G)}\) the chromatic number of a graph \(G\), that is, the minimum number of colors needed for a proper vertex coloring of \(G\).
Observation 2.8. For every graph \(G\), \(\chi(G)\leq\chi_{_=}(G)\).
Another easy observation is the following. We denote by \(\deg_G(x)\) the degree of vertex \(x\) in \(G\), and by \(\deg_{M(G)}(x)\) or \(\deg_{M(G)}(e)\) the degree of vertex \(x\) or \(e\) in \(M(G)\).
Observation 2.9. For every graph \(G\), \(\Delta(G)+1\leq\chi(M(G))\leq2\Delta(G)\).
Proof. The lower bound follows from the fact that a vertex of degree \(d\) in \(G\) together with the incident edges induces in \(M(G)\) a clique \(K_{d+1}\) which needs to be colored with \(d+1\) colors. For the upper bound, we observe that for every vertex \(x\in G\), \(\deg_{M(G)}(x)=\deg_G(x)\), while for an edge \(e=yz\in G\), which is a vertex in \(M(G)\), we have \(\deg_{M(G)}(e) = \deg_G(y)+\deg_G(z)\). Therefore, \(\Delta(M(G))\leq2\Delta(G)\), and the upper bound follows from Brooks’ Theorem, because no middle graph is isomorphic to a complete graph or an odd cycle. ◻
There however seems to be no trivial upper bound on \(\chi_{_=}(M(G))\) related to \(\chi(G)\). As an example, observe that \(\chi(K_{1,n})=2\) and \(\chi_{_=}(K_{1,n})=\lceil n/2\rceil+1\), while \(\chi(M(K_{1,n}))=\chi_{_=}(M(K_{1,n}))=n+1\).
In this section, we obtain exact values of the equitable chromatic number \(\chi_{_=}(G)\) for all classes of graphs defined in Section 2. We start with middle graphs of triangular cycle graphs and alternate triangular cycle graphs.
With a slight abuse of usual terminology, we will say that each graph consists of \(n\) building blocks, although the graphs themselves are 2-connected and therefore our building blocks are not blocks in the usual sense. With this in mind, we will further use just the name “block”. We will be using colors red, blue, green, yellow, and orange, denoted as \(R,B,G,Y,O\), respectively.
We observe that in all our theorems, \(\chi_{_=}(M(G))=\chi(M(G))=\omega(M(G))\), where \(\omega(M(G))\) is the clique number of \(M(G)\). To prove the equalities, it is then enough to find equitable \(k\)-colorings of our graphs for \(k=\omega(M(G))\).
Theorem 3.1. For every \(n\geq2\), \(\chi_{_=}(M(TC_n))=5\) and \(\chi_{_=}(M(ATC_{2n}))=4\).
Proof. In both cases our constructions are recursive. We first find colorings of the graphs for small values of \(n\) and then show how to extend them to graphs with larger values of \(n\).
We present the building blocks for both graphs in Figure 7.
The base cases \(M(TC_3)\) and \(M(TC_{2k})\) are shown in Figure 8.
In Figure 9 we show how the graphs \(M(TC_{2k+3})\) are built. Notice that this can be done also for \(k=1\) to obtain \(M(TC_5)\) since \(M(TC_2)\) is a legitimate simple graph. We take the graph \(M(TC_{2k})\), split it at the yellow vertex \(x_i\) and fill in the segment shown in part (c).
Now we focus on the middle graph \(M(ATC_{2n})\). Recall that \(e_{2i-1}=x_{2i-1}x_{2i}\) in \(ATC_{2n}\) is the edge joining two triangles. We first color \(M(ATC_4)\) as in Figure 10 and observe that the vertices \(e_1\) and \(e_3\) (arising from edges \(e_1\) and \(e_3\) of \(ATC_4\)) are both colored yellow. We now have four green vertices, four red vertices, three blue and three yellow vertices.
Let \(\lambda(Z)\) denote the number of vertices colored with color \(Z\) and the ordered quadruple \((\lambda_n(A),\lambda_n(B),\lambda_n(C),\lambda_n(D))\) of the numbers of occurrences of colors in an equitable 4-coloring of \(M(ATC_{2n})\). Suppose we have a coloring where all vertices \(e_{2i-1}, i\in[n]\) are colored yellow and \[\lambda_n(A)\geq\lambda_n(B)\geq\lambda_n(C)\geq\lambda_n(D).\]
Then \[\lambda_n(A)\geq\lambda_n(D)\geq\lambda_n(A)-1.\]
By splitting \(e_{2i-1}\) and adding a block with color occurrences \((1,2,2,2)\)—that is, color \(A\) appears once—we obtain \[\begin{aligned} &(\lambda_{n+1}(A),\lambda_{n+1}(B),\lambda_{n+1}(C),\lambda_{n+1}(D)) \\ &\qquad= (\lambda_n(A)+1,\lambda_n(B)+2,\lambda_n(C)+2,\lambda_n(D)+2), \end{aligned}\] where \[\lambda_{n+1}(B)\geq\lambda_{n+1}(C)\geq\lambda_{n+1}(D)\geq\lambda_{n+1}(A),\] implying that the coloring of \(M(ATC_{2n+2})\) is again an equitable 4-coloring.
Therefore, we just need to find for every color \(X\in\{R,B,G,Y\}\) a coloring of the building block in which the color \(X\) appears once while each of the other three colors appears twice.
We present such colorings in Figure 11 and the proof is now complete. ◻
Now we look at diamond cycle graphs and alternate diamond cycle graphs.
Theorem 3.2. For every \(n\geq2\), \(\chi_{_=}(M(DC_n))=5\) and \(\chi_{_=}(M(ADC_{2n}))=4\).
Proof. We start with \(M(DC_n)\) and color the cliques \(K_5\) as shown in Figure 12. We observe from the construction of \(M(DC_n)\) that the uncolored vertices of degree two in the upper row are \(y_i, i\in [n]\), and in the lower row \(y'_i, i\in[n]\). It is obvious now that vertices \(y_i\) can be colored \(R, Y\) or \(B\) while \(y'_i\) can be colored \(O,G\), or \(B\).
We now color them as follows: \[f(y_i)=\begin{cases} Y \text{ when }i\equiv2,4\pmod{5},\\ R \text{ when }i\equiv0,3 \pmod{5},\\ B \text{ when }i\equiv1 \pmod{5}, \end{cases}\] and \[f(y'_i)=\begin{cases} O \text{ when }i\equiv0,2\pmod{5},\\ G \text{ when }i\equiv1,3 \pmod{5},\\ B \text{ when }i\equiv4 \pmod{5}. \end{cases}\]
Every color appears in each clique once, so to prove that our coloring is equitable, we need to show that the vertex colors on vertices \(y_i\) and \(y'_i\) are also assigned equitably. We present a table with the numbers of colors occurrences for all values of \(i\pmod{5}\). We start the table with \(i\equiv1\pmod{5}\), because we need to start with \(n=2\) for the smallest \(M(DC_n)\).
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline &1 &2 &3 &4 &5 \\ \hline Y &0 &1 &1 &2 &2 \\ \hline R &0 &0 &1 &1 &2 \\ \hline O &0 &1 &1 &1 &2 \\ \hline G &1 &1 &2 &2 &2 \\ \hline B &1 &1 &1 &2 &2 \\ \hline \end{array}\]
We can see that for each value of \(i\) the coloring is equitable, which proves our claim for \(M(DC_n)\).
Now we look at \(M(ADC_{2n})\). We first color graphs \(M(ADC_{2n})\) for \(n\in[4]\) as shown in Figure 13. Notice that what we denote as \(M(ADC_2)\) in fact arises from \(ADC_2\), corresponding to the cycle \(C_{2\cdot1}\). While \(C_{2\cdot1}\) is not a simple graph, \(ADC_2\cong K_4-e\) is.
The construction of any longer \(M(ADC_{2n})\) is now easy. Let \(n=4k+r, k\geq1, r\in[0,3]\). Then we cut \(M(ADC_8)\) and \(M(ADC_{2r})\) at the blue vertex \(e_{8}\) and \(e_{2r}\), respectively, and glue together \(k\) copies of the segment arising from \(M(ADC_8)\) and, if \(r>0\), one segment arising from \(M(ADC_{2r})\). This completes the construction. ◻
Our next pair of graphs is middle graphs of quadrilateral cycle graphs \(M(QC_n)\) and alternate quadrilateral cycle graphs \(M(AQC_{2n})\).
Theorem 3.3. For every \(n\geq2\), \(\chi_{_=}(M(QC_n))=5\) and \(\chi_{_=}(M(AQC_{2n}))=4\).
Proof. For \(M(QC_n)\), we start with colorings of \(M(QC_2)\) and \(M(QC_3)\) shown in Figure 14. The coloring schemes are \[(\lambda_{2}(R),\lambda_{2}(B),\lambda_{2}(G),\lambda_{2}(O),\lambda_2(Y)) =(3,2,3,3,3),\] and \[(\lambda_{3}(R),\lambda_{3}(B),\lambda_{3}(G),\lambda_{3}(O),\lambda_3(Y)) =(4,4,4,4,5).\]
All longer cycles will be again obtained by cutting and pasting segments arising from shorter cycles. We can WLOG assume that in \(M(AQC_{2n})\) we have a clique colored as in Figure 15 part (a). We split the graph at the yellow vertex \(x_i\) as shown in part (b) and fill the gap with one of the segments shown further in Figure 15 (c)–(g). In each of them one color is present only twice, while the remaining four thrice. We match the color present twice with the color of maximum appearance in \(M(AQC_n)\) to obtain an equitable coloring of \(M(AQC_{n+2})\). More precisely, we have \[\lambda_{n}(A)\geq\dots\geq\lambda_{n}(E)\geq\lambda_{n}(A)-1\] and obtain \[\begin{gathered} (\lambda_{n+2}(A),\lambda_{n+2}(B),\lambda_{n+2}(C),\lambda_{n+2}(D),\lambda_{n+2}(E))\\ =(\lambda_n(A)+2,\lambda_n(B)+3,\lambda_n(C)+3,\lambda_n(D)+3,\lambda_n(E)+3), \end{gathered}\] where \[\lambda_{n+2}(B)\geq\lambda_{n+2}(C)\geq\lambda_{n+2}(D)\geq\lambda_{n+2}(E)\geq\lambda_{n+2}(A)\geq\lambda_{n+2}(B)-1,\] which is an equitable distribution.
For \(M(AQC_n)\), we use the same method as above. We first color \(M(AQC_4)\) as shown in Figure 16 and then proceed recursively, splitting \(M(AQC_{2n})\) in a green vertex \(e_i\) and adding one block in which one color is present thrice and the other three twice as in Figure 17. The color occurring thrice is matched with the color of minimal appearance in \(M(AQC_{2n})\). The calculations are similar to the previous case and are left to the reader. ◻
