Stronger finite-exception conjecture for choosability of graph powers

From papers

Let GG be a simple connected graph with maximum degree Δ3\Delta\geq 3. For kNk\in\mathbb{N}^*, let GkG^k be the graph obtained by joining vertices at distance at most kk, and define

D(k,Δ)=Δi=1k(Δ1)i1=Δ(Δ1)k1Δ2.D(k,\Delta)=\Delta\sum_{i=1}^{k}(\Delta-1)^{i-1}=\Delta\frac{(\Delta-1)^k-1}{\Delta-2}.

Stronger finite-exception conjecture. For any kNk\in\mathbb{N}^*, except for a finite number of graphs, the kkth power GkG^k is (D(k,Δ)+1k)(D(k,\Delta)+1-k)-choosable. This is posed as a stronger generalization of the square-choosability conjecture, and the source does not report a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Marthe Bonamy and Nicolas Bousquet, “Brooks' theorem on powers of graphs”, arXiv:1310.5493 (2013).

Solutions 0

No solutions have been posted yet.