×

A proof of the Erdős-Faber-Lovász conjecture. (English) Zbl 1520.05036

Summary: The Erdős-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on \(n\) vertices is at most \(n\). In this paper, we prove this conjecture for every large \(n\). We also provide stability versions of this result, which confirm a prediction of J. Kahn [Bolyai Soc. Math. Stud. 3, 305–353 (1994; Zbl 0820.05050)].

MSC:

05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achlioptas, Dimitris; Iliopoulos, Fotis; Sinclair, Alistair, Beyond the {L}ov{\'{a}}sz local lemma: point to set correlations and their algorithmic applications. 2019 {IEEE} 60th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience, 725-744 (2019) · doi:10.1109/FOCS.2019.00049
[2] Ajtai, M.; Koml\'{o}s, J.; Pintz, J.; Spencer, J.; Szemer\'{e}di, E., Extremal uncrowded hypergraphs, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 32, 321-335 (1982) · Zbl 0485.05049 · doi:10.1016/0097-3165(82)90049-8
[3] Ajtai, Mikl\'{o}s; Koml\'{o}s, J\'{a}nos; Szemer\'{e}di, Endre, A note on {R}amsey numbers, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 29, 354-360 (1980) · Zbl 0455.05045 · doi:10.1016/0097-3165(80)90030-8
[4] Alon, Noga; Krivelevich, Michael; Sudakov, Benny, Coloring graphs with sparse neighborhoods, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 77, 73-82 (1999) · Zbl 1026.05043 · doi:10.1006/jctb.1999.1910
[5] Alon, Noga; Yuster, Raphael, On a hypergraph matching problem, Graphs Combin.. Graphs and Combinatorics, 21, 377-384 (2005) · Zbl 1090.05051 · doi:10.1007/s00373-005-0628-x
[6] Berge, C., On the chromatic index of a linear hypergraph and the {C}hv\'{a}tal conjecture. Combinatorial {M}athematics: {P}roceedings of the {T}hird {I}nternational {C}onference, Ann. New York Acad. Sci., 555, 40-44 (1989) · Zbl 0726.05055 · doi:10.1111/j.1749-6632.1989.tb22435.x
[7] Bonamy, Marthe; Perrett, Thomas; Postle, Luke, Colouring graphs with sparse neighbourhoods: bounds and applications, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 155, 278-317 (2022) · Zbl 1492.05041 · doi:10.1016/j.jctb.2022.01.009
[8] Bruhn, Henning; Joos, Felix, A stronger bound for the strong chromatic index, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 27, 21-43 (2018) · Zbl 1378.05047 · doi:10.1017/S0963548317000244
[9] Chang, W. I.; Lawler, E. L., Edge coloring of hypergraphs and a conjecture of {E}rd{\H{o}}s, {F}aber, {L}ov{\'{a}}sz, Combinatorica. Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society, 8, 293-295 (1988) · Zbl 0661.05026 · doi:10.1007/BF02126801
[10] Chung, Fan; Graham, Ron, Erd{\H{o}}s on Graphs. His Legacy of Unsolved Problems, xiv+142 pp. (1998) · Zbl 0890.05049 · doi:10.1201/9781439863879
[11] Chung, Fan; Lu, Linyuan, Connected components in random graphs with given expected degree sequences, Ann. Comb.. Annals of Combinatorics, 6, 125-145 (2002) · Zbl 1009.05124 · doi:10.1007/PL00012580
[12] Davies, E.; Kang, R. J.; Pirot, F.; Sereni, J.-S., Graph structure via local occupancy (2020)
[13] Ehard, Stefan; Glock, Stefan; Joos, Felix, Pseudorandom hypergraph matchings, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 29, 868-885 (2020) · Zbl 1466.05147 · doi:10.1017/s0963548320000280
[14] Erd{\H{o}}s, P.; Hanani, H., On a limit theorem in combinatorial analysis, Publ. Math. Debrecen. Publicationes Mathematicae Debrecen, 10, 10-13 (1963) · Zbl 0122.24802 · doi:10.5486/pmd.1963.10.1-4.02
[15] Erd{\H{o}}s, P., On the combinatorial problems which {I} would most like to see solved, Combinatorica. Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society, 1, 25-42 (1981) · Zbl 0486.05001 · doi:10.1007/BF02579174
[16] Erd{\H{o}}s, P.; Gy\'{a}rf\'{a}s, A.; Pyber, L., Vertex coverings by monochromatic cycles and trees, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 51, 90-95 (1991) · Zbl 0766.05062 · doi:10.1016/0095-8956(91)90007-7
[17] Faber, Vance, The {E}rd{\H{o}}s-{F}aber-{L}ov{\'{a}}sz conjecture-the uniform regular case, J. Comb.. Journal of Combinatorics, 1, 113-120 (2010) · Zbl 1225.05190 · doi:10.4310/JOC.2010.v1.n2.a2
[18] Faber, Vance, Linear Hypergraph List Edge Coloring – {G}eneralizations of the {EFL} Conjecture to List Coloring (2017)
[19] Faber, Vance; Harris, David G., Edge-coloring linear hypergraphs with medium sized edges, Random Structures Algorithms. Random Structures & Algorithms, 55, 153-159 (2019) · Zbl 1423.05066 · doi:10.1002/rsa.20843
[20] Frieze, Alan; Mubayi, Dhruv, Coloring simple hypergraphs, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 103, 767-794 (2013) · doi:10.1016/j.jctb.2013.09.003
[21] F\"{u}redi, Z., The chromatic index of simple hypergraphs, Graphs Combin.. Graphs and Combinatorics, 2, 89-92 (1986) · Zbl 0589.05036 · doi:10.1007/BF01788081
[22] Glock, Stefan; K\"{u}hn, Daniela; Osthus, Deryk, Optimal path and cycle decompositions of dense quasirandom graphs, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 118, 88-108 (2016) · Zbl 1332.05078 · doi:10.1016/j.jctb.2016.01.004
[23] Graham, R. L.; Pollak, H. O., On embedding graphs in squashed cubes. Graph Theory and Applications, Lecture Notes in Math., 303, 99-110 (1972) · Zbl 0251.05123 · doi:10.1007/BFb0067362
[24] Huang, Hao; Sudakov, Benny, A counterexample to the {A}lon-{S}aks-{S}eymour conjecture and related problems, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 32, 205-219 (2012) · Zbl 1299.05123 · doi:10.1007/s00493-012-2746-4
[25] Hurley, Eoin; de Joannis de Verclos, R\'{e}mi; Kang, Ross J., An improved procedure for colouring graphs of bounded local density. Proceedings of the 2021 {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms, 135-148 (2021) · doi:10.1137/1.9781611976465.10
[26] Johansson, A., Asymptotic choice number for triangle free graphs (1996)
[27] Kahn, Jeff, Coloring nearly-disjoint hypergraphs with {\(n+o(n)\)} colors, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 59, 31-39 (1992) · Zbl 0774.05073 · doi:10.1016/0097-3165(92)90096-D
[28] Kahn, J., Recent results on some not-so-recent hypergraph matching and covering problems. Extremal Problems for Finite Sets, Bolyai Soc. Math. Stud., 3, 305-353 (1994) · Zbl 0820.05050
[29] Kahn, Jeff, Asymptotics of hypergraph matching, covering and coloring problems. Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. 1, 2, 1353-1362 (1995) · Zbl 0842.05067 · doi:10.1007/978-3-0348-9078-6_130
[30] Kahn, Jeff, Asymptotically good list-colorings, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 73, 1-59 (1996) · Zbl 0851.05081 · doi:10.1006/jcta.1996.0001
[31] Kahn, Jeff, On some hypergraph problems of {P}aul {E}rd{\H{o}}s and the asymptotics of matchings, covers and colorings. The Mathematics of {P}aul {E}rd{\H{o}}s, {I}, Algorithms Combin., 13, 345-371 (1997) · Zbl 0865.05056 · doi:10.1007/978-3-642-60408-9_26
[32] Kahn, Jeff; Seymour, P. D., A fractional version of the {E}rd{\H{o}}s-{F}aber-{L}ov{\'{a}}sz conjecture, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 12, 155-160 (1992) · Zbl 0774.05072 · doi:10.1007/BF01204719
[33] Kang, Dong Yeap; Kelly, Tom; K{\"{u}}hn, Daniela; Methuku, Abhishek; Osthus, Deryk, Graph and hypergraph colouring via nibble methods: A survey (2021)
[34] Kang, Dong Yeap; Kelly, Tom; K{\"{u}}hn, Daniela; Methuku, Abhishek; Osthus, Deryk, A proof of the {E}rd{\H{o}}s-{F}aber-{L}ov{\'{a}}sz conjecture: algorithmic aspects. 2021 {IEEE} 62nd {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience—{FOCS} 2021, 1080-1089 (2022) · doi:10.1109/FOCS52979.2021.00107
[35] Kang, Dong Yeap; Kelly, Tom; K{\"{u}}hn, Daniela; Methuku, Abhishek; Osthus, Deryk, Solution to a problem of {E}rd{\H{o}}s on the chromatic index of hypergraphs with bounded codegree (2021)
[36] Kang, Dong Yeap; K{\"{u}}hn, Daniela; Methuku, Abhishek; Osthus, Deryk, New bounds on the size of Nearly Perfect Matchings in almost regular hypergraphs (2020)
[37] Kayll, P. Mark, Two chromatic conjectures: one for vertices and one for edges. Graph theory-favorite conjectures and open problems. 1, Probl. Books in Math., 171-194 (2016) · Zbl 1352.05071 · doi:10.1007/978-3-319-31940-7_11
[38] Kelly, T.; K{\"u}hn, D.; Osthus, D., A special case of {V}u’s conjecture: {C}oloring nearly disjoint graphs of bounded maximum degree (2021)
[39] Kim, Jeong Han, On {B}rooks’ theorem for sparse graphs, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 4, 97-132 (1995) · Zbl 0833.05030 · doi:10.1017/S0963548300001528
[40] Kim, Jeong Han, The {R}amsey number {\(R(3,t)\)} has order of magnitude {\(t^2/\log t\)}, Random Structures Algorithms. Random Structures & Algorithms, 7, 173-207 (1995) · Zbl 0832.05084 · doi:10.1002/rsa.3240070302
[41] Krivelevich, Michael, Triangle factors in random graphs, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 6, 337-347 (1997) · Zbl 0886.05101 · doi:10.1017/S0963548397003106
[42] K\"{u}hn, Daniela; Osthus, Deryk, Hamilton decompositions of regular expanders: a proof of {K}elly’s conjecture for large tournaments, Adv. Math.. Advances in Mathematics, 237, 62-146 (2013) · Zbl 1261.05053 · doi:10.1016/j.aim.2013.01.005
[43] Lov{\'a}sz, L., Subgraphs with prescribed valencies, J. Combin. Theory. Journal of Combinatorial Theory, 8, 391-416 (1970) · Zbl 0198.29201 · doi:10.1016/S0021-9800(70)80033-3
[44] Molloy, Michael; Reed, Bruce, Near-optimal list colorings. Proceedings of the {N}inth {I}nternational {C}onference “{R}andom {S}tructures and {A}lgorithms”, Random Structures Algorithms. Random Structures & Algorithms, 17, 376-402 (2000) · Zbl 0971.05047 · doi:url = {https://doi.org/cbwx5v
[45] Molloy, Michael; Reed, Bruce, Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, 23, xiv+326 pp. (2002) · Zbl 0987.05002 · doi:10.1007/978-3-642-04016-0
[46] Pippenger, Nicholas; Spencer, Joel, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 51, 24-42 (1989) · Zbl 0729.05038 · doi:10.1016/0097-3165(89)90074-5
[47] R\"{o}dl, Vojt\v{e}ch, On a packing and covering problem, European J. Combin.. European Journal of Combinatorics, 6, 69-78 (1985) · Zbl 0565.05016 · doi:10.1016/S0195-6698(85)80023-8
[48] R\"{o}dl, Vojt\v{e}ch; Ruci\'{n}ski, Andrzej; Szemer\'{e}di, Endre, A {D}irac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 15, 229-251 (2006) · Zbl 1082.05057 · doi:10.1017/S0963548305007042
[49] Schrijver, Alexander, Combinatorial Optimization. {P}olyhedra and Efficiency. {V}ol. {A}, Algorithms and Combinatorics, 24, xxxviii+647 pp. (2003) · Zbl 1041.90001
[50] Seymour, P. D., Packing nearly disjoint sets, Combinatorica. Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society, 2, 91-97 (1982) · Zbl 0494.05015 · doi:10.1007/BF02579285
[51] Tutte, W. T., The factorization of linear graphs, J. London Math. Soc.. The Journal of the London Mathematical Society, 22, 107-111 (1947) · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107
[52] Vizing, V. G., The chromatic class of a multigraph, Cybernetics. Cybernetics and Systems Analysis, 1, 32-41 (1965) · doi:10.1007/BF01885700
[53] Vu, Van H., A general upper bound on the list chromatic number of locally sparse graphs, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 11, 103-111 (2002) · Zbl 0991.05041 · doi:10.1017/S0963548301004898
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.