论文标题:关于图的可选择性与唯一列表可染图研究
Research on Choosability of Graphs and Uniquely List Colorable Graphs
论文作者
论文导师 何文杰,论文学位 博士,论文专业 基础数学
论文单位 河北师范大学,点击次数 112,论文页数 123页File Size4637k
2006-04-12论文网 http://www.lw23.com/lunwen_24409562/
List colorings;k-choosable graphs;Choice number;k-edge-choosable graphs;Edge-choice number;Chromatic-choosable graphs;Ohba"s conjecture;Complete multipartite graphs;(k, l)-choosable graphs;(k,l )-edge-choosable graphs;Planar graphs;Unique list colorings;Uniquely k-list colorable graphs;Property M(k)
本文研究列表染色的若干问题,包括图的色-可选择性和Ohba猜想、某些平面图的(k,l)-可选择性和(k,l)-边-可选择性,以及图(尤其是完全多部图)的唯一列表可染性。 如果图G满足Ch(G)=x(G),则称G是色-可选择的。关于图的色-可选择性,2002年Ohba[71]给出猜想:如果图G满足|V(G)|≤2x(G)+1,则G是色-可选择的。容易发现Ohba猜想成立当且仅当其对完全多部图成立,但是对完全多部图Ohba猜想被验证的情况只有图K_(3*2,2*(k-3),1)、K_(3,2*(k-1))和K_(t+3,2*(k-t-1),1*t)。本文证明:完全多部图K_(t+2,3,2*(k-t-2)),1*t)(t=2,3,4;k≥t+2)是色-可选择图。因此得到,对图K_(t+2,3,2*(k-t-2),1*t)(t=1,2,3,4;k≥t+2)及其所有k-色子图Ohba猜想成立。对独立数最大为3的图,2004年Ohba[72]证明了Ohba猜想的一个较弱的形式:如果图G满足|V(G)|≤2x(G),且G的独立数最大为3,则G是色-可选择的。在此我们证明:若r≤t+1且k≥r+t,则Ch(K_(3*r,2*(k-r-t),1*t))=x(K_(3*r,2*(k-r-t),1*t))=k。此结果表明:在如上Ohba的论断中,条件|V(G)|≤2x(G)可以换成|V(G)|≤2x(G)+1。即对每个独立数最大为3的图及其所有x(G)-色子图Ohba猜想成立。 图的(k,l)-可选择性问题是图的k-可选择性问题的推广。关于图的(k,l)-可选择性,1979年Erd(?)s等人[26]提出了如下猜想:对任意整数m≥1,每一个(k,l)-可选择的图G也是(km,lm)-可选择的。1996年Tuza和Voigt[94]证明了这个猜想在k=2和l=1的情形是正确的,但是对任意的(k,l)验证这个猜想的工作还相差甚远。本文证明:对任意整数m≥1,每一个没有t-圈(t=3,4,5或6)的平面图是(4m,m)-可选择的。这一结果推广了分别由Lam等人[65]、由Wang和Lih[106]、由Fijav(?)等人[28]给出的如上图都是4-可选择的结果。另一方面,我们还证明:如果一个平面图G不包含t-圈(t=3,4,5或6)且△(G)≠4,
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_3*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.
|
