A Combined Logarithmic Bound on the Chromatic Index of Multigraphs

Michael Plantholt*, 2012: A Combined Logarithmic Bound on the Chromatic Index of Multigraphs. Journal of Graph Theory aop(aop)

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> 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.