Answers are grounded in this paper and cite their sources.
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 χₗ(G), is the smallest integer k for which G is k-choosable. Cranston and Kim {ck} showed that χₗ(G²) ≤ 8 for all subcubic graphs except the Petersen Graph. Moreover, Cranston and Kim {ck} conjectured that for graphs with maximum degree k and maximum clique size w (G²)≤ k²-1, we have χₗ(G²) ≤ k²-1. We prove that for a 4-irregular graph G, we have χₗ(G²) ≤ 11. Moreover, we provide an example to show that this bound is sharp.
No takes yet. Share an insight, caveat, or question.
Sara Al Hajjar (2026) studied this question.