2026/07/25 by Sara Al Hajjar
#math.CO
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 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 L-colorable if there exists a proper coloring f such that f(v) ∈ L(v) for every vertex v. A graph G is called k-choosable if it is L-colorable for every list assignment where each list has exactly k colors. The list chromatic number of G, denoted by χl(G), is the smallest integer k for which G is k-choosable. Cranston and Kim \citeck showed that χl(G2) ≤ 8 for all subcubic graphs except the Petersen Graph. Moreover, Cranston and Kim \citeck conjectured that for graphs with maximum degree k and maximum clique size w (G2)≤ k2-1, we have χl(G2) ≤ k2-1. We prove that for a 4-irregular graph G, we have χl(G2) ≤ 11. Moreover, we provide an example to show that this bound is sharp.