By Mike Plantholt
Illinois State University
Abstract:
For a multigraph G, the integer round-up f(G) of the fractional chromatic index yields the best general lower bound for the chromatic index c′(G), and long-standing conjectures suggest that the chromatic index never surpasses this lower bound by more than one. We review classic upper bounds by Shannon, Vizing, Goldberg & Nishizeki, and some newer bounds by Kahn, and by Sanders and Streurer. Then we discuss an approach to show that if n denotes the order of G, then c′(G) ≤ f(G) + log (n+1), and c′(G) ≤ f(G) + log (f(G)).
January 25, 2005
At 3:30 in Wallace 430