Chromatic index determined by fractional chromatic index

Abstract

Given a graph $G$ possibly with multiple edges but no loops, denote by $\Delta$ the {\it maximum degree}, $\mu$ the {\it multiplicity}, ${\chi }^{\prime }$ the {\it chromatic index} and ${\chi }_f^{\prime }$ the {\it fractional chromatic index} of $G$, respectively. It is known that $\Delta \le {\chi }_f^{\prime }\le {\chi }^{\prime }\le \Delta +\mu$, where the upper bound is a classic result of Vizing. While deciding the exact value of ${\chi }^{\prime }$ is a classic NP-complete problem, the computing of ${\chi }_f^{\prime }$ is in polynomial time. In fact, it is shown that if ${\chi }_f^{\prime }>\Delta$ then ${\chi }_f^{\prime }=\max \frac{|E(H)|}{\lfloor |V(H)|/2\rfloor }$, where the maximality is over all induced subgraphs $H$ of $G$. Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) conjectured that ${\chi }^{\prime }=\lceil {\chi }_f^{\prime }\rceil$ if ${\chi }^{\prime }\ge \Delta +2$, which is commonly referred as Goldberg's conjecture. In this paper, we show that if ${\chi }^{\prime }>\Delta +\sqrt[3]{\Delta /2}$ then ${\chi }^{\prime }=\lceil {\chi }_f^{\prime }\rceil$. The previous best known result is for graphs with ${\chi }^{\prime }>\Delta +\sqrt{\Delta /2}$ obtained by Scheide, and by Chen, Yu and Zang, independently. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: {\it For any positive integer $m$ with $m\ge 3$, every graph $G$ with ${\chi }^{\prime }>\frac{m}{m-1}\Delta +\frac{m-3}{m-1}$ satisfies ${\chi }^{\prime }=\lceil {\chi }_f^{\prime }\rceil$.} Jakobsen's conjecture has been verified for $m$ up to 15 by various researchers in the last four decades. We show that it is true for $m\le 23$. Moreover, we show that Goldberg's conjecture holds for graphs $G$ with $\Delta \le 23$ or $|V(G)|\le 23$.

21pages

Cited by in corpus (1)

• Goldberg's Conjecture is true for random multigraphs