Geodesic
On property $M(4)$ of the graph $K^n_2+O_m$
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 17 (2024) no. 4, pp. 470-477.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, we characterize uniquely list colorability of the graph $G=K^n_2+O_r$. We shall prove that $m(K^2_2+O_r)=4$ if and only if $r\geqslant 9$, $m(K^3_2+O_r)=4$ for every $1\leqslant r\leqslant 5$ and $m(K^4_2+O_1)=4$.
Keywords: vertex coloring (coloring), list coloring, uniquely list colorable graph, complete r-partite graph. 
@article{JSFU_2024_17_4_a4,
     author = {Le Xuan Hung},
     title = {On property $M(4)$ of the graph $K^n_2+O_m$},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {470--477},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2024_17_4_a4/}
}
TY  - JOUR
AU  - Le Xuan Hung
TI  - On property $M(4)$ of the graph $K^n_2+O_m$
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2024
SP  - 470
EP  - 477
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2024_17_4_a4/
LA  - en
ID  - JSFU_2024_17_4_a4
ER  - 
%0 Journal Article
%A Le Xuan Hung
%T On property $M(4)$ of the graph $K^n_2+O_m$
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2024
%P 470-477
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2024_17_4_a4/
%G en
%F JSFU_2024_17_4_a4
Le Xuan Hung. On property $M(4)$ of the graph $K^n_2+O_m$. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 17 (2024) no. 4, pp. 470-477. http://geodesic.mathdoc.fr/item/JSFU_2024_17_4_a4/

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

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

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

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

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

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

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

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

[9] W.J.He, Y.N.Wang, Y.F.Shen, X.Ma, “On property $M(3)$ of some complete multipartite graphs”, Australasian Journal of Combinatorics, 35:2 (2006), 211–220 | MR | Zbl

[10] Le Xuan Hung, “List-chromatic number and chromatically unique of the graph $K^r_2+O_k$”, Selecciones Matemáticas, Universidad Nacional de Trujillo, 6:1 (2019), 26–30 | DOI

[11] Le Xuan Hung, “Colorings of the graph $K^m_2+K_n$”, J. Sib. Fed. Univ. Math. Phys., 13:3 (2020), 297–305 | DOI | MR | Zbl

[12] Le Xuan Hung, “Unique list colorability of the graph $K^n_2+K_r$”, Prikladnaya Diskretnaya Matematika, 2022, no. 55, 88–94 | DOI | MR | Zbl

[13] Le Xuan Hung, “Uniquely list colorability of complete tripartite graphs”, Chebyshevskii sbornik, 23:2 (2022), 170–178 | DOI | MR | Zbl

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

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

[16] Y.F.Shen, Y.N Wang, “On uniquely list colorable complete multipartite graphs”, Ars Combin., 88 (2008), 367–377 | MR | Zbl

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

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

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

[20] W.Wang, 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

[21] Y.Wang, Y.Shen, G.Zheng, W.He, “On uniquely $4$-list colorable complete multipartite graphs”, Ars Combinatoria, 93 (2009), 203–214 | MR | Zbl

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

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