Bounds on Erdos - Faber - Lovász conjecture - the uniform and regular cases

Suresh M. Hegde, Suresh Dara

Abstract


We consider the Erds - Faber - Lovász (EFL) conjecture for hypergraphs. This paper gives an upper bound for the chromatic number of r regular linear hypergraphs H of size n. If r ≥ 4, χ(H)≤1.181n and if r = 3, χ(H)≤1.281n.

Keywords


hypergraphs; chromatic number; Erdos - Faber - Lovász conjecture

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2025.13.1.8

References

C. Berge, On two conjectures to generalize Vizing’s theorem, Matematiche (Catania), 45(1) (1990), 15–23.

W.I. Chang and E.L. Lawler, Edge coloring of hypergraphs and a conjecture of Erdös, Faber, Lovász, Combinatorica, 8(3) (1988), 293–295.

P. Erds, Problems and results in graph theory and combinatorial analysis, Proc. British Combinatorial Conj., 5th, (1975), 169–192.

P. Erds, On the combinatorial problems which I would most like to see solved, Combinatorica, 1 (1981), no. 1, 25–42.

V. Faber, The Erdos-Faber-Lovász conjecture—the uniform regular case, J. Comb., 1(2) (2010), 113–120.

V. Faber, Linear hypergraph edge coloring - generalizations of the EFL conjecture, Bulletin of Mathematical Sciences and Applications, 17 (2016), 1–9.

S.M. Hegde and S. Dara, Further results on Erds–Faber–Lovász conjecture, AKCE Int. J. Graphs Comb., 17(1) (2020), 614–631.

B. Jackson, G. Sethuraman, and C. Whitehead, A note on the Erdos-Farber-Lovász conjecture, Discrete Math., 307(7-8) (2007), 911–915.

J. Kahn, Coloring nearly-disjoint hypergraphs with n + o(n) colors, J. Combin. Theory Ser. A, 59(3) (1992), 31–39.

V. Paul and K.A. Germina, On edge coloring of hypergraphs and Erdös-Faber-Lovász conjecture, Discrete Math. Algorithms Appl., 4(1) (2012), 1250003.

R. Zhang and F.M. Dong, Problems on chromatic polynomials of hypergraphs, Electron. J. Graph Theory Appl., 8(2) (2020), 241–246.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats