×

Chromatic index determined by fractional chromatic index. (English) Zbl 1387.05083

Summary: Given a graph \(G\) possibly with multiple edges but no loops, denote by \(\Delta\) the maximum degree, \(\mu\) the multiplicity, \(\chi^\prime\) the chromatic index and \(\chi_f^\prime\) the fractional chromatic index of \(G\), respectively. It is known that \(\Delta \leq \chi_f^\prime \leq \chi^\prime \leq \Delta + \mu\), where the upper bound is a classic result of V. G. Vizing [“On an estimate of the chromatic class of a \(p\)-graph”, Diskretn. Anal. Issled. Oper. 3, 25–30 (1964)]. 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 taken over all induced subgraphs \(H\) of \(G\). R. P. Gupta [Studies in the theory of graphs. Bombay: Tata Institute of Fundamental Research (PhD) (1967)], M. K. Gol’dberg [Diskret. Analiz, Novosibirsk 23, 3–7 (1973; Zbl 0301.05110)], L. D. Andersen [Math. Scand. 40, 161–175 (1977; Zbl 0373.05035)], and P. Seymour [Proc. Lond. Math. Soc., III. Ser. 38, 423–460 (1979; Zbl 0411.05037)] conjectured that \(\chi^\prime = \lceil \chi_f^\prime \rceil\) if \(\chi^\prime \geq \Delta + 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 \geq 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 use an extended form of a Tashkinov tree to show that it is true for \(m \leq 23\). With the same technique, we show that if \(\chi^\prime \geq \Delta + \root 3 \of {\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 D. Scheide [J. Comb. Theory, Ser. B 100, No. 1, 68–96 (2010; Zbl 1210.05051)], and by G. Chen et al. [J. Comb. Optim. 21, No. 2, 219–246 (2011; Zbl 1233.90268)], independently. Moreover, we show that Goldberg’s conjecture holds for graphs \(G\) with \(\Delta \leq 23\) or \(| V(G) | \leq 23\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andersen, Lars Døvling, On edge-colourings of graphs, Math. Scand., 40, 2, 161-175 (1977) · Zbl 0373.05035
[2] Chen, Guantao; Yu, Xingxing; Zang, Wen’an, Approximating the chromatic index of multigraphs, J. Comb. Optim., 21, 2, 219-246 (2011) · Zbl 1233.90268
[3] Edmonds, Jack, Maximum matching and a polyhedron with \(0, 1\)-vertices, J. Res. Natl. Bur. Stand., B, 69, 125-130 (1965) · Zbl 0141.21802
[4] Lene Monrad Favrholdt, Michael Stiebitz, Bjarne Toft, Graph edge coloring: Vizing’s theorem and goldberg’s conjecture, Preprint DMF-2006-10-003, IMADA-PP-2006-20, University of Southern Demark, 2006.; Lene Monrad Favrholdt, Michael Stiebitz, Bjarne Toft, Graph edge coloring: Vizing’s theorem and goldberg’s conjecture, Preprint DMF-2006-10-003, IMADA-PP-2006-20, University of Southern Demark, 2006.
[5] Goldberg, Mark K., On multigraphs of almost maximal chromatic class, Diskretn. Anal., 23, 3-7 (1973), (in Russian)
[6] Goldberg, Mark K., Edge-coloring of multigraphs: recoloring technique, J. Graph Theory, 8, 1, 123-137 (1984) · Zbl 0554.05023
[7] Gupta, Ram Prakash, Studies in the Theory of Graphs (1967), Tata Institute of Fundamental Research: Tata Institute of Fundamental Research Bombay, Thesis (PhD) · Zbl 0149.41604
[8] Holyer, Ian, The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720 (1981) · Zbl 0473.68034
[9] Jakobsen, Ivan Tafteberg, Some remarks on the chromatic index of a graph, Arch. Math. (Basel), 24, 440-448 (1973) · Zbl 0273.05108
[10] Kahn, Jeff, Asymptotics of the chromatic index for multigraphs, J. Combin. Theory Ser. B, 68, 2, 233-254 (1996) · Zbl 0861.05026
[11] Kierstead, Henry Andrew, On the chromatic index of multigraphs without large triangles, J. Combin. Theory Ser. B, 36, 2, 156-160 (1984) · Zbl 0541.05027
[12] McDonald, Jessica, Edge-colourings, (Beineke, L. W.; Wilson, R. J., Topics in Topological Graph Theory (2015), Cambridge University Press), 94-113 · Zbl 1355.05113
[13] Nishizeki, Takao; Kashiwagi, Kenichi, On the 1.1 edge-coloring of multigraphs, SIAM J. Discrete Math., 3, 3, 391-410 (1990) · Zbl 0702.05036
[14] Scheide, Diego, Graph edge colouring: Tashkinov trees and Goldberg’s conjecture, J. Combin. Theory Ser. B, 100, 1, 68-96 (2010) · Zbl 1210.05051
[15] Seymour, Paul, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. Lond. Math. Soc. (3), 38, 3, 423-460 (1979) · Zbl 0411.05037
[16] Shannon, Claude Elwood, A theorem on coloring the lines of a network, J. Math. Phys., 28, 148-151 (1949) · Zbl 0032.43203
[17] Stiebitz, Michael; Scheide, Diego; Toft, Bjarne; Favrholdt, Lene Monrad, Vizing’s theorem and Goldberg’s conjecture, (Graph Edge Coloring. Graph Edge Coloring, Wiley-Intersci. Ser. Discrete Math. Optim. (2012), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. Hoboken, NJ), With a preface by Stiebitz and Toft · Zbl 1339.05001
[18] Tashkinov, Vladimir Aleksandrovich, On an algorithm for the edge coloring of multigraphs, Diskretn. Anal. Issled. Oper. Ser. 1, 7, 3, 72-85 (2000) · Zbl 0955.05036
[19] Vizing, Vadim Georgievich, On an estimate of the chromatic class of a \(p\)-graph, Diskretn. Anal., 3, 25-30 (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.