RUS  ENG
Full version
JOURNALS // Chebyshevskii Sbornik // Archive

Chebyshevskii Sb., 2024 Volume 25, Issue 2, Pages 208–221 (Mi cheb1426)

The chromaticity of complete split graphs

Hung Xuan Le

Hanoi University of Industry (Hanoi, Vietnam)

Abstract: The join of null graph $O_m$ and complete graph $K_n$, $O_m+K_n=S(m,n)$, is called a complete split graph. In this paper, we characterize chromatically unique, determine list-chromatic number and characterize unique list colorability of the complete split graph $G=S(m,n)$. We shall prove that $G$ is chromatically unique if and only if $1\le m\le 2$, $ch(G)=n+1$, $G$ is uniquely $3$-list colorable graph if and only if $m\ge 4$, $n\ge 4$ and $m+n\ge 10$, $m(G)\le 4$ for every $1\le m\le 5$ and $n\ge 6$. Some the property of the graph $G=S(m,n)$ when it is $k$-list colorable graph also proved.

Keywords: chromatically unique, list- chromatic number, uniquely list colorable graph, complete split graph.

UDC: 519.1

Received: 11.12.2023
Accepted: 28.06.2024

Language: English

DOI: 10.22405/2226-8383-2024-25-2-208-221



© Steklov Math. Inst. of RAS, 2024