×

Goldberg’s conjecture is true for random multigraphs. (English) Zbl 1415.05165

Summary: M. K. Gol’dberg [Diskret. Analiz, Novosibirsk 23, 3–7 (1973; Zbl 0301.05110)], and independently P. D. Seymour [Proc. Lond. Math. Soc. (3) 38, 423–460 (1979; Zbl 0411.05037)], conjectured that for any multigraph \(G\), the chromatic index \(\chi^\prime(G)\) satisfies \(\chi^\prime(G) \leq \max \{{\Delta}(G) + 1, \lceil \rho(G) \rceil \}\), where \(\rho(G) = \max \{\frac{e(G [S])}{\lfloor | S | / 2 \rfloor} | S \subseteq V \}\). We show that their conjecture (in a stronger form) is true for random multigraphs. Let \(M(n, m)\) be the probability space consisting of all loopless multigraphs with \(n\) vertices and \(m\) edges, in which \(m\) pairs from \([n]\) are chosen independently at random with repetitions. Our result states that, for a given \(m : = m(n)\), \(M \sim M(n, m)\) typically satisfies \(\chi^\prime(G) = \max \{{\Delta}(G), \lceil \rho(G) \rceil \}\). In particular, we show that if \(n\) is even and \(m : = m(n)\), then \(\chi^\prime(M) = {\Delta}(M)\) for a typical \(M \sim M(n, m)\). Furthermore, for a fixed \(\varepsilon > 0\), if \(n\) is odd, then a typical \(M \sim M(n, m)\) has \(\chi^\prime(M) = {\Delta}(M)\) for \(m \leq(1 - \varepsilon) n^3 \log n\), and \(\chi^\prime(M) = \lceil \rho(M) \rceil\) for \(m \geq(1 + \varepsilon) n^3 \log n\). To prove this result, we develop a new structural characterization of multigraphs with chromatic index larger than the maximum degree.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Alon, N.; Spencer, J. H., The Probabilistic Method (2016), Wiley: Wiley New York · Zbl 1333.05001
[2] Andersen, L. D., On edge-colourings of graphs, Math. Scand., 40, 2, 161-175 (1977) · Zbl 0373.05035
[3] Bollobás, B., Random Graphs (2001), Cambridge University Press · Zbl 0997.05049
[4] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B, 71, 2, 184-204 (1997) · Zbl 0876.05032
[5] Chen, G.; Gao, Y.; Kim, R.; Postle, L.; Shan, S., Chromatic index determined by fractional chromatic index (2016), preprint · Zbl 1387.05083
[6] Chen, G.; Yu, X.; Zang, W., Approximating the chromatic index of multigraphs, J. Comb. Optim., 21, 2, 219-246 (2011) · Zbl 1233.90268
[7] Choudum, S. A.; Kayathri, K., An extension of Vizing’s adjacency lemma on edge chromatic critical graphs, Discrete Math., 206, 1-3, 97-103 (1999) · Zbl 0929.05029
[8] Dubhashi, D. P.; Priebe, V.; Ranjan, D., Negative dependence through the FKG inequality, BRICS Rep. Ser., 3, 27 (1996)
[9] Erdős, P.; Wilson, R. J., On the chromatic index of almost all graphs, J. Combin. Theory Ser. B, 23, 2-3, 255-257 (1977) · Zbl 0378.05032
[10] Ferber, A.; Jain, V., 1-factorizations of pseudorandom graphs (2018), preprint
[11] Frieze, A. M.; Jackson, B.; McDiarmid, C. J.; Reed, B., Edge-colouring random graphs, J. Combin. Theory Ser. B, 45, 2, 135-149 (1988) · Zbl 0656.05054
[12] Galvin, F., The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B, 63, 1, 153-158 (1995) · Zbl 0826.05026
[13] Goldberg, M. K., On multigraphs of almost maximal chromatic class, Diskretn. Anal., 23, 3, 7 (1973), (in Russian)
[14] Goldberg, M. K., Edge-coloring of multigraphs: recoloring technique, J. Graph Theory, 8, 1, 123-137 (1984) · Zbl 0554.05023
[15] Haxell, P. E.; Kierstead, H. A., Edge coloring multigraphs without small dense subsets, Discrete Math., 338, 12, 2502-2506 (2015) · Zbl 1318.05028
[16] Hind, H. R.F., Restricted Edge-Colourings (1988), University of Cambridge, PhD diss.
[17] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720 (1981) · Zbl 0473.68034
[18] Janson, S.; Łuczak, T.; Rucinski, A., Random Graphs (2000), John Wiley & Sons
[19] Kahn, J., Asymptotically good list-colorings, J. Combin. Theory Ser. A, 73, 1, 1-59 (1996) · Zbl 0851.05081
[20] Kahn, J., Asymptotics of the chromatic index for multigraphs, J. Combin. Theory Ser. B, 68, 2, 233-254 (1996) · Zbl 0861.05026
[21] McDiarmid, C., On a correlation inequality of Farr, Combin. Probab. Comput., 1, 2, 157-160 (1992) · Zbl 0798.60009
[22] Plantholt, M., A combined logarithmic bound on the chromatic index of multigraphs, J. Graph Theory, 73, 3, 239-259 (2013) · Zbl 1269.05040
[23] Scheide, D., Graph edge colouring: Tashkinov trees and Goldberg’s conjecture, J. Combin. Theory Ser. B, 100, 1, 68-96 (2010) · Zbl 1210.05051
[24] Seymour, P. D., On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. Lond. Math. Soc., 3, 3, 423-460 (1979) · Zbl 0411.05037
[25] Seymour, P. D., Some unsolved problems on one-factorizations of graphs, (Graph Theory and Related Topics (1979), Academic Press: Academic Press New York)
[26] Shannon, C. E., A theorem on coloring the lines of a network, J. Math. Phys., 28, 1, 148-152 (1949) · Zbl 0032.43203
[27] Stiebitz, M.; Scheide, D.; Toft, B.; Favrholdt, L., Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture (2012), Wiley · Zbl 1339.05001
[28] Tashkinov, V. A., On an algorithm to color the edges of a multigraph, Diskretn. Anal., 7, 3, 72-85 (2000), (in Russian) · Zbl 0955.05036
[29] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Diskretn. Anal., 3, 3, 25-30 (1964), (in Russian)
[30] West, D. B., Introduction to Graph Theory (2001), Prentice Hall
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.