Non-persistence of equality between chromatic polynomials and list-color functions

Abstract

For any graph $G$, let $P(G,k)$ and $P_{\ell}(G,k)$ denote the chromatic polynomial and the list-color function of $G$, respectively. It remains an open problem whether, for every graph $G$ and integer $k$, the equality $P(G,k)=P_{\ell}(G,k)>0$ implies that $P(G,k+1)=P_{\ell}(G,k+1)$ also holds. In this paper, we answer this question in the negative. For every integer $k\geq 3$, we construct an infinite family of graphs $G$ such that $P(G,k)=P_{\ell}(G,k)>0$ while $P(G,k+1)>P_{\ell}(G,k+1)$. Moreover, using this infinite family of graphs as attachment gadgets, we further show that any graph $H$ with $P(H,k)=P_{\ell}(H,k)>0$ can be developed into an infinite family of graphs $H^{\prime}$ with $P(H^{\prime},k)=P_{\ell}(H^{\prime},k)>0$ and $P(H^{\prime},k+1)>P_{\ell}(H^{\prime},k+1)$.

1 Introduction

In this article, we consider simple graphs only. For any graph $G$, let $V(G)$ and $E(G)$ be the vertex set and the edge set of $G$, respectively. For any non-empty subset $V_{0}$ of $V(G)$, let $G[V_{0}]$ denote the subgraph of $G$ induced by $V_{0}$. Denote by $\mathbb{N}$ the set of positive integers. For any $k,r\in\mathbb{N}$, let $[k]=\{1,\dots,k\}$ and $(k)_{r}=k(k-1)\cdots(k-r+1)$.

For any graph $G$, a proper coloring of $G$ is a mapping $\theta:V(G)\rightarrow\mathbb{N}$, such that $\theta(u)\neq\theta(v)$ for all $uv\in E(G)$. For any $k\in\mathbb{N}$, a proper $k$-coloring of $G$ is a proper coloring $\theta$ with $\theta(v)\in[k]$ for all $v\in V(G)$. Then the chromatic polynomial $P(G,k)$ of $G$ is a polynomial that counts the number of proper $k$-colorings of $G$ for each $k\in\mathbb{N}$. We say $G$ is uniquely $k$-colorable if $V(G)$ has a unique partition into $k$ nonempty independent sets, which implies that $P(G,k)=k!$. The chromatic polynomial was originally designed by Birkhoff in [5] as a tool to attack the Four-Color Conjecture, but later gained unique research significance because of its elegant properties. See [9, 10, 21, 22] for reference.

To generalize proper coloring, Vizing [24] and Erdős, Rubin and Taylor [13] independently introduced the notion of list-coloring. For any graph $G$, a list assignment $L$ of $G$ is a mapping from $V(G)$ to the power set of $\mathbb{N}$, and an $L$-coloring of $G$ is a proper coloring $\theta$ with $\theta(v)\in L(v)$ for all $v\in V(G)$. Denote the number of $L$-colorings of $G$ by $P(G,L)$. Then $G$ is called uniquely $L$-colorable if $P(G,L)=1$.

We say $L$ is a $k$-list assignment of $G$ if $|L(v)|=k$ holds for all $v\in V(G)$. Then the list-color function $P_{\ell}(G,k)$ of $G$ is defined to be the minimum value of $P(G,L)$ over all $k$-list assignments $L$ of $G$ for each $k\in\mathbb{N}$. Observe that there is a trivial $k$-list assignment $L^{*}$ of $G$ with $L^{*}(v)=[k]$ for all $v\in V(G)$, which leads to the equality $P(G,L^{*})=P(G,k)$. Then by the definition of the list-color function, for each $k\in\mathbb{N}$,

$$P_{\ell}(G,k)\leq P(G,k).$$ (1.1)

Note that the inequality of (1.1) can hold nontrivially, e.g., $P_{\ell}(K_{2,4},2)=0<2=P(K_{2,4},2)$. Consequently, Kostochka and Sidorenko [20] asked the question for which $k$ the equality of (1.1) holds. Very soon, Donner [12] answered this question by establishing a deletion-contraction formula for the list-color function.

Theorem 1 ([12]).

For any graph $G$, $P(G,k)=P_{\ell}(G,k)$ if $k$ is sufficiently large.

In fact, Theorem 1 reveals that the list-color function of every graph tends to be the same as its chromatic polynomial. It further indicates that $P_{\ell}(G,k)$ inherits all the nice properties of the chromatic polynomial when $k$ is sufficiently large. Following Theorem 1, the next question is naturally that for any graph $G$, what is the minimum integer $\tau(G)$ such that $P(G,k)=P_{\ell}(G,k)$ whenever $k\geq\tau(G)$. In 2009, Thomassen [23] gave the first answer regarding the order of the graph.

Theorem 2 ([23]).

For any graph $G$, $\tau(G)\leq|V(G)|^{10}+1$.

Later in 2017, Wang, Qian and Yan [25] improved Theorem 2 by developing a list-coloring version of Whitney’s broken cycle theorem.

Theorem 3 ([25]).

For any graph $G$, $\tau(G)\leq\frac{|E(G)|-1}{\log(1+\sqrt{2})}+1$.

Recently, by refining the techniques in [25], Dong and Zhang gave a better result in [11].

Theorem 4 ([11]).

For any graph $G$, $\tau(G)\leq|E(G)|-1$.

By the definition of $\tau(G)$, the authors of [12, 23, 25, 11] were required to verify the equality for all relatively large integers $k$, which is by no means trivial. This naturally raises the question of whether such a verification is always necessary. More specifically, the following question has recurred repeatedly over the past 10 years.

Question 5 ([7, 14, 8, 6, 15, 18, 4, 19]).

For all graphs $G$ and integers $k$, does the equality $P(G,k)=P_{\ell}(G,k)>0$ always imply $P(G,k+1)=P_{\ell}(G,k+1)$?

Question 5 is trivially true for $k=1$. For $k=2$, all graphs $G$ satisfying $P(G,2)=P_{\ell}(G,2)>0$ have been characterized in [3], and each such graph has the property that $P(G,k)=P_{\ell}(G,k)$ holds for all $k\in\mathbb{N}$. For $k\geq 3$, the question remains open since 2016.

Also, a question parallel to Question 5 concerning the DP-color function and the chromatic polynomial was posed in [18] and subsequently resolved in [8, 6] by constructing an infinite family of counterexamples.

In this paper, we show that the answer to Question 5 is also negative by constructing an infinite family of graphs as counterexamples.

Theorem 6.

For each integer $k\geq 3$, there are infinitely many graphs $G$ such that $P(G,k)=P_{\ell}(G,k)>0$ and $P(G,k+1)>P_{\ell}(G,k+1)$.

Moreover, using the graphs constructed in Theorem 6, we are able to provide an infinite family of counterexamples based on any graph $G$ with $P(G,k)=P_{\ell}(G,k)>0$ when $k\geq 3$.

Theorem 7.

For any integer $k\geq 3$ and graph $G$ with $P(G,k)=P_{\ell}(G,k)>0$, there exists an infinite set ${\mathcal{G}}^{np}(G)$ such that for each graph $G^{\prime}\in{\mathcal{G}}^{np}(G)$, $P(G^{\prime},k)=P_{\ell}(G^{\prime},k)>0$ but $P(G^{\prime},k+1)>P_{\ell}(G^{\prime},k+1)$.

Theorems 6 and 7 will be proven in Sections 2 and 3, respectively, with further discussion provided in Section 4.

2 Proof of Theorem 6

In this section, we prove Theorem 6 by providing for each integer $k\geq 3$ an infinite family of graphs $G_{k,t}$ with $P_{\ell}(G_{k,t},k)=P(G_{k,t},k)>0$ and $P_{\ell}(G_{k,t},k+1)<P(G_{k,t},k+1)$.

Let $k$ be a fixed integer with $k\geq 3$, and let $t\in\mathbb{N}$. Now we give the construction of $G_{k,t}$. Let

$$V(G_{k,t})=X_{k}\cup S\cup Y_{t},$$

where

$$\left\{\begin{aligned} &X_{k}=\{x_{i}:i\in[k]\},\\ &S=\{s_{i}:i\in[2]\},\\ &Y_{t}=\{y_{i,j}:i\in[4],\,j\in[t]\},\end{aligned}\right.$$

and

$$E(G_{k,t})= \{x_{i}x_{j}:i,j\in[k],i\neq j\}\cup\{s_{i}x_{j}:i\in[2],j\in[k],i\neq j\}$$

$$\cup\{y_{i,j}s_{r}:i\in[4],j\in[t],r\in[2]\}.$$

Figure 1: The graph $G_{3,2}$.

An example for $G_{3,2}$ is as shown in Figure 1. It is clear that $|V(G_{k,t})|=k+2+4t$, and $G_{k,t}[X_{k}]$ and all $G_{k,t}[X_{k}\cup\{s_{i}\}\setminus\{x_{i}\}]$ with $i\in[2]$ are isomorphic to $K_{k}$.

In the following, we shall prove that each $G_{k,t}$ is a graph satisfying Theorem 6 whenever $t$ is sufficiently large. We first show that $P_{\ell}(G_{k,t},k)=P(G_{k,t},k)$.

Lemma 8.

For any $k\geq 3$ and $t\in\mathbb{N}$,

$$P_{\ell}(G_{k,t},k)=P(G_{k,t},k)=k!(k-2)^{4t}.$$ (2.1)

Proof.

We shall prove that $P(G_{k,t},k)=k!(k-2)^{4t}$ by counting the number of proper $k$-colorings of $G_{k,t}$ in the order of $x_{1},x_{2},\dots,x_{k},s_{1},s_{2},y_{1,1},y_{1,2},\dots,y_{4,t}$. It is easy to see that we have $k-i+1$ available colors for each $x_{i}$. Since $k\geq 3$ and each $s_{i}$ is adjacent to $k-1$ vertices in $X_{k}$, we then have exactly one available color for each $s_{i}$, which is the color we assign to $x_{i}$. Moreover, in any proper $k$-coloring of $G_{k,t}$, the colors of all $x_{i}$ are pairwise distinct as all $x_{i}$ together forms a clique. Thus $s_{1}$ and $s_{2}$ have distinct colors, which leaves exactly $k-2$ available colors for each $y_{i,j}$. Hence $P(G_{k,t},k)=k!(k-2)^{4t}$.

Now it remains to show that $P_{\ell}(G_{k,t},k)=k!(k-2)^{4t}$. Since $P_{\ell}(G_{k,t},k)\leq P(G_{k,t},k)$, we need only to prove that $P(G_{k,t},L)\geq k!(k-2)^{4t}$ for all $k$-list assignments $L$ of $G_{k,t}$.

Let $L$ be any $k$-list assignment of $G_{k,t}$. We shall give a lower bound for the number of $L$-colorings in the order of $x_{1},x_{2},\dots,x_{k},s_{1},s_{2},y_{1,1},y_{1,2},\dots,y_{4,t}$. It is easy to see that we have at least $k-i+1$ available colors for each $x_{i}$, at least one available color for each $s_{i}$, and at least $k-2$ colors for each $y_{i,j}$, which implies $P(G_{k,t},L)\geq k!(k-2)^{4t}$. ∎

Next, we establish a lower bound for $P(G_{k,t},k+1)$.

Lemma 9.

For any $k\geq 3$ and $t\in\mathbb{N}$,

$$P(G_{k,t},k+1)\geq(k+1)!k^{4t}.$$ (2.2)

Proof.

We shall also prove by establishing a lower bound for the number of proper $(k+1)$-colorings of $G_{k,t}$ in the order of $s_{1},s_{2},x_{1},x_{2},\dots,x_{k},y_{1,1},y_{1,2},\dots,y_{4,t}$. We can first assign a same color to both $s_{1}$ and $s_{2}$, for which we have $k+1$ choices. Then we have $k-i+1$ available colors for each $x_{i}$, and $k$ available colors for each $y_{i,j}$. Hence (2.2) holds. ∎

In the following, we shall determine an upper bound for $P_{\ell}(G_{k,t},k+1)$ by finding a special ($k+1$)-list assignment for $G_{k,t}$.

Let $C,B_{1},B_{2}$ be pairwise disjoint sets where $C=\{c_{1},c_{2},\dots,c_{k-1}\}$, $B_{1}=\{b_{1,1},b_{1,2}\}$ and $B_{2}=\{b_{2,1},b_{2,2}\}$. Then let $D_{1}=\{b_{1,1},b_{2,1}\}$, $D_{2}=\{b_{1,1},b_{2,2}\}$, $D_{3}=\{b_{1,2},b_{2,1}\}$, and $D_{4}=\{b_{1,2},b_{2,2}\}$.

Now let $L$ be the $(k+1)$-list assignment of $G_{k,t}$ such that

$$\left\{\begin{aligned} &L(x_{i})=C\cup B_{1}~\text{for all}~i\in[k],\\ &L(s_{i})=C\cup B_{i}~\text{for all}~i\in[2],\\ &L(y_{i,j})=C\cup D_{i}~\text{for all}~i\in[4],\,j\in[t].\end{aligned}\right.$$ (2.3)

Then it is easy to see that $L$ is a ($k+1$)-list assignment, hence $P_{\ell}(G_{k,t},k+1)\leq P(G_{k,t},L).$ We shall further determine $P(G_{k,t},L)$ by the next two lemmas.

Lemma 10.

Let $L|_{X_{k}\cup S}$ be the $(k+1)$-list assignment of $G_{k,t}[X_{k}\cup S]$ which is the restriction of $L$ to $X_{k}\cup S$. Then for each $L|_{X_{k}\cup S}$-coloring $\theta$ of $G_{k,t}[X_{k}\cup S]$, the number of $L$-colorings $c$ of $G_{k,t}$ with $c|_{X_{k}\cup S}=\theta$ is

$$\left\{\begin{aligned} &k^{4t},&&\qquad\text{if }\theta(s_{1})=\theta(s_{2}),\\ &(k-1)^{4t},&&\qquad\text{if }\theta(s_{1})\neq\theta(s_{2})~\text{and}~\theta(s_{1}),\theta(s_{2})\in C,\\ &\bigl(k(k-1)\bigr)^{2t},&&\qquad\text{if }\theta(s_{1})\neq\theta(s_{2})~\text{and}~|\{\theta(s_{1}),\theta(s_{2})\}\cap C|=1,\\ &\bigl((k-1)k^{2}(k+1)\bigr)^{t},&&\qquad\text{if }\theta(s_{1})\neq\theta(s_{2})~\text{and}~|\{\theta(s_{1}),\theta(s_{2})\}\cap C|=0.\end{aligned}\right.$$

Proof.

Let $\theta$ be any $L|_{X_{k}\cup S}$-coloring of $G_{k,t}[X_{k}\cup S]$, and let $Z=\{\theta(s_{i}):i\in[2]\}$. Then $1\leq|Z|\leq 2$. To extend $\theta$ into an $L$-coloring of $G_{k,t}$, it remains to assign colors to the vertices in $Y_{t}$. For each $y_{i,j}\in Y_{t}$, we have $|(C\cup D_{i})\setminus Z|$ available colors to choose. Then the number of $L$-colorings of $G_{k,t}$ extending $\theta$ is

$$\left(\prod_{i=1}^{4}\left|(C\cup D_{i})\setminus Z\right|\right)^{t}.$$ (2.4)

If $|Z|=1$ (i.e., $\theta(s_{1})=\theta(s_{2})$), then $\theta(s_{1})=\theta(s_{2})=c_{s}\in C$ for some $s\in[k-1]$. Thus $|(C\cup D_{i})\setminus Z|=k$ for all $i\in[4]$, implying that

$$\prod_{i=1}^{4}|(C\cup D_{i})\setminus Z|=k^{4}.$$ (2.5)

By (2.4), the result holds when $\theta(s_{1})=\theta(s_{2})$.

Now consider the case $|Z|=2$ (i.e., $\theta(s_{1})\neq\theta(s_{2})$.) Let $q=|Z\cap C|$ and $p=|Z|-q$. Then $p$ is the number of colors in $Z\cap(B_{1}\cup B_{2})$. Moreover, either $(q,p)=(2,0)$, or $(q,p)=(1,1)$, or $(q,p)=(0,2)$. We shall analyze each of the three cases below.

Case 1: $(q,p)=(2,0)$.

In this case, $\theta(s_{1})\neq\theta(s_{2})$ and $\theta(s_{1}),\theta(s_{2})\in C$. Then $\left|(C\cup D_{i})\setminus Z\right|=k-1$ for all $i\in[4]$, implying that

$$\prod_{i=1}^{4}|(C\cup D_{i})\setminus Z|=(k-1)^{4}.$$ (2.6)

Case 2: $(q,p)=(1,1)$.

In this case, $\theta(s_{1})\neq\theta(s_{2})$ and $|\{\theta(s_{1}),\theta(s_{2})\}\cap C|=1$. Without loss of generality, assume that $Z=\{c_{1},b_{1,1}\}$. Then,

$$\left\{\begin{array}[]{l}|(C\cup D_{1})\setminus Z|=|(C\cup D_{2})\setminus Z|=k-1;\\ |(C\cup D_{3})\setminus Z|=|(C\cup D_{4})\setminus Z|=k.\end{array}\right.$$

Thus

$$\prod_{i=1}^{4}|(C\cup D_{i})\setminus Z|=k^{2}(k-1)^{2}.$$ (2.9)

Case 3: $(q,p)=(0,2)$.

In this case, $\theta(s_{1})\neq\theta(s_{2})$ and $|\{\theta(s_{1}),\theta(s_{2})\}\cap C|=0$. Without loss of generality, assume that $Z=\{b_{1,1},b_{2,1}\}$. Then,

$$\left\{\begin{array}[]{l}|(C\cup D_{1})\setminus Z|=k-1;\\ |(C\cup D_{2})\setminus Z|=|(C\cup D_{3})\setminus Z|=k;\\ |(C\cup D_{4})\setminus Z|=k+1.\end{array}\right.$$

Thus,

$$\prod_{i=1}^{4}|(C\cup D_{i})\setminus Z|=(k-1)k^{2}(k+1).$$ (2.13)

By (2.4) and the results in the three cases above, the lemma is proven. ∎

Lemma 11.

For any $k\geq 3$ and $t\in\mathbb{N}$, let $L$ be the $(k+1)$-list assignment of $G_{k,t}$ defined in (2.3). Then

$$P(G_{k,t},L)= (k-1)k!k^{4t}+3(k-2)(k-1)!(k-1)^{4t+1}+\big(4(k-1)k!$$

$$+6(k-1)(k-1)!\big)\bigl(k(k-1)\bigr)^{2t}+8k!\bigl((k-1)k^{2}(k+1)\bigr)^{t}.$$ (2.14)

Proof.

We shall prove by analyzing all possible $L|_{X_{k}\cup S}$-colorings of $G_{k,t}[X_{k}\cup S]$ and combine them with Lemma 10.

We first count the number of $L|_{X_{k}\cup S}$-colorings $\theta$ of $G_{k,t}[X_{k}\cup S]$ such that $\theta(s_{1})=\theta(s_{2})$. Suppose $\theta(s_{1})=\theta(s_{2})=c$. Then $c\in C$ and $c$ can be any one of the $k-1$ colors in $C$. According to the construction of $G_{k,t}$, each vertex in $X_{k}$ is adjacent to at least one vertex in $S$, which implies that no vertex in $X_{k}$ can receive color $c$. Therefore, all vertices in $X_{k}$ have all colors in $(C\setminus\{c\})\cup B_{1}$ to use, where $|(C\setminus\{c\})\cup B_{1}|=k$. Since $X_{k}$ is a clique of size $k$, we have exactly $k!$ ways to assign colors to $X_{k}$. Thus in this case, the number of $L|_{X_{k}\cup S}$-colorings $\theta$ of $G_{k,t}[X_{k}\cup S]$ such that $\theta(s_{1})=\theta(s_{2})$ is $(k-1)k!$. Then by Lemma 10, the number of $L$-colorings $\theta^{\prime}$ of $G_{k,t}$ such that $\theta^{\prime}(s_{1})=\theta^{\prime}(s_{2})$ is $(k-1)k!k^{4t}$.

For the remaining $L|_{X_{k}\cup S}$-colorings $\theta$ of $G_{k,t}[X_{k}\cup S]$, $\theta(s_{1})\neq\theta(s_{2})$ and we shall discuss each of the three cases below.

Case 1: $\theta(s_{1})\neq\theta(s_{2})$ and $\theta(s_{1}),\theta(s_{2})\in C$.

For this case, we count by coloring the vertices in the order $s_{1},s_{2},x_{3},x_{4},\dots,x_{k},x_{1},x_{2}$. There are $(k-1)(k-2)$ ways to color $s_{1}$ and $s_{2}$, followed by $(k-1)(k-2)\cdots 2$ ways to color $x_{3},x_{4},\dots,x_{k}$, which leaves exactly one remaining color in $C\cup B_{1}$, say $q$. We may then assign to $(x_{1},x_{2})$ any of the three ordered pairs $(\theta(s_{1}),q)$, $(q,\theta(s_{2}))$, and $(\theta(s_{1}),\theta(s_{2}))$. Hence, the number of such colorings is $3(k-1)(k-2)(k-1)!$.

Case 2: $\theta(s_{1})\neq\theta(s_{2})$ and $|\{\theta(s_{1}),\theta(s_{2})\}\cap C|=1$.

Suppose $\theta(s_{1})\in C$ and $\theta(s_{2})\in B_{2}$ first. Then we count the colorings in the order $s_{1},s_{2},x_{2},x_{3},\dots,x_{k},x_{1}$. There are $2(k-1)$ ways to color $s_{1}$ and $s_{2}$, followed by $k(k-1)\cdots 2$ ways to color $x_{2},x_{3},\dots,x_{k}$. This leaves exactly one remaining color in $C\cup B_{1}$, say $q$. We may then assign the color $q$ or $\theta(s_{1})$ to $x_{1}$. Hence, the number of such colorings is $4(k-1)k!$.

Then we suppose $\theta(s_{2})\in C$ and $\theta(s_{1})\in B_{1}$. We count the colorings in the order $s_{1},s_{2},x_{3},x_{4},\dots,x_{k},x_{1},x_{2}$. There are $2(k-1)$ ways to color $s_{1}$ and $s_{2}$, followed by $(k-1)(k-2)\cdots 2$ ways to color $x_{3},x_{4},\dots,x_{k}$, which leaves exactly one remaining color in $C\cup B_{1}$, say $q$. We may then assign to $(x_{1},x_{2})$ any of the three ordered pairs $(\theta(s_{1}),q)$, $(q,\theta(s_{2}))$, and $(\theta(s_{1}),\theta(s_{2}))$. Hence, the number of such colorings is $6(k-1)(k-1)!$.

Case 3: $\theta(s_{1})\neq\theta(s_{2})$ and $|\{\theta(s_{1}),\theta(s_{2})\}\cap C|=0$.

For this case, we count the colorings in the order $s_{1},s_{2},x_{2},x_{3},\dots,x_{k},x_{1}$. There are $2\times 2$ ways to color $s_{1}$ and $s_{2}$, followed by $k(k-1)\cdots 2$ ways to color $x_{2},x_{3},\dots,x_{k}$, which leaves exactly one remaining color in $C\cup B_{1}$, say $q$. We may then assign the color $q$ or $\theta(s_{1})$ to $x_{1}$. Hence, the number of such colorings is $8k!$.

By Lemma 10 and the three cases above, we have $3(k-1)(k-2)(k-1)!(k-1)^{4t}+\big(4(k-1)k!+6(k-1)(k-1)!\big)\bigl(k(k-1)\bigr)^{2t}+8k!\bigl((k-1)k^{2}(k+1)\bigr)^{t}$ $L$-colorings $\theta^{\prime}$ of $G_{k,t}$ such that $\theta^{\prime}(s_{1})\neq\theta^{\prime}(s_{2})$.

Hence the result is proven. ∎

Now we are able to show that $P_{\ell}(G_{k,t},k+1)<P(G_{k,t},k+1)$ when $t$ is sufficiently large.

Proposition 12.

For any integer $k\geq 3$, there is an integer $t_{0}=t_{0}(k)$ such that $P_{\ell}(G_{k,t},k+1)<P(G_{k,t},k+1)$ holds for all $t\geq t_{0}$.

Proof.

Let $L$ be the $(k+1)$-list assignment of $G_{k,t}$ defined in (2.3). Then by Lemmas 9 and 11,

$$P(G_{k,t},k+1)-P_{\ell}(G_{k,t},k+1)$$

$$\geq P(G_{k,t},k+1)-P(G_{k,t},L)$$

$$\geq (k+1)!k^{4t}-(k-1)k!k^{4t}-3(k-2)(k-1)!(k-1)^{4t+1}-\big(4(k-1)k!$$

$$+6(k-1)(k-1)!\big)\bigl(k(k-1)\bigr)^{2t}-8k!\bigl((k-1)k^{2}(k+1)\bigr)^{t}.$$ (2.15)

Then we need only to show that for all sufficiently large integers $t$,

$$(k+1)!k^{4t}> (k-1)k!k^{4t}-3(k-2)(k-1)!(k-1)^{4t+1}+(4(k-1)k!$$

$$+6(k-1)(k-1)!)\bigl(k(k-1)\bigr)^{2t}+8k!\bigl((k-1)k^{2}(k+1)\bigr)^{t}.$$ (2.16)

Let $r=1-1/k,s=1-1/k^{2},$ and

$$F_{k}(t)=\frac{3(k-1)(k-2)}{2k}r^{4t}+\frac{(2k+3)(k-1)}{k}r^{2t}+4s^{t}.$$ (2.17)

Then it can be easily verified that (2) holds if and only if $F_{k}(t)<1$. Let $t_{0}$ be the integer defined below:

$$t_{0}=\left\lceil k^{2}\log\left(\frac{7k+1}{2}\right)\right\rceil.$$

In the following, we shall prove that $F_{k}(t)<1$ whenever $t\geq t_{0}$.

Since $k\geq 3$, we have

$$r^{2}=\left(1-\frac{1}{k}\right)^{2}<1-\frac{1}{k^{2}}=s,$$

implying that $r^{4t}<r^{2t}<s^{t}$. Then for any integer $t\geq t_{0}$,

$$F_{k}(t)< \left(\frac{3(k-1)(k-2)}{2k}+\frac{(2k+3)(k-1)}{k}+4\right)s^{t}$$

$$= \frac{7k+1}{2}(1-\frac{1}{k^{2}})^{t}$$

$$< \frac{7k+1}{2}\exp(-t/k^{2})$$

$$\leq \frac{7k+1}{2}\exp\left(-\log\left(\frac{7k+1}{2}\right)\right)$$

$$=1.$$ (2.18)

Hence the result holds. ∎

By Lemma 8 and Proposition 12, Theorem 6 is proven.

3 Proof of Theorem 7

In this section, we prove Theorem 7 after introducing an elementary property of the list-color function.

Let $r\in\mathbb{N}$. For any pair of vertex-disjoint graphs $G$ and $H$ that each contains a copy of $K_{r}$, let $G\cup_{r}H$ denote a graph obtained by identifying a copy of $K_{r}$ in $G$ with a copy of $K_{r}$ in $H$. It is well known that for any $r,k\in\mathbb{N}$,

$$P(G\cup_{r}H,k)=\frac{P(G,k)P(H,k)}{(k)_{r}}.$$ (3.1)

However, for the list-color function, the analogous identity does not hold in general. For example, $P_{\ell}(C_{4},2)=2$ while $P_{\ell}(C_{4}\cup_{1}C_{4},2)=0$.

On the other hand, for the DP-color function, it is known that

$$P_{DP}(G\cup_{r}H,k)\leq\frac{P_{DP}(G,k)P_{DP}(H,k)}{(k)_{r}}$$

holds for $r=1,2$ and all $k\in\mathbb{N}$, whereas a counterexample exists for $r=3$ and $k=4$ [4, 16]. This naturally raises the question of whether for the list-color function,

$$P_{\ell}(G\cup_{r}H,k)\leq\frac{P_{\ell}(G,k)P_{\ell}(H,k)}{(k)_{r}}$$ (3.2)

holds for all $r,k\in\mathbb{N}$.

In fact, (3.2) is not true even for $r=2$. To see this, consider the graph $K_{2,12}\cup_{2}K_{3}$. It is clear that for any 3-list assignment $L$ of $K_{2,12}\cup_{2}K_{3}$, an $L|_{V(K_{2,12})}$-coloring of $K_{2,12}$ naturally extends to an $L$-coloring of $K_{2,12}\cup_{2}K_{3}$, implying that $P_{\ell}(K_{2,12}\cup_{2}K_{3},3)\geq P_{\ell}(K_{2,12},3)$. Moreover, results in [14] show that every $3$-list assignment $L$ of $K_{2,12}$ satisfying $P(K_{2,12},L)=P_{\ell}(K_{2,12},3)$ has the property that $L(u)\neq L(v)$ for every $uv\in E(K_{2,12})$. Then for any 3-list assignment $L$ of $K_{2,12}\cup_{2}K_{3}$ such that $P(K_{2,12},L|_{V(K_{2,12})})=P_{\ell}(K_{2,12},3)$, an $L|_{V(K_{2,12})}$-coloring of $K_{2,12}$ does not extend uniquely to $L$-colorings of $K_{2,12}\cup_{2}K_{3}$, implying that $P_{\ell}(K_{2,12}\cup_{2}K_{3},3)>P_{\ell}(K_{2,12},3)$. Therefore

$$P_{\ell}(K_{2,12}\cup_{2}K_{3},3)>P_{\ell}(K_{2,12},3)=\frac{P_{\ell}(K_{2,12},3)P_{\ell}(K_{3},3)}{3\cdot 2},$$

which provides a counterexample to (3.2) when $r=2$.

Thus, we restrict our attention to the case $r=1$, as follows.

Lemma 13.

For any $k\in\mathbb{N}$ and any pair of vertex-disjoint graphs $G$ and $H$,

$$P_{\ell}(G\cup_{1}H,k)\leq\frac{P_{\ell}(G,k)P_{\ell}(H,k)}{k}.$$ (3.3)

Proof.

Suppose $G\cup_{1}H$ is obtained by identifying $u$ in $V(G)$ and $v$ in $V(H)$.

Let $L_{G}$ and $L_{H}$ be a $k$-list assignment of $G$ and $H$, respectively, such that

$$P(G,L_{G})=P_{\ell}(G,k)\qquad\text{and}\qquad P(H,L_{H})=P_{\ell}(H,k).$$

Moreover, we assume without loss of generality that

$$L_{G}(u)=\{1,\dots,k\}\qquad\text{and}\qquad L_{H}(v)=\{1,\dots,k\}.$$

In the following, we shall construct a $k$-list assignment $L$ of $G\cup_{1}H$ such that

$$P(G\cup_{1}H,L)\leq\frac{P(G,L_{G})P(H,L_{H})}{k}=\frac{P_{\ell}(G,k)P_{\ell}(H,k)}{k}.$$ (3.4)

For $i=1,2,\dots,k$, let $g_{i}$ be the number of $L_{G}$-colorings $\theta$ such that $\theta(u)=i$, and let $h_{i}$ be the number of $L_{H}$-colorings $\varphi$ such that $\varphi(v)=i$. Then

$$\sum_{i=1}^{k}g_{i}=P(G,L_{G})\qquad\text{and}\qquad\sum_{j=1}^{k}h_{j}=P(H,L_{H}).$$

For each permutation $\sigma\in S_{k}$, set $S_{\sigma}=\sum_{i=1}^{k}g_{i}h_{\sigma(i)}.$ Then

$$\frac{1}{k!}\sum_{\sigma\in S_{k}}S_{\sigma} =\ \frac{1}{k!}\sum_{\sigma\in S_{k}}\left(\sum_{i=1}^{k}g_{i}h_{\sigma(i)}\right)$$

$$=\sum_{i=1}^{k}g_{i}\left(\frac{1}{k!}\sum_{\sigma\in S_{k}}h_{\sigma(i)}\right)$$

$$=\sum_{i=1}^{k}g_{i}\left(\frac{(k-1)!}{k!}\sum_{j=1}^{k}h_{j}\right)$$

$$=\frac{1}{k}\left(\sum_{i=1}^{k}g_{i}\right)\left(\sum_{j=1}^{k}h_{j}\right)$$

$$=\frac{P(G,L_{G})P(H,L_{H})}{k}.$$ (3.5)

Since $|S_{k}|=k!$, (3) indicates a permutation $\sigma_{0}\in S_{k}$ such that

$$S_{\sigma_{0}}\leq\frac{P(G,L_{G})P(H,L_{H})}{k}=\frac{P_{\ell}(G,k)P_{\ell}(H,k)}{k}.$$ (3.6)

Let $f$ be the mapping from $\mathbb{N}$ to $\mathbb{N}$ such that $f(\sigma_{0}(i))=i$ for all $i\in[k]$ and $f(i)=i$ for $i\geq k+1$.

Now we shall construct a special $k$-list assignment $L$ of $G\cup_{1}H$, where

$$\left\{\begin{aligned} &L(x)=L_{G}(x)~\text{for all}~x\in V(G),\\ &L(y)=\{f(i):i\in L_{H}(y)\}~\text{for all}~y\in V(H)\setminus\{v\}.\end{aligned}\right.$$

Then it is clear by (3.6) that

$$P_{\ell}(G\cup_{1}H,k)\leq P(G\cup_{1}H,L)=\sum_{i=1}^{k}g_{i}h_{\sigma_{0}(i)}=S_{\sigma_{0}}\leq\frac{P_{\ell}(G,k)P_{\ell}(H,k)}{k}.$$ (3.7)

∎

Now we give the proof of Theorem 7.

Proof of Theorem 7. For any graph $G$ with $P(G,k)=P_{\ell}(G,k)>0$, let $H_{k,t}$ be a graph obtained by identifying one vertex of $G$ and $x_{k}$ of $G_{k,t}$. We shall show that $P(H_{k,t},k)=P_{\ell}(H_{k,t},k)>0$ and $P(H_{k,t},k+1)>P_{\ell}(H_{k,t},k+1)$ whenever $t$ is sufficiently large.

Recall that $P(G_{k,t},k+1)>P_{\ell}(G_{k,t},k+1)$ whenever $t$ is sufficiently large. Then by (3.1) and (3.3),

$$P_{\ell}(H_{k,t},k+1) \leq\frac{P_{\ell}(G,k+1)P_{\ell}(G_{k,t},k+1)}{k+1}$$

$$<\frac{P(G,k+1)P(G_{k,t},k+1)}{k+1}$$

$$=P(H_{k,t},k+1).$$ (3.8)

Thus it remains to show that $P(H_{k,t},k)=P_{\ell}(H_{k,t},k)>0$.

By Lemma 8 and (3.1), we have

$$P(H_{k,t},k)=\frac{P(G,k)P(G_{k,t},k)}{k}=(k-1)!(k-2)^{4t}P(G,k)>0.$$ (3.9)

We next consider $P_{\ell}(H_{k,t},k)$. Let $L$ be a $k$-list assignment of $H_{k,t}$ such that $P_{\ell}(H_{k,t},k)=P(H_{k,t},L)$. Then there are at least $P_{\ell}(G,k)$ $L|_{V(G)}$-colorings of $G$. Moreover, each of them can be extended to at least $(k-1)!(k-2)^{4t}$ $L$-colorings of $H_{k,t}$ by considering in the order $x_{1},\ldots,x_{k-1},s_{1},s_{2},y_{1,1},\dots,y_{4,t}$. Thus

$$P_{\ell}(H_{k,t},k)=P(H_{k,t},L)\geq(k-1)!(k-2)^{4t}P_{\ell}(G,k)=(k-1)!(k-2)^{4t}P(G,k).$$ (3.10)

Hence $P_{\ell}(H_{k,t},k)=P(H_{k,t},k)>0$ follows from (3.9) and (3.10). ∎

4 Concluding Remarks

Although all counterexamples constructed in the proofs of Theorems 6 and 7 for each integer $k\geq 3$ contain copies of $K_{k}$, we shall show in this section that the presence of $K_{k}$ is not essential.

Figure 2: The graph $Q$.

Let $Q$ be the graph as shown in Figure 2. $Q$ was constructed in [2] as an example that is uniquely 3-colorable but contains no $K_{3}$. Therefore, $P(Q,3)=3!=6$. Moreover, $P_{\ell}(Q,3)$ can be determined by the following theorem.

Theorem 14 ([1]).

Let $G$ be a graph on a set $V=\{v_{1},v_{2},\dots,v_{n}\}$ of $n\geq 1$ vertices. For $1\leq i\leq n$, let $L_{v_{i}}$ be a list of $d_{i}+1$ colors where $d_{i}\geq 0$ is a given integer. Suppose that $G$ is uniquely $L$-colorable and $d_{1}+d_{2}+\cdots+d_{n}=m$, where $m$ is the size of $G$. Then $G$ has $f$-colorings for every list assignment $f$ of $G$ provided $f(v_{i})=d_{i}+1$ for $1\leq i\leq n$.

Proposition 15.

$P_{\ell}(Q,3)=P(Q,3)=6$.

Proof.

Since $P_{\ell}(Q,3)\leq P(Q,3)=6$, we need only to show that $Q$ has at least 6 $L$-colorings for all 3-list assignments $L$ of $Q$.

Assume that $u,v$ are two vertices from different partition sets in the unique partition of $V(Q)$ into three independent sets. Let $L_{0}$ be a list assignment of $G$ such that $L_{0}(u)=\{1\},L_{0}(v)=\{1,2\}$, and $L_{0}(w)=\{1,2,3\}$ for all $w\in V(Q)\setminus\{u,v\}$. Then $Q$ is uniquely $L_{0}$-colorable as $Q$ is uniquely 3-colorable. Also, note that $|V(Q)|=24$ and $|E(Q)|=45$. Then $L_{0}$ satisfies the requirements of Theorem 14 as $0+1+2\times 22=45$, which implies that $G$ has $L$-colorings for every list assignment $L$ of $G$ provided $|L(u)|=1$, $|L(v)|=2$, and $|L(w)|=3$ for all $w\in V(Q)\setminus\{u,v\}$.

Now we consider any 3-list assignment $L$ of $Q$. Assume that $L(u)=\{1,2,3\}$ and $L(v)=\{a,b,c\}$. For each $i\in[3]$, let $L_{i}(u)=\{i\},L_{i}(v)=\{a,b\}$, and $L_{i}(w)=L(w)$ for all $w\in V(Q)\setminus\{u,v\}$. Then by Theorem 14, $Q$ has an $L_{i}$-coloring $\theta_{i}$, which is also an $L$-coloring. Further, let $L_{i}^{\prime}(u)=\{i\},L_{i}^{\prime}(v)=L(v)\setminus\{\theta_{i}(v)\}$, and $L_{i}^{\prime}(w)=L(w)$ for all $w\in V(Q)\setminus\{u,v\}$. We again obtain by Theorem 14 an $L_{i}^{\prime}$-coloring $\theta_{i}^{\prime}$ for each $i\in[3]$, which is also an $L$-coloring and is different from $\theta_{i}$ as $\theta_{i}(v)\neq\theta_{i}^{\prime}(v)$. Since $\theta_{i}(u)=\theta_{i}^{\prime}(u)$ are pairwise distinct for all $i\in[3]$, we now have six $L$-colorings of $Q$, which completes the proof. ∎

For any pair of vertex-disjoint graphs $G$ and $H$, let $G\vee H$ be the join of $G$ and $H$, i.e., $V(G\vee H)=V(G)\cup V(H)$ and $E(G\vee H)=E(G)\cup E(H)\cup\{uv:u\in V(G),v\in V(H)\}$. Since $Q$ contains no $K_{3}$, $Q\vee K_{k-3}$ contains no $K_{k}$. We shall show that $Q\vee K_{k-3}$ is an ideal replacement for $G_{k,t}[X_{k}\cup S]$ after proving the next proposition.

Lemma 16 ([17]).

For any graph $G$ and $n,k\in N$,

$$P_{\ell}(G,k-n)P(K_{n},k)\leq P_{\ell}(G\vee K_{n},k)\leq P(G\vee K_{n},k)=P(G,k-n)P(K_{n},k).$$

Proposition 17.

For any $k\geq 3$, $P_{\ell}(Q\vee K_{k-3},k)=P(Q\vee K_{k-3},k)=k!$.

Proof.

By Lemma 16, we have

$$P_{\ell}(Q,3)P(K_{k-3},k)\leq P_{\ell}(Q\vee K_{k-3},k)\leq P(Q\vee K_{k-3},k)=P(Q,3)P(K_{k-3},k).$$

Then by Proposition 15, the first equality holds.

The second equality is then obvious as $Q\vee K_{k-3}$ is uniquely $k$-colorable. ∎

Observe that $G_{k,t}[X_{k}\cup S]$ is uniquely $k$-colorable, where $x_{1},x_{2},\dots,x_{k}$ are in different color classes while $x_{i}$ and $s_{i}$ are in the same color class for $i\in[2]$, and $s_{1},s_{2}$ are nonadjacent. We shall see that a similar structure also exists in $Q\vee K_{k-3}$.

Let $x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime},s_{1}^{\prime},s_{2}^{\prime}$ be the vertices in $Q$ as shown in Figure 2, and let $V(K_{k-3})=\{x_{4}^{\prime},x_{5}^{\prime},\dots,x_{k}^{\prime}\}$. Then $Q\vee K_{k-3}$ is uniquely $k$-colorable, where $x_{1}^{\prime},x_{2}^{\prime},\dots,x_{k}^{\prime}$ are in different color classes while $x_{i}^{\prime}$ and $s_{i}^{\prime}$ are in the same color class for $i\in[2]$, and $s_{1}^{\prime},s_{2}^{\prime}$ are nonadjacent. Thus replacing $G_{k,t}[X\cup S]$ and $x_{1},x_{2},\dots,x_{k},s_{1},s_{2}$ in $G_{k,t}$ with $Q\vee K_{k-3}$ and $x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime},\dots,x_{k}^{\prime},s_{1}^{\prime},s_{2}^{\prime}$ provides us another infinite family of graphs supporting Theorem 6 that contains no $K_{k}$. The proof can be carried out based on Proposition 17 by establishing a series of results analogous to Lemmas 8, 9, 10, and 11, which together yield Proposition 12.

However, it remains unclear for which graphs the agreement of the chromatic polynomial and the list-color function always persists.

Question 18.

Characterize the graphs $G$ such that for all integers $k$, $P(G,k)=P_{\ell}(G,k)>0$ implies $P(G,k+1)=P_{\ell}(G,k+1).$