
arXiv: 1606.07927
Given a graph $G$ possibly with multiple edges but no loops, denote by $��$ the {\it maximum degree}, $��$ the {\it multiplicity}, $��'$ the {\it chromatic index} and $��_f'$ the {\it fractional chromatic index} of $G$, respectively. It is known that $��\le ��_f' \le ��' \le ��+ ��$, where the upper bound is a classic result of Vizing. While deciding the exact value of $��'$ is a classic NP-complete problem, the computing of $��_f'$ is in polynomial time. In fact, it is shown that if $��_f' > ��$ then $��_f'= \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 $��'=\lceil��_f'\rceil$ if $��'\ge ��+2$, which is commonly referred as Goldberg's conjecture. In this paper, we show that if $��' >��+\sqrt[3]{��/2}$ then $��'=\lceil��_f'\rceil$. The previous best known result is for graphs with $��'> ��+\sqrt{��/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 $��'>\frac{m}{m-1}��+\frac{m-3}{m-1}$ satisfies $��'=\lceil��_f'\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 $��\leq 23$ or $|V(G)|\leq 23$.
21pages
Coloring of graphs and hypergraphs, 05C15, Tashkinov tree, critical graph, FOS: Mathematics, Mathematics - Combinatorics, fractional chromatic index, edge chromatic index, extended Tashkinov tree, Combinatorics (math.CO), Trees
Coloring of graphs and hypergraphs, 05C15, Tashkinov tree, critical graph, FOS: Mathematics, Mathematics - Combinatorics, fractional chromatic index, edge chromatic index, extended Tashkinov tree, Combinatorics (math.CO), Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
