Premium
A Combined Logarithmic Bound on the Chromatic Index of Multigraphs
Author(s) -
Plantholt* Michael
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21670
Subject(s) - multigraph , mathematics , combinatorics , upper and lower bounds , integer (computer science) , edge coloring , logarithm , generalization , chromatic scale , order (exchange) , index (typography) , discrete mathematics , graph , computer science , mathematical analysis , finance , line graph , world wide web , economics , graph power , programming language
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.