THE LIST CHROMATIC INDEX OF A BIPARTITE MULTIGRAPH

摘要

For a bipartite multigraph, the list chromatic index is equal to the chromatic index (which is, of course, the same as the maximum degree). This generalizes Janssen's result on complete bipartite graphs K-m,K-n with m not equal n; in the case of K-n,K-n, it answers a question of Dinitz. (The list chromatic index of a multigraph is the least number n for which the edges can be colored so that adjacent edges get different colors, the color of each edge being chosen from an arbitrarily prescribed list of n different colors associated with that edge.) (C) 1995 Academic Press, Inc. [References: 9]