✦ LIBER ✦

On a list coloring conjecture of Reed

✍ Scribed by Tom Bohman; Ron Holzman

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 54 KB
Volume: 41
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10054

No coin nor oath required. For personal study only.

✦ Synopsis

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–109, 2002

📜 SIMILAR VOLUMES

A list analogue of equitable coloring

✍ A. V. Kostochka; M. J. Pelsmajer; D. B. West 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a __list coloring__ is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is __equitable__ if each color appears on at mo

A conjecture of Borodin and a coloring o

A conjecture of Borodin and a coloring of Grünbaum

✍ Dieter Rautenbach 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every __k__ color classes with 1 ≤ __k__ ≤ 4 induces a (__k__—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139

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-coloring the square of a subcubic g

List-coloring the square of a subcubic graph

✍ Daniel W. Cranston; Seog-Jin Kim 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 1 views

## Abstract The __square__ __G__^2^ of a graph __G__ is the graph with the same vertex set __G__ and with two vertices adjacent if their distance in __G__ is at most 2. Thomassen showed that every planar graph __G__ with maximum degree Δ(__G__) = 3 satisfies χ(__G__^2^) ≤ 7. Kostochka and Woodall c

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

Acyclic list 7-coloring of planar graphs

✍ O. V. Borodin; D. G. Fon-Der Flaass; A. V. Kostochka; A. Raspaud; E. Sopena 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views