For a multigraph G, the integer round-up φ(G) of the fractional chromatic index χf′(G) provides a good general lower bound for the chromatic index χ′(G). For an upper bound, Kahn 1996 showed that for any real c>0 there exists a positive integer N so that χ′(G) <χf′(G)+cχf′(G) whenever χf′(G)>N. We show that for any multigraph G with order n and at least one edge, χ′(G)≤φ(G)+ log 3/2(min {(n+1)/3,φ(G)}). This gives the following natural generalization of Kahn's result: for any positive reals c,e, there exists a positive integer N so that χ′(G)<χf′(G) + c (χf′(G))e whenever χf′(G)>N. We also compare the upper bound found here to other leading upper bounds.
展开▼
