Uniquely list colorability of complete tripartite graphs

Le Xuan Hung

Čebyševskij sbornik, Tome 23 (2022) no. 2, pp. 170-178.

Résumé

Given a list $L(v)$ for each vertex $v$, we say that the graph $G$ is $L$-colorable if there is a proper vertex coloring of $G$ where each vertex $v$ takes its color from $L(v)$. The graph is uniquely $k$-list colorable if there is a list assignment $L$ such that $|L(v)| = k$ for every vertex $v$ and the graph has exactly one $L$-coloring with these lists. If a graph $G$ is not uniquely $k$-list colorable, we also say that $G$ has property $M(k)$. The least integer $k$ such that $G$ has the property $M(k)$ is called the $m$-number of $G$, denoted by $m(G)$. In this paper, first we characterize about the property of the complete tripartite graphs when it is uniquely $k$-list colorable graphs, finally we shall prove that $m(K_{2,2,m})=m(K_{2,3,n})=m(K_{2,4,p})=m(K_{3,3,3})=4$ for every $m\ge 9,n\ge 5, p\ge 4$.

Détail

Keywords: Vertex coloring (coloring), list coloring, uniquely list colorable graph, complete $r$-partite graph.

Bibliographie

[1] M. Behzad, Graphs and thei chromatic number, Doctoral Thesis, Michigan State University, 1965 | MR

[2] M. Behzad and G. Chartrand, Introduction to the theory of graphs, Allyn and Bacon, Boston, 1971 | MR | Zbl

[3] M. Behzad, G. Chartrand and J. Cooper, “The coloring numbers of complete graphs”, J. London Math. Soc., 1967, no. 42, 226–228 | DOI | MR | Zbl

[4] J.A. Bondy and U.S.R. Murty, Graph theory with applications, MacMillan, 1976 | MR

[5] R. Diestel, Graph Theory, Springer-Verlag, New Youk, 2000 | MR

[6] J.H. Dinitz and W.J. Martin, “The stipulation polynomial of a uniquely list colorable graph”, Austran. J. Combin., 1995, no. 11, 105–115 | MR | Zbl

[7] P. Erdös, A. L. Rubin, and H. Taylor, “Choosability in graphs”, Proceedings of west coast conference on combinatorics, graph theory, and computing (Arcata, CA, September, 1979), Congr. Numer., 26, 125–157 | MR

[8] M. Ghebleh and E.S. Mahmoodian, “On uniquely list colorable graphs”, Ars Combin., 59 (2001), 307–318 | MR | Zbl

[9] Le Xuan Hung, “Colorings of the graph $K^m_2+K_n$”, Journal of Siberian Federal University. Mathematics $\ $ Physics (to appear)

[10] M. Mahdian and E.S. Mahmoodian, “A characterization of uniquely 2-list colorable graphs”, Ars Combin., 51 (1999), 295–305 | MR | Zbl

[11] R.C. Read, “An introduction to chromatic polynomials”, J. Combin. Theory, 1968, no. 4, 52–71 | DOI | MR

[12] Ngo Dac Tan and Le Xuan Hung, “On colorings of split graphs”, Acta Mathematica Vietnammica, 31:3 (2006), 195–204 | MR | Zbl

[13] V.G. Vizing, “On an estimate of the chromatic class of a $p$-graph”, Discret. Analiz, 1964, no. 3, 23–30 (In Russian) | MR

[14] V. G. Vizing, “Coloring the vertices of a graph in prescribed colors”, Metody Diskret. Anal. v Teorii Kodov i Shem, 29, 1976, 3–10 | MR | Zbl

[15] W. Wang and X. Liu, “List-coloring based channel allocation for open-spectrum wireless networks”, Proceedings of the IEEE International Conference on Vehicular Technology, VTC '05, 2005, 690–694

[16] R.J. Wilson, Introduction to graph theory, Longman group Ltd, London, 1975 | MR

[17] Yancai Zhao and Erfang Shan, “On characterization of uniquely 3-list colorable complete multipartite graphs”, Discussiones Mathematicae Graph Theory, 30 (2010), 105–114 | DOI | MR | Zbl

[18] Y.Q. Zhao, W.J. He, Y.F. Shen and Y.N. Wang, “Note on characterization of uniquely 3-list colorable complete multipartite graphs”, Discrete Geometry, Combinatorics and Graph Theory, LNCS, 4381, Springer, Berlin, 2007, 278–287 | MR | Zbl