Circular chromatic index of Cartesian products of graphs

✍ Scribed by Douglas B. West; Xuding Zhu

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 164 KB
• Volume: 57
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20257

✦ Synopsis

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