Circular chromatic index of graphs of maximum degree 3

Abstract

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 H 1 or H 2 as a subgraph, where H 1 and H 2 are obtained by subdividing one edge of K (the graph with three parallel edges between two vertices) and K 4 , respectively. As χ′ c ( H 1 ) = χ′ c ( H 2 ) = 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. J Graph Theory 49: 325–335, 2005