Informace o publikaci
Coloring graphs from lists with bounded size of their union
| Autoři | |
|---|---|
| Rok publikování | 2005 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Graph Theory |
| Citace | |
| Doi | http://dx.doi.org/10.1002/jgt.20073 |
| Klíčová slova | graph coloring; list coloring |
| Popis | A graph G is k-choosable if its vertices can be colored from any lists L(v) of colors with vertical bar L(v)vertical bar >= k for all v is an element of V(G). A graph G is said to be (k,l)-choosable if its vertices can be colored from any lists L(v) with vertical bar L(v)vertical bar >= k, for all v is an element of V(G), and with vertical bar U-v is an element of V(G) L(v)vertical bar <= l. For each 3 <= k <= l, we construct a graph G that is (k,f)-choosable but not (k,l+1)-choosable. On the other hand, it is proven that each (k, 2k-1)-choosable graph G is O(k (.) In k - 2(4k))-choosable. (c) 2005 Wiley Periodicals, Inc. |