𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of a restricted list-coloring problem

✍ Scribed by Moshe Dror; Gerd Finke; Sylvain Gravier; Wieslaw Kubiak

Book ID
108316282
Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
355 KB
Volume
195
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On a list coloring conjecture of Reed
On a list coloring conjecture of Reed
✍ Tom Bohman; Ron Holzman πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 54 KB

## Abstract We construct graphs with lists of available colors for each vertex, such that the size of every list exceeds the maximum vertex‐color degree, but there exists no proper coloring from the lists. This disproves a conjecture of Reed. Β© 2002 Wiley Periodicals, Inc. J Graph Theory 41: 106–10

On the list dynamic coloring of graphs
On the list dynamic coloring of graphs
✍ S. Akbari; M. Ghanbari; S. Jahanbekam πŸ“‚ Article πŸ“… 2009 πŸ› Elsevier Science 🌐 English βš– 317 KB
The complexity of the T-coloring problem
The complexity of the T-coloring problem for graphs with small degree
✍ Krzysztof Giaro; Robert Janczewski; MichaΕ‚ MaΕ‚afiejski πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 194 KB

In the paper we consider a generalized vertex coloring model, namely T -coloring. For a given ΓΏnite set T of nonnegative integers including 0, a proper vertex coloring is called a T -coloring if the distance of the colors of adjacent vertices is not an element of T . This problem is a generalization