On coloring numbers of graph powers

NEW

Problem: For finite simple graphs, reconstruct Question 3.6 as asking whether, for each allowed pair $(k,C)$, there is a minimum real number $m(C)$ such that every graph $G$ with

satisfies

Here $\operatorname{mad}(G)=\max_{H\subseteq G,\,H\ne\emptyset}2|E(H)|/|V(H)|$, $G^2$ joins vertices at distance at most $2$, and $\chi_\ell$ is list chromatic number.

Result: The literal question has no answer as stated: the requested minimum need not exist. Already for the allowed case $k=1,\ C=1$, there is no minimum $m$.

Indeed, if $m>0$, then $\operatorname{mad}(G)\le 2-m<2$, so $G$ is a forest. For a forest $T$, $T^2$ is chordal and has clique number $\Delta(T)+1$, hence

Thus every graph $G$ with $\operatorname{mad}(G)\le 2-m$ satisfies

So every $m>0$ works.

But $m=0$ does not work: take $G=C_5$. Then $\operatorname{mad}(C_5)=2$, $\Delta(C_5)=2$, and $C_5^2=K_5$, so

Hence the admissible set of $m$'s is $(0,\infty)$, which has no minimum.

The defect is an endpoint/minimum issue caused by using $\le$ in the maximum-average-degree condition while asking for a minimum deficit. A natural repair is to ask for the infimum of such $m$, or to use a strict inequality $\operatorname{mad}(G)<2k-m(C)$. For $(k,C)=(1,1)$, the repaired value is $0$.

Citation: No external citation is needed for the counterexample. The facts used are standard: forests have square chordal with clique number $\Delta+1$, and $C_5^2=K_5$.