Bad list assignments for non-$k$-choosable $k$-chromatic graphs with $2k+2$-vertices

A proper colouring of a graph $G$ is a mapping $f:V(G)\rightarrow\mathbb{N}$ such that $f(u)\neq f(v)$ for every edge $uv$ of $E(G)$. The chromatic number $\chi(G)$ of $G$ is the minimum $k$ such that $G$ has a proper $k$-colouring, i.e., a proper colouring $f$ with $|f(V(G))|\leq k$. A $k$-list assignment of a graph $G$ is a mapping $L$ which assigns to each vertex $v$ a set $L(v)$ of at least $k$ permissible colours, i.e., $|L(v)|\geq k$. An $L$-colouring of $G$ is a proper colouring of $G$ which colours each vertex $v$ with a colour from $L(v)$. We say that $G$ is $L$-colourable if there exists an $L$-colouring of $G$, and $G$ is $k$-choosable if $G$ is $L$-colourable for each $k$-list assignment $L$ of $G$. More generally, for a function $f:V(G)\to\mathbb{N}$, an $f$-list assignment of $G$ is a list assignment $L$ with $|L(v)|\geq f(v)$ for all $v\in V(G)$. We say $G$ is $f$-choosable if $G$ is $L$-colourable for every $f$-list assignment $L$ of $G$. The choice number ${\rm ch}(G)$ of $G$ is the minimum $k$ for which $G$ is $k$-choosable. List colouring of graphs was introduced independently by Erdős-Rubin-Taylor [3] and Vizing [16], and has been studied extensively in the literature (cf. [15]).

It follows from the definitions that $\chi(G)\leq ch(G)$ for any graph $G$, and it is well-known [3] that bipartite graphs can have arbitrarily large choice number. A graph $G$ is called chromatic-choosable if $\chi(G)=ch(G)$. Some families of graphs are conjectured or proven to be chromatic-choosable. For example, the list colouring conjecture, proposed independently by Albertson and Collins, Gupta, and Vizing (see [6]), asserts that line graphs are chromatic-choosable. This conjecture was proved for bipartite graphs [4], for complete graphs of odd order [6] and for complete graphs of order $p+1$ for primes $p$ [14]. Also it was conjectured by Ohba [12] and proved by Noel, Reed and Wu [11] that $k$-chromatic graphs $G$ with $|V(G)|\leq 2\chi(G)+1$ are chromatic-choosable. We shall refer this result as Noel-Reed-Wu Theorem in the remainder of this paper.

We denote by $K_{k_{1}\star n_{1},k_{2}\star n_{2},\ldots,k_{q}\star n_{q}}$ the complete multi-partite graph with $n_{i}$ partite sets of size $k_{i}$, for $i=1,2,\ldots,q$. If $n_{j}=1$, then the number $n_{j}$ is omitted from the notation. For example, $K_{4,2\star(k-1)}$ is the complete $k$-partite graph with one partite set of size $4$, and $k-1$ partite sets of size $2$. It was proved in [2] that if $k$ is an even integer, then $K_{4,2\star(k-1)}$ and $K_{3\star(k/2+1),1\star(k/2-1)}$ are not $k$-choosable.

So Noel-Reed-Wu Theorem is tight, when $\chi(G)$ is even. Noel [9] conjectured that if $k$ is odd, then the bound is not tight, i.e., all $k$-chromatic graphs with $2k+2$ vertices are $k$-choosable. This conjecture was confirmed in [17], where the following result was proved.

Thus any $k$-chromatic non-$k$-choosable graph with $2k+2$ vertices is a spanning subgraph of $G=K_{4,2\star(k-1)}$ or $G=K_{3\star(k/2+1),1\star(k/2-1)}$, and $k$ is an even integer.

For $G=K_{4,2\star(k-1)}$ or $G=K_{3\star(k/2+1),1\star(k/2-1)}$, a bad list assignment of $G$ is a $k$-list assignment $L$ of $G$ such that $G$ is not $L$-colourable. Bad list assignments for $G=K_{4,2\star(k-1)}$ were characterized in [2]. We shall give a simpler proof of this result. Then we characterize bad list assignments for $G=K_{3\star(k/2+1),1\star(k/2-1)}$: If $k\geq 4$, then a $k$-list assignment $L$ of $G=K_{3\star(k/2+1),1\star(k/2-1)}$ is bad if and only if

• •

  $|\bigcup_{v\in V(G)}L(v)|=\frac{3}{2}k$,

• •

  for each $3$-part $P$ of $G$, $\bigcap_{v\in P}L(v)=\emptyset$.

If $k=2$, then a $k$-list assignment $L$ of $K_{3,3}$ is bad if and only if it is isomorphic to one of the list assignments in Figure 1.

As a consequence, we characterize all non-$k$-choosable $k$-chromatic graphs with $2k+2$ vertices.

Assume that $G=K_{4,2\star(k-1)}$ or $G=K_{3\star(k/2+1),1\star(k/2-1)}$, and $L$ is a bad $k$-list assignment of $G$.

For a subset $X$ of $V(G)$, let

$$L(X)=\bigcup_{v\in X}L(v).$$

Let $C=L(V(G))$. It was proved in [7] that if $L$ is a bad list assignment of $G$ with $|C|$ minimum, then $|C|<|V(G)|$. We observe that by the same argument, without assuming the minimality of $|C|$, the conclusion still holds for bad list assignments of $G$. Indeed, if $|C|\geq|V(G)|$, then we let $X$ be a maximum subset of $V(G)$ with $|X|>|L(X)|$ (it is possible that $X=\emptyset$). As $|V(G)|\leq|C|$, we know that $X\neq V(G)$. Thus $|X|\leq 2k+1$ and by Noel-Wu-Reed Theorem, we have $G[X]$ is $L$-colourable. The maximality of $X$ implies that for any $Y\subseteq V(G)-X$, $|L(Y)-L(X)|\geq|Y|$. By Hall ’s Theorem, there is an injective colouring $f$ of $G-X$ such that for each vertex $v$, $f(v)\in L(v)-L(X)$. Hence $G$ is $L$-colourable.

Each partite set of $G$ is called a part of $G$, and a part of size $i$ (respectively, at least $i$ or at most $i$) is called a $i$-part (respectively,$i^{+}$-part, or $i^{-}$-part).

For each $3^{+}$-part $P$ of $G$, let

$$t_{P}=\max\{|L(u)\cap L(v)|:u\neq v,u,v\in P\}.$$

For $c\in C$ and $C^{\prime}\subseteq C$, let

$$L^{-1}(c)=\{v:c\in L(v)\},\ L^{-1}(C^{\prime})=\bigcup_{c\in C^{\prime}}L^{-1}(c).$$

For a part $P$ of $G$ and integer $i$, let

$$C_{P,i}=\{c\in C:|L^{-1}(c)\cap P|=i\},C_{P,i^{+}}=\{c\in C:|L^{-1}(c)\cap P|\geq i\}.$$

If $S=\{v\}\in\mathcal{S}$ is a singleton part of $\mathcal{S}$, then we may also denote $v_{S}$ by $v$. In this case, $L_{\mathcal{S}}(v)=L(v)$. In the partitions $\mathcal{S}$ constructed in this paper, most parts of $\mathcal{S}$ are singleton parts. To define $\mathcal{S}$, it suffices to list its non-singleton parts.

It is obvious that a matching $M$ in $B_{\mathcal{S}}$ covering $V(G/\mathcal{S})$ induces a proper $L_{\mathcal{S}}$-colouring of $G/\mathcal{S}$, which in turn induces a proper $L$-colouring of $G$. As $G$ is not $L$-colourable, no such matching $M$ exists. By Hall’s Theorem, there is a subset $X_{\mathcal{S}}$ of $V(G/\mathcal{S})$ such that $|X_{\mathcal{S}}|>|N_{B_{\mathcal{S}}}(X_{\mathcal{S}})|$.

In the remainder of the paper, for a given partition $\mathcal{S}$ of $V(G)$, let $X_{\mathcal{S}}$ be a maximum subset of $V(G/\mathcal{S})$ for which $|X_{\mathcal{S}}|>|N_{B_{\mathcal{S}}}(X_{\mathcal{S}})|$. Let

$$Y_{\mathcal{S}}=N_{B_{\mathcal{S}}}(X_{\mathcal{S}})=\bigcup_{v_{S}\in X_{\mathcal{S}}}L_{\mathcal{S}}(v_{S}).$$

(2) Assume $P$ is a $2^{+}$-part of $G$ with $\bigcap_{v\in P}L(v)\neq\emptyset$, say $c\in\bigcap_{v\in P}L(v)$. We colour all vertices of $P$ by colour $c$. Let $G^{\prime}=G-P$ and $L^{\prime}(v)=L(v)-\{c\}$ for any vertex $v$ of $G^{\prime}$. As $|V(G^{\prime})|\leq 2\chi(G^{\prime})+2$ and $\chi(G^{\prime})=k-1$ is odd, it follows from Theorem 1.1 that $G^{\prime}$ is $L^{\prime}$-colourable, and hence $G$ is $L$-colourable, a contradiction.  

The following lemma was proved in [17] and also will be used in this paper.

The following theorem is the characterization of bad list assignments of $K_{4,2\star(k-1)}$ which has been proved in [2]. In this section, we give an alternate (and shorter) proof of this theorem.

Thus $|L^{-1}(c)\cap P_{1}|\leq 2$ for any $c\in C$. By (2) of Observation 2.1, we have $|C|\geq 2k$. Recall that $|C|\leq|V(G)|-1=2k+1$. Depending on the size of $C$, we consider two cases.

Since $|C|=2k+1$ and $|L(u_{1})|+|L(v_{1})|+|L(x_{1})|+|L(y_{1})|\geq 4k$, we may assume $L(u_{1})\cap L(v_{1})\neq\emptyset$. Let $\mathcal{S}$ be the partition of $V(G)$ with one non-singleton part $S=\{u_{1},v_{1}\}$, and consider the graph $G/\mathcal{S}$ and list assignment $L_{\mathcal{S}}$. Let $X_{\mathcal{S}}$ and $Y_{\mathcal{S}}$ be as defined in Section 2. We denote by $P^{\prime}_{i}$ be the parts of $G/\mathcal{S}$.

It is obvious that $X_{\mathcal{S}}-\{v_{S}\}\neq\emptyset$, and hence $|Y_{\mathcal{S}}|\geq|L(v)|\geq k$ for $v\in X_{\mathcal{S}}-\{v_{S}\}$. Hence $|X_{\mathcal{S}}|\geq k+1$. If there is an index $i\geq 2$ such that $P^{\prime}_{i}\subseteq X_{\mathcal{S}}$, then $|Y_{\mathcal{S}}|\geq|L^{\prime}(u_{i})|+|L^{\prime}(v_{i})|\geq 2k$ and hence $|X_{\mathcal{S}}|=|V(G/\mathcal{S})|=2k+1$. But in this case, by Observation 2.1, $|Y_{\mathcal{S}}|=|C|=2k+1=|X_{\mathcal{S}}|$, a contradiction.

So $|P^{\prime}_{i}\cap X|\leq 1$ for $i\geq 2$, and hence $|X_{\mathcal{S}}|\leq k+2$. Since $|X_{\mathcal{S}}|\geq k+1$, $|X_{\mathcal{S}}\cap P^{\prime}_{1}|\geq 2$. This implies that $|Y_{\mathcal{S}}|\geq k+1$ and hence $|X_{\mathcal{S}}|=k+2$, i.e., $P^{\prime}_{1}\subseteq X$. So $|Y_{\mathcal{S}}|\geq|L^{\prime}(v_{S})|+|L^{\prime}(x_{1})\cup L^{\prime}(y_{1})|\geq 1+k+1=k+2=|X_{\mathcal{S}}|$, a contradiction.

As $|C_{P_{1},1}|+2|C_{P_{1},2}|=\sum_{v\in P_{1}}|L(v)|=4k$ and $|C_{P_{1},1}|+|C_{P_{1},2}|\leq|C|$, we conclude that $|C_{P_{1},2}|=2k$, i.e., $C_{P_{1},2}=C$.

It is easy to see that $X_{\mathcal{S}}-\{v_{S},v_{T}\}\neq\emptyset$. Hence $|Y_{\mathcal{S}}|\geq|L(v)|\geq k$ for some $v\in X_{\mathcal{S}}-\{v_{S},v_{T}\}$. This implies that $|X_{\mathcal{S}}|\geq k+1$. If $|X_{\mathcal{S}}|>k+1$, then $P_{i}\subseteq X$ for some $2\leq i\leq k$, and hence $|Y_{\mathcal{S}}|\geq 2k=|V(G/\mathcal{S})|\geq|X_{\mathcal{S}}|$, a contradiction. So $|X_{\mathcal{S}}|=k+1$ and $k=|Y_{\mathcal{S}}|$. This implies that $P^{\prime}_{1}\subseteq X_{\mathcal{S}}$ and $|X_{\mathcal{S}}\cap P_{i}|=1$ for $2\leq i\leq k$. Let $S_{U}=X_{\mathcal{S}}-\{v_{S},v_{T}\}$ and $Y_{U}=Y_{\mathcal{S}}$. We have $L(S_{U})\cup(\bigcap_{v\in U}L(v))\cup(\bigcap_{v\in P_{1}-U}L(v))=Y_{U}.$ For $i=2,\ldots,k$ and $v\in S_{U}\cap P_{i}$, since $|Y_{U}|=k\leq|L(v)|$, we have $Y_{U}=L(v)$.  

By symmetry, we may assume $L(u_{1})\cap L(v_{1})\neq\emptyset$, $S_{\{u_{1},v_{1}\}}=\{u_{2},u_{3},\ldots,u_{k}\}$.

Since $|L(u_{1})\cap L(v_{1})|=|L(x_{1})\cap L(y_{1})|$ and $|L(u_{1})\cap L(v_{1})|+|L(x_{1})\cap L(y_{1})|\leq|Y_{\{u_{1},v_{1}\}}|=k$, we have $|L(u_{1})\cap L(v_{1})|=|L(x_{1})\cap L(y_{1})|\leq k/2$.

As $C_{P_{1},2}=C$, we may assume that $L(u_{1})\cap L(x_{1})\neq\emptyset$. Similarly, we have $|L(u_{1})\cap L(x_{1})|=|L(v_{1})\cap L(y_{1})|\leq k/2$.

Then

$$C_{P_{1},2}=C=(L(u_{1})\cap L(v_{1}))\cup(L(x_{1})\cap L(y_{1}))\cup(L(u_{1})\cap L(x_{1}))\cup(L(v_{1})\cap L(y_{1})).$$

Hence $|L(u_{1})\cap L(v_{1})|=|L(x_{1})\cap L(y_{1})|=|L(u_{1})\cap L(x_{1})|=|L(v_{1})\cap L(y_{1})|=k/2$. Then

$$(L(u_{1})\cap L(v_{1}))\cup(L(x_{1})\cap L(y_{1}))=Y_{\{u_{1},v_{1}\}},$$

$$(L(u_{1})\cap L(x_{1}))\cup(L(v_{1})\cap L(y_{1}))=Y_{\{u_{1},x_{1}\}}.$$

As $L(u_{1})\cap L(v_{1})\cap L(x_{1})=\emptyset$, we conclude that $Y_{\{u_{1},v_{1}\}}\cap Y_{\{u_{1},x_{1}\}}=\emptyset$ and $S_{\{u_{1},v_{1}\}}\cap S_{\{u_{1},x_{1}\}}=\emptyset$.

Thus we have $S_{\{u_{1},x_{1}\}}=\{v_{2},v_{3},\ldots,v_{k}\}$. Theorem 3.1 holds with $A_{1}=L(u_{1})\cap L(v_{1}),A_{2}=L(x_{1})\cap L(y_{1}),A_{3}=A_{4}=\emptyset$, $B_{1}=L(u_{1})\cap L(x_{1}),B_{2}=L(v_{1})\cap L(y_{1})$.

Since

	$\displaystyle C_{P_{1},2}=C$	$\displaystyle=(L(u_{1})\cap L(v_{1}))\cup(L(x_{1})\cap L(y_{1}))\cup(L(u_{1})\cap L(x_{1}))\cup(L(v_{1})\cap L(y_{1}))$
		$\displaystyle\cup(L(u_{1})\cap L(y_{1}))\cup(L(v_{1})\cap L(x_{1})),$

we may assume that $S_{\{u_{1},v_{1}\}}=S_{\{u_{1}y_{1}\}}$, $Y_{\{u_{1},v_{1}\}}=Y_{\{u_{1}y_{1}\}}$, $S_{\{u_{1},v_{1}\}}\cap S_{\{u_{1}x_{1}\}}=\emptyset$ and $Y_{\{u_{1},v_{1}\}}\cap Y_{\{u_{1}x_{1}\}}=\emptyset$. Then Theorem 3.1 holds with $A_{1}=L(u_{1})\cap L(v_{1}),A_{2}=L(x_{1})\cap L(y_{1}),A_{3}=L(u_{1})\cap L(y_{1}),A_{4}=L(v_{1})\cap L(x_{1})$, $B_{1}=L(u_{1})\cap L(x_{1}),B_{2}=L(v_{1})\cap L(y_{1})$.

This completes the proof of Theorem 3.1.  

Let $G=K_{3\star(k/2+1),1\star(k/2-1)}$. Assume $L$ is a bad $k$-list assignment of $G$. By Observation 2.1, for any 3-part $P$ of $G$, $\bigcap_{v\in P}L(v)=\emptyset$. Thus $2|C|\geq\sum_{v\in P}|L(v)|\geq 3k$. Hence $|C|\geq 3k/2$. If $|C|=3k/2$, then $G$ is not $L$-colourable, because if $f$ is a proper $L$-colouring of $G$, then $|f(P)|\geq 2$ for each 3-part $P$ and $|f(P)|=1$ for each 1-part $P$. As $f(P)\cap f(P^{\prime})=\emptyset$ for distinct parts $P$ and $P^{\prime}$, we have $|C|\geq\sum|f(P)|\geq 2\times(k/2+1)+(k/2-1)=3k/2+1$, a contradiction.