论文标题:一些完全多部图唯一列表可染性的特征化
A Characterization of Uniquely List Colorable for Some Complete Multipartite Graphs
论文作者 孙书刚
论文导师 何文杰,论文学位 硕士,论文专业 应用数学
论文单位 河北工业大学,点击次数 788,论文页数 36页File Size1223k
2005-05-01论文网 http://www.lw23.com/lunwen_64497/ 完全多部图;列表染色;UkLC图;M(3)性质;ch(G);m(G)
complete multipartite graph; list coloring; UkLC graph;property M(3); ch(G); m(G)
图的染色问题是图论的主要研究课题之一,它包括列表染色、T染色、集合染色、n元数组染色等,其中列表染色是通常染色的推广,近年来颇受人们的关注,并且在唯一k列表可染、m数、选择数等方面已经取得了许多成果。列表染色的概念最早由V.G.Vizing和P.Erdos,A.L.Rubin,H.Taylor分别独立地提出,它与普通染色概念的区别在于,事先给图G的每一个顶点u关联一个颜色列表L(v),在给图G染色的时候,每个顶点的颜色必须在它所关联的颜色列表中选择,如果在此条件下,图G存在一个正常染色,则称图G是列表可染色的;如果存在唯一列表染色,则称G是唯一列表可染的,唯一列表染色这个概念由E.S.Mahmoodian和M.Mahdian首次提出。令G是一个阶为n的图,如果对G的每个顶点u,存在一个有k个颜色的颜色列表L(v)(k称为颜色列表的长度),使得G有一个唯一列表染色,则称图G是一个唯一k列表可染色图,简记为UkLC图,UkLC这个概念最早由E.S.Mahmoodian和M.Mahdian提出。2001年M.Ghebleh和E.S.Mahmoodian针对完全多部图这一重要图类,除了其中9个图,特征化了U3LC图;同时他们对这9个图提出了开放问题:查证图K_(2,2,r),r=4,5,…,8,K_(2,3,4) ,K_(1*4,4) ,K_(1+4,5) 和K_(1*5,4) 具有M(3) 性质。本人主要证明了图K_(2,2,r),r=4,5,6,7,具有M(3) 性质。
A coloring of a graph is one of the most important topics in graph theory, it consists of list coloring, T-coloring, set coloring, n-tuple coloring and etc. List coloring is a generalization of normal vertex coloring of a graph, it has attracted much more attention, a lot of results about uniquely k-list colorable, m-number and choice number about a graph have been obtained.List coloring was introduced originally by V. G. Vizing and independly by P. Erdos, A. L. Rubin and H. Taylor. The diffrence between list coloring and normal coloring is produced as follows, for each vertex uina graph G, let L(v) denote a list of colors available for v. A list coloring from the given collection of lists is a proper coloring c such that c(v) is chosen from L(v), we will refer to such a coloring as an L-coloring. If there exists a unique L-coloring, then we call such a coloring as an unique L-coloring. Unique List coloring was introduced by E. S. Mahmoodian and M. Mahdian. Let G be a graph with n vertices and suppose that for each vertex v in G, there exists a list of k colors L(v), such that there exists a unique L-coloring for G, then G is called uniquely k-list colorable graph or a UkLC graph for short. This concept was introduced by E. S. Mahmoodian and M. Mahdian.M. Ghebleh and E. S. Mahmoodian(2001 年)have shown the open problem that verify the graphs K_(2,3,R) for r = 4,5,... ,8, K_(2,3,4),K_(1*4,4) K_(1*4,5) and K_(1*5,4) have the property M(3). I have proved that K_(2,2,r) for r = 4,5.6, 7, have the property M(3).
|
