Research On Choosability Of Graphs And Uniquely List Colorable Graphs

Several problems on list colorings, including chromatic-choosability of graphs and Ohba's conjecture, (k, l)-choosability and (k, l)-edge-choosability of some planar graphs, and unique list colorability of graphs, especially for complete multipartite graphs, have been studied in this thesis.A graph G is called chromatic-choosable if Ch(G) = x(G). For the choosability of graphs, in 2002 Ohba [71] conjectured that every graph G with 2x(G) + 1 or fewer vertices is chromatic-choosable. It is easy to see that Ohba's conjecture holds if and only if it holds for complete multipartite graphs. But for complete multipartite graphs, the graphs for which Obha's conjecture has been verified are nothing more than K_{3*2,2*(k-3),1,}K_3,2*(k-1)and K_{t+3.2*(k-t-1),1*t} In this thesis we show that graphs K_{t+2,3,2*(k-t-2),1*t} (t = 2,3,4;k≥ t + 2) are chromatic-choosable. Hence Ohba's conjecture holds for K_{t+2,3,2*(k-t-2),1*t} (t =1,2,3,4;k ≥ t + 2) and all k-chromatic subgraphs of them. For the graphs with independence number at most three, as a weaker version of Ohba's conjecture, Ohba [72] proved that if G is a graph with |V(G)| < 2x(G) and the independence number of G is at most 3, then G is chromatic-choosable. Here we prove C_h(K_{3*r,2*(k-r-t),1*t}) = X(K₃*r,i2*(k-r-t),1*t)) = k, where r ≤ t + 1 and k ≥ r +t. This result implies that in the above assertion given by Ohba, the condition |V(G)| < 2x(G) can be replaced by |V(G)| < 2x(G) + 1. Namely, Ohba's conjecture holds for every graph G with independence number at most three and all x(G)-chromatic subgraphs of G.The (k, l)-choosability is a more general setting for k-choosability. For (k, l)-choosability, in 1979 Erdos et al. [26] raised the conjecture that every (k, l)-choosable graph G is also (km, lm)-choosable for all integer m≥ 1. In 1996 Tuza and Voigt [94] showed the above conjecture is true if k = 2 and l = 1. The general proof for all pairs (k, l), however, still seems to be far beyond reach. In this thesis we prove that every planar graph without t-cycle (t = 3,4, 5 or 6) is (4m, m)-choosable for all integer m ≥ 1, generalizing the results that the above graphs are 4-choosable shown by Lam et al. [65] by Wang and Lih [106], and by Fijavz et al. [28], respectively. On the other hand, we also prove that every planar graph G without t-cycle (t = 3,4,5 or 6) and with Δ(G) ≠ 4 is (sm, m)-edge-choosable for all integer m ≥ 1,where s = A(G) + 1 if t {3,4,5}, or t = 6 but A(G) 5;s = 7 if t = 6 and A(G) = 5. These results generalize the results that every planar graph G without i-cycle (t = 3,4, 5 or 6) is (A(G) + l)-edge-choosable given by Wang and Lih [105, 106], by Zhang and Wu [114], and by Wang [117], respectively, except for the case A(G) = 4, and the case t = 6 and A(G) = 5. Moreover, as a consequence of our main result we obtain that every planar graph G without 4-cyele is (A(G) + l)-edge-choosable, which also improves the result given by Zhang and Wu: every planar graph G without 4-cycles is s-edge-choosable, where s = A(G) + 1 if A(G) ^ 5;s - 7 if A(G) = 5.A graph G is called uniquely A:—list colorable, or UkLC for short, if it admits a /c-list assignment L such that G has a unique L-coloring. In 1999 Mah-dian and Mahmoodian [67] characterized the U2LC graphs. In 2001 Ghebleh and Mahmoodian [32] extensively studied the unique list colorability for complete multipartite graphs, especially for U3LC complete multipartite graphs. They characterized the J73LC graphs for complete multipartite graphs except for nine graphs. At the same time, for the nine exempted graphs they give an open problem: verify all the graphs K^^r for r = 4,5,..., 8, 1^2,3,4) â– ^1*4,4) -Ki*4,5> and ^1*5,4 not being UZLC. In 2004 Zhao et al. [115] showed that graph i^2,3,4 is not U3LC. In this thesis we provide a simple proof for the theorem of characterizing the U2LC graphs. And we show that all the graphs K2l2,r for r = 4,5,.... 8,1^1*4,4, 1*4,5, and 1*5,4 are not UZLC. As a result, the U3LC complete multipartite graphs are completely characterized.