Premium
Edge‐coloring linear hypergraphs with medium‐sized edges
Author(s) -
Faber Vance,
Harris David G.
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20843
Subject(s) - combinatorics , edge coloring , conjecture , enhanced data rates for gsm evolution , mathematics , bounded function , upper and lower bounds , value (mathematics) , discrete mathematics , computer science , graph , artificial intelligence , statistics , mathematical analysis , line graph , graph power
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 , ϵninclusive, then there is a list edge coloring using ( 1 + ϵ ) n i − 1colors. The dependence on n in the upper bound is optimal (up to the value of C i , ϵ ).