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/}
}
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/