✦ LIBER ✦
Coloring graphs from lists with bounded size of their union
✍ Scribed by Daniel Král'; Jiří Sgall
- Publisher
- John Wiley and Sons
- Year
- 2005
- Tongue
- English
- Weight
- 103 KB
- Volume
- 49
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,ℓ)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with $|\bigcup_{{\nu}\in V(G)}, L(\nu)|\le \ell$. For each 3 ≤ k ≤ ℓ, we construct a graph G that is (k,ℓ)‐choosable but not (k,ℓ + 1)‐choosable. On the other hand, it is proven that each (k,2__k__ − 1)‐choosable graph G is O(k · ln k · 2^4__k__^)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory