ArticleOriginal scientific text

Title

On characterization of uniquely 3-list colorable complete multipartite graphs

Authors 1, 2, 1

Affiliations

  1. Department of Mathematics, Shanghai University, Shanghai 200444, P.R. China
  2. Department of Science, Bengbu University, Anhui 233030, P.R. China

Abstract

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: K2,2,r r ∈ {4,5,6,7,8}, K2,3,4, K14,4, K14,5, K15,4. Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for K2,2,r r ∈ {4,5,6,7,8}, the others have been proved not to be U3LC graphs. In this paper we first prove that K2,2,8 is not U3LC graph, and thus as a direct corollary, K2,2,r (r = 4,5,6,7,8) are not U3LC graphs, and then the uniquely 3-list colorable complete multipartite graphs are characterized completely.

Keywords

list coloring, complete multipartite graph, uniquely 3-list colorable graph

Bibliography

  1. N. Alon, Restricted colorings of graphs, in: K. Walker, editor, Surveys in Combinatorics, Number 187 in London Math. Soc. LNS, pp. 1-33, 1993.
  2. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing Co., INC., New York, 1976).
  3. J.H. Dinitz and W.J. Martin, The stipulation polynomial of a uniquely list colorable graph, Austral. J. Combin. 11 (1995) 105-115.
  4. P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proceedings of West Coast Conference on Combinatorics, Graph Theory and Computing, number 26 in Congr. Number., pp. 125-157, Arcata, CA, September 1979.
  5. Y.G. Ganjali, M. Ghebleh, H. Hajiabohassan, M. Mirzadeh and B.S. Sadjad, Uniquely 2-list colorable graphs, Discrete Appl. Math. 119 (2002) 217-225, doi: 10.1016/S0166-218X(00)00335-8.
  6. M. Ghebleh and E.S. Mahmoodian, On uniquely list colorable graphs, Ars Combin. 59 (2001) 307-318.
  7. W.J. He, Y.N. Wang, Y.F. Shen and X. Ma, On property M(3) of some complete multipartite graphs, Australasian Journal of Combinatorics, to appear.
  8. M. Mahdian and E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. 51 (1999) 295-305.
  9. E.S. Mahmoodian and M. Mahdian, On the uniquely list colorable graphs, in: Proceedings of the 28th Annual Iranian Mathematics Conference, Part 1, number 377 in Tabriz Univ. Ser., Tabriz, 1997.
  10. Y.F. Shen and Y.N. Wang, On uniquely list colorable complete multipartite graphs, Ars Combin. 88 (2008) 367-377.
  11. V.G. Vizing, Coloring the vertices of a graph in prescribed colors, (in Russian) Discret. Anal. 29 (1976) 3-10.
  12. Y.Q. Zhao, W.J. He, Y.F. Shen and Y.N. Wang, Note on characterization of uniquely 3-list colorable complete multipartite graphs, in: Discrete Geometry, Combinatorics and Graph Theory, LNCS 4381 (Springer, Berlin, 2007) 278-287, doi: 10.1007/978-3-540-70666-3₃0.
Pages:
105-114
Main language of publication
English
Received
2009-02-26
Accepted
2009-04-02
Published
2010
Exact and natural sciences