A Combined Logarithmic Bound on the Chromatic Index of Multigraphs

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.