2016/06/25 by Guantao Chen, Chen, Guantao, Yuping Gao +7
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1606.07927
openalex publication_date 2016/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Δ≤ χ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)|)/(\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 χ'≥ Δ+2, which is commonly referred as Goldberg's conjecture. In this paper, we show that if χ' >Δ+√[3]Δ/2 then χ'=\lceilχf'\rceil. The previous best known result is for graphs with χ'> Δ+√(Δ/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≥ 3, every graph G with χ'>(m)/(m-1)Δ+(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≤ 23. Moreover, we show that Goldberg's conjecture holds for graphs G with Δ≤ 23 or |V(G)|≤ 23.