Subscribe to our Newsletter and get informed about new publication regulary and special discounts for subscribers!

BMSA > Volume 17 > Linear Hypergraph Edge Coloring - Generalizations...
< Back to Volume

Linear Hypergraph Edge Coloring - Generalizations of the EFL Conjecture

Full Text PDF


Motivated by the Erdos-Faber-Lovász (EFL) conjecture for hypergraphs, we consider the edge coloring of linear hypergraphs. We discuss several conjectures for coloring linear hypergraphs that generalize both EFL and Vizing's theorem for graphs. For example, we conjecture that in a linear hypergraph of rank 3, the edge chromatic number is at most 2 times the maximum degree unless the hypergraph is the Fano plane where the number is 7. We show that for fixed rank sufficiently large and sufficiently large degree, the conjectures are true.


Bulletin of Mathematical Sciences and Applications (Volume 17)
V. Faber "Linear Hypergraph Edge Coloring - Generalizations of the EFL Conjecture", Bulletin of Mathematical Sciences and Applications, Vol. 17, pp. 1-9, 2016
Online since:
Nov 2016

[1] Hypergraph Seminar (C. Berge and D. Ray-Chaudhuri, eds. ), Vol 411, Lecture Notes in Mathematics, New York, (1974).

[2] V. Faber, The Erdős-Faber-Lovász conjecture – the uniform regular case, J. Combinatorics, 1(2) (2010) 113-120.

DOI: 10.4310/joc.2010.v1.n2.a2

[3] C. Berge, Hypergraphs: Combinatorics of Finite Sets, Vol. 45, North-Holland Mathematical Library, (1989).

DOI: 10.1016/s0924-6509(08)70096-5

[4] P. Erdős, V. Faber, F. Jones, Projective -designs, J. Stat. Plan. Inference. 7 (1982) 181-191.

[5] N. Alon, M. Krivelevich, B. Sudakov, Coloring graphs with sparse neighborhoods, J. Comb. Theory, B. 77(1) (1999) 73-82.

DOI: 10.1006/jctb.1999.1910

[6] A. Sánchez-Arroyo, The Erdős-Faber-Lovász conjecture for dense hypergraphs, Discrete Mathematics. 308(5-6) (2008) 991-992.

[7] L. Lovász, On minimax theorems of combinatorics (in Hungarian), Mat. Lapok. 26 (1975) 209-264.

Show More Hide