| 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 K (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. J Graph Theory 49: 325–335, 2005 |
