An improved bound on the chromatic number of the Pancake graphs

The Pancake graph $P_{n},\ n\geqslant 2$, is defined as the Cayley graph over the symmetric group $\mathrm{Sym}_{n}$ with the generating set of all prefix–reversals $r_{i},\ 2\leqslant i\leqslant n$, inverting the order of any substring $[1,i]$ of a permutation when multiplied on the right. It is a connected vertex–transitive $(n-1)$-regular graph without loops and multiple edges of order $n!$. It contains all cycles $C_{l}$ of length $l$, where $6\leqslant l\leqslant n!$ [14, 23].

A mapping $c:V(\Gamma)\rightarrow\{1,2,\ldots,k\}$ is called a proper $k$–coloring of a graph $\Gamma=(V,E)$ if $c(u)\neq c(v)$ whenever the vertices $u$ and $v$ are adjacent. The chromatic number $\chi(\Gamma)$ of a graph $\Gamma$ is the least number of colors needed to properly color vertices of $\Gamma$. A subset of vertices assigned to the same color forms an independent set, i.e. a proper $k$–coloring is the same as a partition of the vertex set into $k$ independent sets. The trivial lower and upper bounds on the chromatic number of the Pancake graphs are given as follows:

Indeed, the graph $P_{n}$ is $(n-1)$–regular, hence by Brooks’ theorem [4] we have the upper bound. Moreover, $\chi(P_{3})=2$ since $P_{3}\cong C_{6}$, and $\chi(P_{4})=3$ since there are $7$–cycles in $P_{n}$ for any $n\geqslant 4$ [19] which gives us the lower bound. The Brooks’ bound is improved by $1$ for graphs with $\omega\leqslant(\Delta-1)/2$, where $\omega$ and $\Delta$ are the size of the maximum clique and the maximum degree of the graph (see [5, 6]). Since $\omega(P_{n})=2$, then $\chi(P_{n})\leqslant n-2$ for any $n\geqslant 6$. Moreover, there is a proper $3$–coloring of $P_{5}$ [18]. Thus, we have:

Catlin’s bound for $C_{4}$–free graphs [7], that is $\chi\leqslant\frac{2}{3}\left(\Delta+3\right)$, gives one more bound for any $n\geqslant 8$:

Using structural properties of $P_{n}$, the following bounds were obtained in [18]:

These bounds improve (2) for $n\geqslant 7$, however Catlin’s bound (3) is still better for all $n>28$ and some smaller $n$ (for example, $n=21,25,26,27$). Thus, they are far from good. Meanwhile, the asymptotic bound $\chi(P_{n})\leqslant O\left(\frac{n-1}{log(n-1)}\right)$ holds for the Pancake graphs which follows from the results for $C_{3},C_{4}$–free graphs [10, 15].

In this paper in Section 2 we present a new upper bound which improves Catlin’s bound (3). The new bound is obtained using a subadditivity property of the chromatic number of $P_{n}$ and known chromatic numbers for $n\leqslant 9$. We have $\chi(P_{3})=2$ since $P_{3}\cong C_{6}$, and $\chi(P_{4})=3$ since there are $7$–cycles in $P_{n},\,n\geqslant 4$. An example of a proper $3$–coloring for $P_{5}$ was given in [18]. An optimal $4$-coloring for $P_{6}$ was computed by Tomaž Pisanski, University of Primorska, Koper, Slovenia, and Jernej Azarija, University of Ljubljana, Slovenia, so $\chi(P_{6})=4$. Since $P_{n-1}$ is an induced subgraph of $P_{n}$, then $\chi(P_{7})$ is at least $4$, and from (4) we have $\chi(P_{7})=4$. Optimal $4$-colorings for $P_{8}$ and $P_{9}$ were computed by A. H. Ghodrati, Sharif University, Tehran, Iran. By (5), $4\leqslant\chi(P_{n})\leqslant 12$, where $10\leqslant n\leqslant 16$, however, proper $4$-colorings in these cases are unknown. The known chromatic numbers are presented in the Table 1.

In Section 3 an equitable coloring is considered. A graph $\Gamma$ is said to be equitably $k$-colorable if $\Gamma$ has a proper $k$-coloring such that the sizes of any two color classes differ by at most one. The equitable chromatic number $\chi_{=}(\Gamma)$ is the smallest integer $k$ such that $\Gamma$ is equitably $k$-colorable. Equitable coloring was introduced by W. Meyer in $1973$ due to scheduling problems [21]. Moreover, it was conjectured that every connected graph with maximum degree $\Delta$ has an equitable coloring with $\Delta$ or fewer colors, with the exceptions of complete graphs and odd cycles. A strengthened version [8] of the conjecture states that each such graph has an equitable coloring with exactly $\Delta$ colors, with one additional exception, a complete bipartite graph in which both sides of the bipartition have the same odd number of vertices. A survey on equitable colorings can be found in [20].

In Section 3.1 an equitable $(n-1)$-coloring based on efficient dominating sets in the Pancake graphs $P_{n},n>2$, is presented. Moreover, in Section 3.2 simple optimal equitable $4$-colorings for $P_{5},P_{6}$ and $P_{7}$ are described.

Let us note that any equitable coloring of $P_{n}$ with at most $n$ colors has the property that the sizes of all color classes are equal since every integer at most $n$ divides $n!$. Thus, we have a strongly equitable coloring [12].

Since equitable coloring is a proper coloring with an additional condition, the inequality $\chi(P_{n})\leqslant\chi_{=}(P_{n})$ holds for any $n\geqslant 2$. However, since all above optimal colorings are strongly equitable we have conjectured.

Our main result is given by the following theorem.

To prove this result we need more notation. Let $[n]=\{1,2,\ldots,n\}$. We consider a permutation $\pi=[\pi_{1}\pi_{2}\ldots\pi_{n}]$ written as a string in one-line notation, where $\pi_{i}=\pi(i)$ for any $i\in[n]$. For $K\subset[n]$, let $P_{n,K}$ be the induced subgraph of $P_{n}$ whose vertex set consists of all permutations $\pi$ with $\pi_{1}\in K$. By the symmetry of $P_{n}$, for any $k$-element subset $K$ of $[n]$, the induced subgraph $P_{n,K}$ is isomorphic to $P_{n,[k]}$, which is abbreviated to $P_{n,k}$.

We define a map $f_{n,k}:P_{n,k}\to P_{k}$ by removing the elements that are not in $[k]$. For example, for $n=5$ and $k=3$, the vertex $[14352]$ of $P_{5,3}$ is mapped to the vertex $[132]$ of $P_{3}$. It is clear that this mapping is a graph homomorphism. Note that $f_{n,k}$ is surjective, but not necessarily an isomorphism. In fact, $P_{n,k}$ is not even connected unless $k=n$ or $n=2$.

Since an $r$-coloring of a graph $\Gamma$ is equivalent to a graph homomorphism from $\Gamma$ to the complete graph $K_{r}$, this property implies that

Since $P_{n,k}$ always contains a subgraph isomorphic to $P_{k}$ (e. g. the subgraph of all vertices that end with $k+1,k+2,\ldots,n$) it even follows that $\chi(P_{n,k})=\chi(P_{k})$.

One more useful property says that all fibers $f_{n+1,n}:P_{n+1,n}\to P_{n}$ are of size $n$, which means that $\left|f_{n+1,n}^{-1}(v)\right|=n$ for every $v\in V(P_{n})$. Indeed, for any permutation of length $n$ one can insert $n+1$ at $n$ different positions: the first position is forbidden since the vertices of $P_{n+1,n}$ start with an element from $[n]$.

The following theorem immediately gives the general upper bound of (7) with taking into account $\chi(P_{9})=4$.

It was shown in Introduction that there are optimal colorings of the Pancake graphs found by computer experiments. Such computations do not provide us any structural insight. In this section we consider colorings of the Pancake graphs $P_{n},n\geqslant 3$, using their structural properties. More precisely, we present equitable colorings of $P_{n}$ in $(n-1)$ colors.

An equitable coloring is not the same as a perfect coloring for which the multiset of colors of all neighbors of a vertex depends only on its own color [11]. This type of coloring gives a partition known as an equitable partition [13] which are used in algebraic combinatorics, graph theory and coding theory. In coding theory such kind of partitions are known as perfect codes [1, 16]. Some general information about equitable partitions can be found in [2].

The notion of perfect codes was generalized to the Pancake graphs in a natural way in [9]. An independent set $D$ of vertices in a graph $\Gamma$ is an efficient dominating set (or $1$-perfect code) if each vertex not in $D$ is adjacent to exactly one vertex in $D$. There are $n$ efficient dominating sets in $P_{n}$ [9, 22] given by:

where $\pi_{k}\in[n]\backslash\{i\},\,k\in[n]\backslash\{1\},\,i\in[n]$. It is obvious that $|D_{i_{1}}\bigcap D_{i_{2}}|=\emptyset$, $i_{1},i_{2}\in[n],\ i_{1}\neq i_{2}$, which immediately gives a proper $n$-coloring. Moreover, this coloring is perfect and equitable.

To present a proper $(n-1)$-coloring of the Pancake graphs based on efficient dominating sets we need to define such sets for induced subgraphs $P_{n-1}$ of $P_{n}$.

Due to the hierarchical structure, for any $n\geqslant 3$ the graph $P_{n}$ has $n$ copies of $P_{n-1}(i)$ with the vertex set $V_{i}=\{[\pi_{1}\ldots\pi_{n-1}i]\}$, where $\pi_{k}\in[n]\backslash\{i\},k\in[n-1]$, $|V_{i}|=(n-1)!$. Any two copies $P_{n-1}(i),P_{n-1}(j),i\neq j$, are connected by $(n-2)!$ edges $\{[i\pi_{2}\ldots\pi_{n-1}j],\,[j\pi_{n-1}\ldots\pi_{2}i]\}$, where $[i\pi_{2}\ldots\pi_{n-1}j]r_{n}=[j\pi_{n-1}\ldots\pi_{2}i]$. Prefix–reversals $r_{j},2\leqslant j\leqslant n-1$, define internal edges in all $n$ copies $P_{n-1}(i)$, and the prefix–reversal $r_{n}$ defines external edges between copies.

Efficient dominating sets of $P_{n-1}(j),j\in[n]$, contain all permutations with the last element fixed to $j$ and the first element fixed [17], namely:

where $i,j\in[n],i\neq j$, $\pi_{k}\in[n]\backslash\{i,\,j\},\,k\in[n]\backslash\{1,n\}$. For any $i\in[n]$, the sets (10) and (11) are given by the following obvious relationship:

There are trivial examples of graphs for which Conjecture $1$ holds such as even cycles, bipartite graphs with equal parts. Any Cayley graph over the symmetric group generated by a set of transpositions gives a bipartite graph with two equal color classes. The statement holds for the Hamming graphs $H(d,q)$ whose (equitable) chromatic number is $q$. A regular graph with a Hoffman coloring always gives a strongly equitable coloring [3]. Hoffman’s lower bound is known as $\chi(\Gamma)\geqslant 1-\lambda_{1}/\lambda_{v}$, where $\lambda_{1}$ and $\lambda_{v}$ are the largest and the smallest eigenvalues of $\Gamma$. If equality holds, an optimal coloring of $\Gamma$ is called a Hoffman coloring.

The research work of the second author is supported by Mathematical Center in Akademgorodok, the agreement with Ministry of Science and High Education of the Russian Federation number 075-15-2019-1613. The authors thank Alexander Kostochka and Sergey Avgustinovich for useful discussions on equitable colorings.