Linear Hypergraph Edge Coloring - Generalizations of the EFL Conjecture

Faber, Vance

doi:10.18052/www.scipress.com/BMSA.17.1

BMSA > Volume 17 > Linear Hypergraph Edge Coloring - Generalizations...

< Back to Volume

Linear Hypergraph Edge Coloring - Generalizations of the EFL Conjecture

Full Text PDF

Abstract:

Motivated by the Erdos-Faber-Lová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.

Info:

Periodical:

Bulletin of Mathematical Sciences and Applications (Volume 17)

Pages:

1-9

DOI:

https://doi.org/10.18052/www.scipress.com/BMSA.17.1

Citation:

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:

November 2016

Authors:

Vance Faber

Keywords:

Edge Coloring, EFL, Hypergraph

Export:

RIS, BibTeX, Text

Distribution:

Open Access

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

References:

[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: https://doi.org/10.4310/joc.2010.v1.n2.a2

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

DOI: https://doi.org/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: https://doi.org/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

Cited By:

This article has no citations.