• 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.

enter image description here

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.

  • $\begingroup$ One quick comment is that whatever your technique is, it should not work in the Klein Bottle grid of the same size (i.e. make the two long edges at the top and bottom crossing instead of parallel), because the graph is then 4-chromatic. So your proof should really distinguish toroidal and Klein bottle grids in a way. A second comment is : have you tried Alon-Tarsi ? $\endgroup$ Jul 8, 2019 at 6:58
  • $\begingroup$ @Esperet By Alon -Tarsi method, we can only get that the list chromatic number is in {3,4}. So I want to get another way to determine the exact value. $\endgroup$ Jul 9, 2019 at 9:10

1 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.

  • $\begingroup$ @Gordeev In this digraph, it does have a 7-circuit which has no kernel. Thank you very much. $\endgroup$ Jul 6, 2019 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.