What is the choice number of a cyclic graph $C_n$, when $n$ is odd? I have been able to show that for even $n$, the choice number is two, using the fact that the cyclic orientation $D$ is kernel-perfect, and that for each vertex we have that the out-degree is 1. However, I cannot use this, because there is no kernel-perfect orientation for an odd cycle, such that this property holds. I don't really know another way to show the choosability? All I know is that the choice number is at least 3, because an odd cycle is 3-colourable.
2026-03-29 04:34:38.1774758878
choice number of an odd cycle
165 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
As you noted, since an odd cycle is not $2$-colorable, it is not $2$-choosable.
To prove that it is $3$-choosable, it suffices to realize that the choice number of any graph is at most one more than the maximum degree.
To see this more general fact, given a graph with maximum degree $d$ and an assignment of a set of size $d+1$ to each vertex, simply go from vertex to vertex making an arbitrary choice at each vertex which has not been chosen by its neighbors. You will never get stuck because each vertex has $d+1$ options, at most $d$ of which are precluded by its neighbors.