✦ LIBER ✦

A note on list-colorings

✍ Scribed by Amanda Chetwynd; Roland Häggkvist

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 384 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130112

No coin nor oath required. For personal study only.

✦ Synopsis

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 Dinitz deserves that epithet:

Dinitz's Problem. Given an m X m array of m-sets, is it always possible to choose one element from each set, keeping the chosen elements distinct in every row and distinct in every column.

This particular formulation of the problem can be found in a paper by Erdos, Rubin and Taylor [4], where those authors, inspired by Dinitz's problem, investigate a natural generalization they term "choosability": Let an adversary assign to each vertex j in a graph G on the vertices 1,2, . . . , n a set off(j) symbols, the functionfchosen by us in advance. Then G is said to bef-choosable if, no matter what symbols the adversary puts down, we can always make a choice consisting of one symbol from each vertex, with distinct symbols on adjacent vertices. In particular, if f(j) = k for each vertex we say that G is k-choosable.

The paper [4] contains a number of facts about this concept. In summary, the authors characterize the 2-choosable graphs completely, estimate the choice number for a random bipartite graph (the choice number for G is the minimum k for which G is k-choosable), determine the choice number for the comple-

📜 SIMILAR VOLUMES

A note on group colorings

✍ Daniel Král'; Ondřej Pangrác; Heinz-Jürgen Voss 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB

## Abstract We study a concept of group coloring introduced by Jaeger et al. We show that the group chromatic number of a graph with minimum degree δ is greater than δ/(2, ln δ) and we answer several open questions on the group chromatic number of planar graphs: a construction of a bipartite planar

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 Note on List Arboricity

✍ P.D. Seymour 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 181 KB

We show that, for any graph or matroid, its ``arboricity'' and its ``list arboricity'' are equal. ## 1998 Academic Press A celebrated recent theorem of Galvin [2] asserts that for any bipartite graph, its chromatic index and its list-chromatic index are equal. This can be formulated as a property

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

Near-optimal list colorings

✍ Michael Molloy; Bruce Reed 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB

A note on defective colorings of graphs

A note on defective colorings of graphs in surfaces

✍ Dan Archdeacon 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 2 views

A graph is (rn, k)-colorable if its vertices can be colored with rn colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. In a recent paper Cowen. Cowen, and Woodall proved that, for each compact surface S, there exists an integer k = k(S) such that eve