The list chromatic number of some special toroidal grid graphs

Question

• A list-assignment $L$ to the vertices of $G$ is the assignment of a list set $L(v)$ of colours to every vertex $v$ of $G$; and a $k$-list-assignment is a list-assignment such that $|L(v)|\geq k$, for every vertex $v$. If $L$ is a list-assignment to $G$, then an $L$-colouring of $G$ is a colouring (not necessarily proper) in which each vertex receives a colour from its own list;

• The graph $G$ is $k$-list-colourable, or $k$-choosable, if it is properly $L$-colourable for every $k$-list-assignment $L$ to $G$. The chromatic number $\chi(G)$ of $G$ is the smallest number $k$ such that $G$ is $k$-colourable. The list chromatic number $\chi_l(G)$, is the smallest number $k$ such that $G$ is $k$-list-colourable or $k$-choosable.

• It is evident that $\chi_l(G)\geq \chi(G)$, since if $k < \chi(G)$ then $G$ is not $L$-colourable when every vertex $v$ of $G$ is given the same list $L(v)$ of $k$ colours.

Consider the graph $S_n$ which has as vertex set the $n^2$ cells of our $n\times n$ array with two cells adjacent if and only if they are in the same row or column. The graph $S_n$ Since any $n$ cells in a row are pairwise adjacent we need at least $n$ colors. Furthermore, any coloring with $n$ colors corresponds to a Latin square, with the cells occupied by the same number forming a color class. Since Latin squares, as we have seen, exist, we infer $\chi(S_n) = n$, and the Dinitz problem can be stated as $$\chi_l(S_n) = n? $$

Now we know that the equality holds for all $n$. By the solution of Dinitz's problem, we know that the list chromatic number of $C_3\Box C_3$ is 3, i.e. $\chi_l(C_3\Box C_3)=3$.

The method of attack for the Dinitz problem is : We have to find an orientation of the graph $S_n$ with outdegrees $d_+(v) ≤ n−1$ for all $v$ and which ensures the existence of a kernel for all induced subgraphs.

I want to know the $\chi_l(C_3\Box C_5)$ and $\chi_l(C_5\Box C_5)$. I conjecure both of them are 3.

In the above oriented graph $C_3\Box C_5$, for all vetex $V$, it is easy to see that
$$ deg_-(v)=deg_+(v)=2.$$ I verified some of induced subgraph which indeed have a kernel. But I have no idea how to prove that all induced subgraph have a kernel. If someone can give any suggestions or comments, I will appreciate it. Thanks.

Answer 1

I will encode orientations of $C_3\square C_5$ with outdegress equal to two by labeling vertices with numbers $0,1,2$, such that vertex with label $x$ has exactly $x$ outgoing horizontal arcs. For example, your picture encodes as $$ 21110\\ 02021\\ 10202 $$

One can restore the orientation from such encoding - each horizontal cycle breaks up into an even number of paths oriented from $2$ to $0$, and each vertical cycle breaks up into two paths oriented from $0$ to $2$.

There is only one orientation of $C_3\square C_5$ satisfying conditions on outdegrees (modulo cyclic shifts and reflections). To see that first note that in any such orientation there will be one vertex of each label in any vertical cycle. Each horizontal cycle must have an equal amount of $0$'s and $2$'s. That means that two of horizontal cycles will have multisets of labels $\{0,0,1,2,2\}$, and the remaining horizontal cycle will have multiset $\{0,1,1,1,2\}$. We can assume it is the first cycle. Modulo cyclic shifts and reflections, this cycle is encoded either as $21110$, or $21101$. In the first case, the only possible orientation is yours (again, modulo horizontal reflection). In the second case, no such orientation exists. In both cases I use the fact that in each cycle $0$'s and $2$'s must interchange each other, if you remove $1$'s.

Finally, the following induced subgraph in the orientation from the picture does not have a kernel, because it is an odd cycle: $$ 2\color{red}{1110}\\ 02021\\ \color{red}{10}20\color{red}2 $$

So unfortunately it looks like the kernel method will not help in this problem.