The List Coloring Of The Bipartite Graphs

The notation of list coloring is a generalization of the notation of coloring ofgraph and has very di?erences from it. The major problem of the list coloring isto determine the choice number for a graph. However, it seems difficult to do,even for the bipartite graphs. In this thesis, we concentrate on the choosabilityof the bipartite graphs. N.Alon in [8] prove, by algebraic method, that every bipartite graph G is( L(G) + 1)-choosable. This implies that bipartite graph G is ((G)/2 + 1)-choosable. Qiongxiang Huang and Guoping Wang in [7], also by algebraicmethod, prove that every bipartite graph G is f-choosable, where f(u) = ([d(u)]/2+1) ( u ∈ V (G)), which also deduces that G is ((G)/2+ 1)-choosable and is animprovement of above result in [8]. Following their investigations, we first con-sider the complete bipartite graphs. By introducing the notation of colour-degreeand applying the graphic method, we show that K2 d,2d(d 3)is d-choosable andfurther prove that every bipartite graph G is (G)/2 -choosable, if (G) 6,which is another improvement of the bounds for the choosability of the bipartitegraphs in [8]. In 1979, Erd(o|¨)os, Rubin and Taylor in [2] classified the 2-choosable graphs.However, the 3-choosable graphs have not been classified, even if 3-choosablebipartite graphs. There are a few of results related it (to see [4] and [5]) andit seems difficult to completely classify them, even if the 3-choosable completebipartite graphs. Therefore, we have to consider a weak problem, that is, toclassify the (2,3)-choosable complete bipartite graphs. We prove that K3,7 , K8 ,2,star, K2,n (n 1) and Km,n (m + n 9 and m = 5 when n = 4) are all(2,3)-choosable complete bipartite graphs. Thus the (2,3)-choosable completebipartite graphs are completely characterized here, which, we consider, will beIIuseful in the further research of the 3-choosable bipartite graphs.