Circular chromatic index of Cartesian products of graphs
Douglas B. West, Xuding Zhu · Journal of Graph Theory · 2007
Abstract The circular chromatic index of a graph G, written $\chi_{c}'(G)$ , is the minimum r permitting a function $f : E(G)\rightarrow [0,r)$ such that $1 \le | f(e)-f(e')|\le r - 1$ whenever e and $e'$ are incident. Let $G = H$ □ $C_{2m +1}$ , where □ denotes Cartesian product and H is an $(s-2)$ ‐regular graph of odd order, with $s \equiv 0 \, {\rm mod}\, 4$ (thus, G is s‐regular). We prove that $\chi_{c}'(G) \ge s +\lfloor \lambda(1 - 1/s)\rfloor^{-1}$ , where $\lambda$ is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When $H = C_{2k +1}$ and m is large, the lower bound is sharp. In particular, if $m \ge 3k + 1$ , then $\chi_{c}'(C_{2k +1}$ □ $C_{2m + 1})=4 + \lceil {3k/2} \rceil^{-1}$ , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008