A Combined Logarithmic Bound on the Chromatic Index of a Multigraph

2010/12/22 by Michael J. Plantholt, Michael Plantholt, Plantholt, Michael
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1012.5003

openalex publication_date 2010/12/22 · arxiv created 2010/12/23 · arxiv updated 2010/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a multigraph G, the integer round-up phi(G) of the fractional chromatic index yields a good general lower bound for the chromatic index . For an upper bound, Kahn showed that for any real c > 0 there exists a positive integer N so that the chromatic index is less than (1+c)*phi(G) whenever the fractional index > N. We show the amount by which the chromatic index can surpass phi(G) is in fact logarithmic, by showing that for any multigraph G with order n > 3 and at least one edge, the chromatic index is less than phi(G) + log (min (n+1)/3, phi(G)) .

Related

• Chromatic index determined by fractional chromatic index
• The \bmod k chromatic index of random graphs
• On the f-matching polytope and the fractional f-chromatic index
• The mod k chromatic index of graphs is O(k)
• Fractional chromatic number of a random subgraph