A Combined Logarithmic Bound on the Chromatic Index of Multigraphs |
| |
Authors: | Michael Plantholt |
| |
Institution: | DEPARTMENT OF MATHEMATICS, ILLINOIS STATE UNIVERSITY, , NORMAL, ILLINOIS, 61790‐4520 |
| |
Abstract: | For a multigraph G, the integer round‐up of the fractional chromatic index provides a good general lower bound for the chromatic index . For an upper bound, Kahn 1996 showed that for any real there exists a positive integer N so that whenever . We show that for any multigraph G with order n and at least one edge, ). This gives the following natural generalization of Kahn's result: for any positive reals , there exists a positive integer N so that + c whenever . We also compare the upper bound found here to other leading upper bounds. |
| |
Keywords: | chromatic index fractional chromatic index multigraph |
|
|