A sublinear bound on the chromatic index of multigraphs Original Research Article

The integer round-up φ(G) of the fractional chromatic index yields the standard lower bound for the chromatic index of a multigraph G. We show that if G has even order n, then the chromatic index exceeds φ(G) by at most max{log32 n, 1 + n/30}. More generally, we show that for any real b,23 ⩽ b < 1, the chromatic index of G exceeds φ(G) by at most max{log1/b n, 1 + n(1 − b)/10}. This is used to show that for n sufficiently large, χ(G) ⩽ φ(G) + 1 + √n 1n n/10. Thus the difference between the chromatic index and its lower bound φ(G) is eventually sublinear; that is, for any real c > 0, there exists a positive integer N such that χ(G) − φ(G) < cn for any multigraph G with order n > N.