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].
References:
[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.,
Send comments to dan.archdeacon@uvm.edu
PUT DATE HERE