Research ArticleOpen AccessGoogle Scholar indexed
The Erdös-Faber-Lovász Conjecture for Gap-Restricted Hypergraphs
School of Mathematics and Statistics, Shandong Normal University, Jinan, China
- 1 School of Mathematics and Statistics, Shandong Normal University, Jinan, China
Copy link · social · email
Abstract
An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromat ic index of H and is denoted by . Erd ö s, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap- restricted hypergraphs. Our result extends a result of Alesandroni in 2021.
KeywordsLinear HypergraphChromatic IndexErdös-Faber-Lovász ConjectureEdge Cardinality
- Erdos, P. (1981) On the Combinatorial Problems Which I Would Most Like to See Solved. Combinatorica, 1, 25-42. https://doi.org/10.1007/BF02579174
- Chang, W.I. and Lawler, E.L. (1988) Edge Coloring of Hypergraphs and a Conjecture of Erdos, Faber, Lovász. Combinatorica, 8, 293-295. https://doi.org/10.1007/BF02126801
- Seymour, P. (1982) Packing Nearly-Disjoint Sets. Combinatorica, 2, 91-97. https://doi.org/10.1007/BF02579285
- Kahn, J. and Seymour, P.D. (1992) A Fractional Version of the Erdos-Faber-Lovász Conjecture. Combinatorica, 12, 155-160. https://doi.org/10.1007/BF01204719
- Kahn, J. (1992) Coloring Nearly-Disjoint Hypergraphs with n + o(n) Colors. Journal of Combinatorial Theory, Series A, 59, 31-39. https://doi.org/10.1016/0097-3165(92)90096-D
- Sánchez-Arroyo, A. (2008) The Erdos-Faber-Lovász Conjecture for Dense Hypergraphs. Discrete Mathematics, 308, 991-992. https://doi.org/10.1016/j.disc.2007.09.026
- Romero, D. and Alonso-Pecina, F. (2014) The Erdos-Faber-Lovász Conjecture Is True for n ≤ 12. Discrete Mathematics, Algorithms and Applications, 6, Article ID: 1450039. https://doi.org/10.1142/S1793830914500396
- Faber, V. and Harris, D. (2019) Edge-Coloring Linear Hypergraphs with Medium- Sized Edges. Random Structures & Algorithms, 55, 153-159. https://doi.org/10.1002/rsa.20843
- Bretto, A., Faisant, A. and Hennecart, F., (2020) On Hyperedge Coloring of Weakly Trianguled Hypergraphs and Well Ordered Hypergraphs. Discrete Mathematics, 343. https://doi.org/10.1016/j.disc.2020.112059
- Alesandroni, G. (2021) The Erdos-Faber-Lovász Conjecture for Weakly Dense Hypergraphs. Discrete Mathematics, 344. https://doi.org/10.1016/j.disc.2021.112401
- Kang, D., Kelly, T., Kühn, D., Methuku, A. and Osthus, D. (2023) A Proof of the Erdos-Faber-Lovász Conjecture. Annals of Mathematics, 198, 537-618. https://doi.org/10.4007/annals.2023.198.2.2
- Wang, Q. and Zhang, X. (2023) A Note on Edge Coloring of Linear Hypergraphs. Journal of Mathematical Research with Applications, 43, 535-541.