Edge‐coloring linear hypergraphs with medium‐sized edges
| Autor: | David G. Harris, Vance Faber |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
List edge-coloring
Mathematics::Combinatorics Conjecture Applied Mathematics General Mathematics 0102 computer and information sciences 01 natural sciences Computer Graphics and Computer-Aided Design Upper and lower bounds Combinatorics Edge coloring Computer Science::Discrete Mathematics 010201 computation theory & mathematics Bounded function Value (mathematics) Software Mathematics |
| Zdroj: | Random Structures & Algorithms. 55:153-159 |
| ISSN: | 1098-2418 1042-9832 |
| DOI: | 10.1002/rsa.20843 |
| Popis: | Motivated by the Erd\H{o}s-Faber-Lov\'{a}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,\epsilon} \sqrt{n}$ inclusive, then there is a list edge coloring using $(1 + \epsilon) \frac{n}{i - 1}$ colors. The dependence on $n$ in the upper bound is optimal (up to the value of $C_{i,\epsilon}$). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text