Font Size: a A A

A Characterization Of Uniquely List Colorable For Some Complete Multipartite Graphs

Posted on:2006-09-18Degree:MasterType:Thesis
Country:ChinaCandidate:S G SunFull Text:PDF
GTID:2120360152491003Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
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 K2,3,R for r = 4,5,... ,8, K2,3,4,K1*4,4 K1*4,5 and K1*5,4 have the property M(3). I have proved that K2,2,r for r = 4,5.6, 7, have the property M(3).
Keywords/Search Tags:complete multipartite graph, list coloring, UkLC graph, property M(3), ch(G), m(G)
PDF Full Text Request
Related items