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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.