Multiple List Coloring And Multiple On-line List Coloring Of Graphs

In this paper, we study some problems in multiple list coloring and multiple on-line list coloring of graphs. A b-tuple coloring of graph G is a mapping S, which maps each vertex v of G to an integer set S(v) with b integers, such that S(u) ∩ S(v)=(?) for every two adjacent vertices u and v. An a-list assignment of graph G is a mapping L, which assigns an integer set L(v) with a integers to each vertex v of G. We say graph G is (a:b)-choosable, if for every a-list assignment L of G, there exists a b-tuple coloring S such that S(v) ∈ L(v). In 1979, Erdos, Rubin, Taylor characterized all (2:1)-choosable graphs. Tuza and Voigt proved that all (2:1)-choosable graphs are (2m:m)-choosable graphs for every integer m. However, for m≥2, characterizing all (2m:m)-choosable graphs remains an open problem.In this paper, we characterize all (4:2)-choosable 3-choice-critical graphs, and pro-pose a conjecture to characterize all (4:2)-choosable graphs. On-line (a:b)-choosable is an on-line version of (a:b)-choosable. We characterize all on-line (2m:m)-choosable graphs, and we determine the b-tuple choice number of K2,4 and odd cycles. Finally, we prove the on-line list version of Brooks’ Theorem, and study the concepts of multiple list ranking coloring and multiple on-line list ranking coloring of graphs.