Circular chromatic index of Cartesian products of graphs |
| |
| Authors: | Douglas B West Xuding Zhu |
| |
| Institution: | 1. Department of Mathematics, University of Illinois, Urbana, Illinois 61801;2. Department of Applied Mathematics, National Sun Yat‐Sen University, Kaohsiung, Taiwan 80424;3. National Center for Theoretical Sciences, Taiwan |
| |
| Abstract: | The circular chromatic index of a graph G, written  , is the minimum r permitting a function  such that  whenever e and  are incident. Let  □  , where □ denotes Cartesian product and H is an  ‐regular graph of odd order, with  (thus, G is s‐regular). We prove that  , where  is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When  and m is large, the lower bound is sharp. In particular, if  , then  □  , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008 |
| |
| Keywords: | circular chromatic number circular chromatic index Cartesian product graph r‐tension |
|
|
