0
$\begingroup$

Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation. For example, the cycle $0-1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-0$ is given the orientation in the usual sense $0\leftarrow1\leftarrow2\leftarrow3\leftarrow4\leftarrow5\leftarrow6\leftarrow7$ $\leftarrow8\leftarrow9\leftarrow10\leftarrow11\leftarrow12\leftarrow13\leftarrow14\leftarrow15\leftarrow0$; similarly for all other generated cycles from the elements $2,3,4$. Then, as I see, all cliques are having kernels, and, overall, i think the graph $G$ is kernel-perfect. But, in this orientation, I observe that maximum outdegree is equal to $k=4$. Then, does it imply that choice number, or, list chromatic number of $G$ is equal to $k+1=5$, by the kernel lemma. Clearly, this should be impossible, as the chromatic number of graph is $6$.

What am I missing here? Thanks beforehand.

$\endgroup$
6
  • $\begingroup$ @bof but, in $C_5$, the orientation is not having kernel right (the usual orientation) $\endgroup$
    – vidyarthi
    Commented Nov 28, 2023 at 10:51
  • $\begingroup$ @bof ok, so the subgraph induced by $\{0,3,6,9,12\}$ does not have a kernel, I suppose. So then, does the power of cycle not have a kernel perfect orientation? $\endgroup$
    – vidyarthi
    Commented Nov 28, 2023 at 10:53
  • $\begingroup$ @bof like, for all cliques to be kernel perfect, this orientation, or its reverse seems to be the only one. So, if this does not work, then there is no such orientation, right! $\endgroup$
    – vidyarthi
    Commented Nov 28, 2023 at 17:32
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – vidyarthi
    Commented Nov 29, 2023 at 10:07
  • $\begingroup$ @bof ok, no problem. The automatic system message said to continue the discussion in chat, so i did. What I was saying that if $G$ had to kernel perfect, that all cliques should be. Then, one vertex in all cliques should be an all absorbing one in the orientation. This invariably implies that, by virtue of the structure of $G$, that no such kernel orientation exists. Is my reasoning right? If no, you could give a kernel perfect orientation, otherwise, you could say don't know. By the way, I never said your reasoning is wrong. I agree with you $\endgroup$
    – vidyarthi
    Commented Nov 29, 2023 at 11:00

0

You must log in to answer this question.