Tomescu's conjectural coloring bound for ℓ-connected graphs

About 10 years old · traced to

Let GG be a kk-chromatic, ℓ\ell-connected graph on nn vertices, with k≥4k\geq 4 and ℓ≥3\ell\geq 3. Let x≥kx\geq k be an integer, let PG(x)P_G(x) be the number of proper xx-colorings, and let (x)k=x(x−1)⋯(x−k+1)(x)_k=x(x-1)\cdots(x-k+1).

Tomescu's ℓ-connected generalization.

PG(x)≤(x)k(x−1)n−ℓ−k+1+O((x−2)n).P_G(x)\leq (x)_k(x-1)^{n-\ell-k+1}+O((x-2)^n).

This generalizes the preceding conjectures to ℓ\ell-connected graphs. The source notes that its theorem proves the case x=kx=k, but does not report a resolution for general integer x≥kx\geq k.

References

Primary source

John Engbers, Aysel Erey, Jacob Fox and Xiaoyu He, “Tomescu's graph coloring conjecture for -connected graphs”, arXiv:1912.03236 (2019).

Additional references

6 papers in this index state this conjecture (2016–2019). The statement above is taken from the most recent of them; the others are arXiv:1712.06067, arXiv:1710.06535, arXiv:1708.01781, arXiv:1611.09545, arXiv:1610.07219.

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.