✦ LIBER ✦

Near-optimal list colorings

✍ Scribed by Michael Molloy; Bruce Reed

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 223 KB
Volume: 17
Category: Article
ISSN: 1042-9832
DOI: 10.1002/1098-2418(200010/12)17:3/4<376::aid-rsa10>3.0.co;2-0

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Oriented list colorings of graphs

✍ Zs. Tuza; M. Voigt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB 👁 1 views

A 2-assignment on a graph G (V,E) is a collection of pairs Lv of allowed colors speci®ed for all vertices v PV. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satis®es the following property: For every 2-assignment there exists a choic

A note on list-colorings

✍ Amanda Chetwynd; Roland Häggkvist 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

In this article we discuss the current results on the list chromatic conjecture and prove that if G is a triangle free graph with maximum degree A then xi(G) 5 9A/5. If the term "a classic" can be used about a mathematical problem less than 10 years old, then surely the following question by Jeff D

List colorings with measurable sets

✍ Jan Hladký; Daniel Kráal; Jean-Sébastien Sereni; Michael Stiebitz 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

## Abstract The measurable list chromatic number of a graph __G__ is the smallest number ξ such that if each vertex __v__ of __G__ is assigned a set __L__(__v__) of measure ξ in a fixed atomless measure space, then there exist sets $c(v)\subseteq L(v)$ such that each __c__(__v__) has measure one an

On the number of list-colorings

✍ Quentin Donner 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract Given a __list of boxes L__ for a graph __G__ (each vertex is assigned a finite set of colors that we call a box), we denote by __f__(__G, L__) the number of L‐__colorings__ of __G__ (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and

A lower bound for partial list colorings

✍ Chappell, Glenn G. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

Let G be an n-vertex graph with list-chromatic number χ . Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least t n /χ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a coroll

List Colorings of K5-Minor-Free Graphs W

List Colorings of K5-Minor-Free Graphs With Special List Assignments

✍ Daniel W. Cranston; Anja Pruchnewski; Zsolt Tuza; Margit Voigt 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

The following question was raised by Bruce Richter. Let G be a planar, 3-connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L-list colorable for every list assignment L with |L(v)|=min{d(v), 6} for all v ∈ V (G)? More generally, we ask for which pairs (r, k)