Circular chromatic index of graphs of maximum degree 3

Abstract

This paper proves that if G is a graph (parallel edges allowed) of maximum degree 3, then χc′(G) ≤ 11/3 provided that G does not contain H1 or H2 as a subgraph, where H1 and H2 are obtained by subdividing one edge of K23 (the graph with three parallel edges between two vertices) and K4, respectively. As χc′(H1) = χ c′(H2) = 4, our result implies that there is no graph G with 11/3 < χc′(G) < 4. It also implies that if G is a 2-edge connected cubic graph, then χc′(G) ≤ 11/3. © 2005 Wiley Periodicals, inc.