Edge‐coloring linear hypergraphs with medium‐sized edges. Issue 1 (1st March 2019)

• Record Type: Journal Article
• Authors: Faber, Vance; Harris, David G.
• Is Part Of: Random structures & algorithms. Volume 55:Issue 1(2019)
• Page Start: 153
• Page End: 159
• Publication Date: 2019-03-01
• Subjects: chromatic index -- EFL -- linear hypergraph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20843
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Motivated by the Erdos̋‐Faber‐Lovász (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We show that if the hyper‐edge sizes are bounded between i and C i, ϵ n inclusive, then there is a list edge coloring using ( 1 + ϵ ) n i − 1 colors. The dependence on n in the upper bound is optimal (up to the value of C i, ϵ ).