Stronger finite-exception conjecture for choosability of graph powers

About 13 years old · traced to

Let GG be a simple connected graph with maximum degree Δ≥3\Delta\geq 3. For k∈N∗k\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)i−1=Δ(Δ−1)k−1Δ−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 k∈N∗k\in\mathbb{N}^*, except for a finite number of graphs, the kkth power GkG^k is (D(k,Δ)+1−k)(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.