List  Edge-Colorings and List  Total-Colorings

A list-assignment L gives a list of colors available at each vertex. Commonly the size k of the list is independent on the vertices, and we talk about a k-list assignment. An L-coloring assigns each vertex one of the colors in its list. Usually we want proper colorings, so that adjacent vertices receive distinct colors. The list-chromatic number is the smallest k such that every k-list assignment L has a proper L-coloring. Obviously, the list chromatic number is greater than or equal to the chromatic number, since the latter is the special case that all vertices get lists 1,...,k.

We are concerned here with the edge-coloring analog, called the list-chromatic index and it's relation to the chromatic index (also known as the edge-chromatic number). Here the edges are assigned lists of colors, and adjacent edges are to receive distinct colors from their lists.  The following conjecture is due to Vizig, to Gupta, and to Albertson and Collins.

Conjecture: For every multigraph, the list list-chromatic index is equal to the chromatic index.

Galvin [G] has shown that the conjecture is true for bipartite multigraphs.

A claw is an induced K_{1,3}. A graph is claw-free if it contains no claw. Every line graph is claw-free, so the following conjecture generalizes the list-edge-coloring conjecture.

Conjecture: [GM] Every claw-free graph has the list-chromatic number equal to the chromatic number.

A total list-coloring assigns lists of colors to both vertices and edges, with the stipulation that in a proper coloring has both adjacent and incident items colored differently. The following is reportedly due almost simultaneously to Borodin, Kostochka and Woodall, to Juvan Mohar and Skrekovski, and to Hilton and Johnson.

Conjecture: Every multigraph has it's total list-chromatic number equal to its total chromatic number.

A very good survey on list colorings is given by Woodall [W].


[HC] R. Haggkvist and A. Chetwynd, Some upper bounds on the total and list chromatic number of multigraphs, J. Graph Theory 16 (1992) 503-516

[G] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63 (1995) 155-158.
[GM]  S. Gravier and F. Maffray, Graphs whose choice number is equal to their chromatic number, J. Graph Theory 27 (1998) 87-97.

[W] D.R. Woodall, List colourings of graphs, 269-301

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to