Choosability of Graph Powers

Choosability of Graph Powers

Definitions and mathematical statement

Let $G$ be a finite nonempty simple graph. Its square $G^2$ joins two distinct vertices when a path of length one or two connects them in $G$. For any graph $H$, let $\chi(H)$ be its ordinary chromatic number and $\operatorname{ch}(H)$ its choice number. The latter is the least $q$ such that every assignment of $q$ colours to each vertex permits a proper colouring using one colour from each vertex's list.

The problem asks whether there exists a function $f:\mathbb N_{\ge1}\to\mathbb R_{\ge0}$ satisfying \[ \lim_{k\to\infty}\frac{f(k)}{k^2}=0, \qquad \operatorname{ch}(G^2)\le f(\chi(G^2)) \quad\text{for every such }G. \] The same function must work for all graphs, regardless of their number of vertices. No monotonicity or effective computability of $f$ is assumed. Equivalently, for every $\varepsilon>0$ there should exist $K$ such that $\operatorname{ch}(G^2)\le\varepsilon\chi(G^2)^2$ whenever $\chi(G^2)\ge K$.

The normalization is natural: if $d=\Delta(G)$, then a vertex and its neighbours form a clique in $G^2$, while every square-degree is at most $d^2$. Consequently the elementary greedy bound gives $\operatorname{ch}(G^2)\le d^2+1\le\chi(G^2)^2$. The requested improvement is uniform and asymptotically smaller than quadratic; it need not make list chromatic number equal ordinary chromatic number. The exponent two denotes graph distance as well as the separate quadratic growth benchmark, in their respective positions.

Short English statement

Is there a universal subquadratic upper bound for the choice number of a graph square in terms of that square’s chromatic number?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 2 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and chosen reduction.

Kosar, Petříčková, Reiniger and Yeager [R1] construct powers whose choice numbers exceed a constant times their chromatic numbers times the logarithm of those chromatic numbers. Thus equality of the two parameters, or a universal linear bound, cannot simply be assumed. Their examples do not rule out the weaker subquadratic target. We prove an explicit linear bound when the original graph has bounded degeneracy, and a separate order-dependent bound from palette splitting. The original graph, rather than its square, supplies the degeneracy parameter throughout the first argument.

A degeneracy order controls later square neighbours.

A graph is $d$-degenerate if its vertices can be ordered so that each vertex has at most $d$ neighbours later in the order. Repeatedly removing a vertex of degree at most $d$ gives such an order whenever every nonempty subgraph has such a vertex. Let $G$ have maximum degree $\Delta\ge1$ and such an order, with $1\le d\le\Delta$. Fix a vertex $v$ and let $r\le d$ be its number of later neighbours in $G$.

A later neighbour of $v$ in $G^2$ can be reached directly, through a later original neighbour, or through an earlier original neighbour. There are at most $r$ direct ones. Each of the $r$ later neighbours has at most $\Delta-1$ other neighbours. Each earlier neighbour $w$ has at most $d-1$ neighbours later than $v$, because its own set of later neighbours includes $v$ and has size at most $d$. There are at most $\Delta-r$ such earlier neighbours. Counting with possible overcounting gives \[ d^+_{G^2}(v)\le r+r(\Delta-1)+(\Delta-r)(d-1) \le(2d-1)\Delta-d(d-1). \] The final expression follows by maximizing the preceding affine function over $r\le d$; its coefficient of $r$ is $\Delta-d+1>0$.

Reverse-order greedy list-colouring now proves \[ \operatorname{ch}(G^2)\le(2d-1)\Delta-d(d-1)+1. \] Indeed, when a vertex is coloured, only its later square neighbours have already been coloured, so a list larger than their number always has an available colour. Arbitrary overlaps among lists do not affect this argument.

Converting the bound to the requested parameter.

Put $k=\chi(G^2)$. A vertex of maximum degree and its neighbours form a clique in $G^2$, so $\Delta\le k-1$. Consequently \[ \operatorname{ch}(G^2)\le(2d-1)(k-1)+1. \] For each fixed $d$ this is linear in $k$, and hence subquadratic. More generally it remains subquadratic on any family with $d=o(k)$. Forests have $d=1$, giving $\operatorname{ch}(G^2)\le\Delta+1$; the neighbourhood clique gives equality for every nonempty forest with an edge. Edgeless graphs have both square parameters equal to one and are handled separately. These are family statements with the same constants at every order, not estimates depending on one chosen graph's number of vertices.

A complementary bound using the order.

For any $k$-colourable graph $H$ on $N$ vertices, fix a proper partition into $k$ independent colour classes. Assign every colour name in a list assignment independently to one of $k$ palettes. A vertex with a list of size $q$ misses its class's palette with probability $(1-1/k)^q\le e^{-q/k}$. If $q>k\log N$, a union bound leaves a split with no missing palette. Choosing colours from the assigned palettes then gives a proper list-colouring. Thus $\operatorname{ch}(H)\le\lfloor k\log N\rfloor+1$ for $k\ge2$. Applied to a square, this is subquadratic whenever $\log N=o(k)$. It does not establish a uniform bound because the catalogue imposes no restriction on $N$.

Verification and the remaining simultaneous obstruction.

The companion script [R2] enumerates all simple graphs through order five, constructs a degeneracy order and the exact square, and checks the displayed later-neighbour bound. The proof allows repeated witnesses to one square edge and therefore uses upper bounds rather than an incorrect equality. It also treats earlier intermediate vertices, which cannot be omitted from a distance-two count.

For unrestricted inputs one can have $d$ comparable to $k$ and $\log N$ comparable to or larger than $k$; neither proved bound then gives $o(k^2)$. Dense original graphs are not automatically counterexamples: for $G=K_k$ both square parameters are just $k$. The gap is the absence of an argument exploiting dense structure while also handling arbitrary order and list overlaps.

Final status.

UNRESOLVED. Bounded-degeneracy roots and the stated order regime satisfy subquadratic bounds. No single function $o(k^2)$ covering every root graph is established.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3249 (OPG-53019), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Choosability of Graph Powers. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/choosability_of_graph_powers.

• R1 Nicholas Kosar, Šárka Petříčková, Benjamin Reiniger and Elyse Yeager, A note on list-coloring powers of graphs, Discrete Mathematics 332 $2014$, 10--14. Primary abstract checked 2 October 2026. https://arxiv.org/abs/1309.7705.
• R2 GPT-6 Astra Ultra, exact batch certificates, 2 October 2026. Repository script scripts/check_attempt_batch03_colouring_2026_10_02.py.