On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao; Erfang Shan

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 1, page 105-114
  • ISSN: 2083-5892

Abstract

top
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: K 2 , 2 , r r ∈ 4,5,6,7,8, K 2 , 3 , 4 , K 1 * 4 , 4 , K 1 * 4 , 5 , K 1 * 5 , 4 . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for K 2 , 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 K 2 , 2 , 8 is not U3LC graph, and thus as a direct corollary, K 2 , 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.

How to cite

top

Yancai Zhao, and Erfang Shan. "On characterization of uniquely 3-list colorable complete multipartite graphs." Discussiones Mathematicae Graph Theory 30.1 (2010): 105-114. <http://eudml.org/doc/270997>.

@article{YancaiZhao2010,
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: $K_\{2,2,r\}$ r ∈ 4,5,6,7,8, $K_\{2,3,4\}$, $K_\{1*4,4\}$, $K_\{1*4,5\}$, $K_\{1*5,4\}$. Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_\{2,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 $K_\{2,2,8\}$ is not U3LC graph, and thus as a direct corollary, $K_\{2,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.},
author = {Yancai Zhao, Erfang Shan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {list coloring; complete multipartite graph; uniquely 3-list colorable graph},
language = {eng},
number = {1},
pages = {105-114},
title = {On characterization of uniquely 3-list colorable complete multipartite graphs},
url = {http://eudml.org/doc/270997},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Yancai Zhao
AU - Erfang Shan
TI - On characterization of uniquely 3-list colorable complete multipartite graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 1
SP - 105
EP - 114
AB - 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: $K_{2,2,r}$ r ∈ 4,5,6,7,8, $K_{2,3,4}$, $K_{1*4,4}$, $K_{1*4,5}$, $K_{1*5,4}$. Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2,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 $K_{2,2,8}$ is not U3LC graph, and thus as a direct corollary, $K_{2,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.
LA - eng
KW - list coloring; complete multipartite graph; uniquely 3-list colorable graph
UR - http://eudml.org/doc/270997
ER -

References

top
  1. [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. Zbl0791.05034
  2. [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing Co., INC., New York, 1976). Zbl1226.05083
  3. [3] J.H. Dinitz and W.J. Martin, The stipulation polynomial of a uniquely list colorable graph, Austral. J. Combin. 11 (1995) 105-115. Zbl0826.05025
  4. [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. [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. Zbl0999.05037
  6. [6] M. Ghebleh and E.S. Mahmoodian, On uniquely list colorable graphs, Ars Combin. 59 (2001) 307-318. Zbl1066.05063
  7. [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. Zbl1097.05019
  8. [8] M. Mahdian and E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. 51 (1999) 295-305. Zbl0977.05046
  9. [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. Zbl0977.05046
  10. [10] Y.F. Shen and Y.N. Wang, On uniquely list colorable complete multipartite graphs, Ars Combin. 88 (2008) 367-377. Zbl1224.05188
  11. [11] V.G. Vizing, Coloring the vertices of a graph in prescribed colors, (in Russian) Discret. Anal. 29 (1976) 3-10. 
  12. [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. Zbl1149.05312

NotesEmbed ?

top

You must be logged in to post comments.