Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903849 | Journal of Combinatorial Theory, Series B | 2018 | 24 Pages |
Abstract
Given a graph G possibly with multiple edges but no loops, denote by Î the maximum degree, μ the multiplicity, Ïâ² the chromatic index and Ïfâ² the fractional chromatic index of G, respectively. It is known that Îâ¤Ïfâ²â¤Ïâ²â¤Î+μ, 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â¡|E(H)|â|V(H)|/2â, where the maximality is taken over all induced subgraphs H of G. Gupta (1967), Goldberg (1973), Andersen (1977), and Seymour (1979) conjectured that Ïâ²=âÏfâ²â if Ïâ²â¥Î+2, which is commonly referred as Goldberg's conjecture. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: For any positive integer m with mâ¥3, every graph G with Ïâ²>mmâ1Î+mâ3mâ1 satisfies Ïâ²=âÏfâ²â. Jakobsen's conjecture has been verified for m up to 15 by various researchers in the last four decades. We use an extended form of a Tashkinov tree to show that it is true for mâ¤23. With the same technique, we show that if Ïâ²â¥Î+Î/23 then Ïâ²=âÏfâ²â. The previous best known result is for graphs with Ïâ²>Î+Î/2 obtained by Scheide, and by Chen, Yu and Zang, independently. Moreover, we showthat Goldberg's conjecture holds for graphs G with Îâ¤23 or |V(G)|â¤23.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Guantao Chen, Yuping Gao, Ringi Kim, Luke Postle, Songling Shan,