List Coloring of the Square of 4-Irregular Graphs

Abstract

The square of a graph $G$ is the graph obtained from $G$ after adding an edge between any two vertices of distance $2$. A $k$-irregular graph is a graph with maximum degree $k$ such that vertices of degree $k$ are not adjacent. A \textit{list assignment} of a graph is a function $L$ that assigns to each vertex a list of permissible colors. The graph is said to be \textit{$L$-colorable} if there exists a proper coloring $f$ such that $f(v) \in L(v)$ for every vertex $v$. A graph $G$ is called \textit{$k$-choosable} if it is $L$-colorable for every list assignment where each list has exactly $k$ colors. The \textit{list chromatic number} of $G$, denoted by $\chi_l(G)$, is the smallest integer $k$ for which $G$ is $k$-choosable. Cranston and Kim \cite{ck} showed that $\chi_l(G^2) \leq 8$ for all subcubic graphs except the Petersen Graph. Moreover, Cranston and Kim \cite{ck} conjectured that for graphs with maximum degree $k$ and maximum clique size $w (G^2)\leq k^2-1$, we have $\chi_l(G^2) \leq k^2-1$. We prove that for a 4-irregular graph $G$, we have $\chi_l(G^2) \leq 11$. Moreover, we provide an example to show that this bound is sharp.