Edge‐coloring linear hypergraphs with medium‐sized edges

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 Ci,ϵn inclusive, then there is a list edge coloring using (1+ϵ)ni−1 colors. The dependence on n in the upper...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2019-08, Vol.55 (1), p.153-159
Main Authors: Faber, Vance, Harris, David G.
Format: Article
Language:English
Subjects:
chromatic index
Coloring
Dependence
EFL
Graph theory
linear hypergraph
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Ci,ϵn inclusive, then there is a list edge coloring using (1+ϵ)ni−1 colors. The dependence on n in the upper bound is optimal (up to the value of Ci,ϵ).
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20843