Edwards–King edge-local conjecture for graph coloring

About 14 years old · traced to

Let GG be a finite simple graph. For each vertex vv, let N~(v)={v}∪N(v)\widetilde N(v)=\{v\}\cup N(v), let γℓ(v)=γ(G[N~(v)])\gamma_\ell(v)=\gamma(G[\widetilde N(v)]), and let

γ(G)=⌈Δ(G)+1+ω(G)2⌉.\gamma(G)=\left\lceil\frac{\Delta(G)+1+\omega(G)}{2}\right\rceil.

Edwards–King conjecture. For any graph GG,

χ(G)≤max⁡uv∈E(G)⌈γℓ(u)+γℓ(v)2⌉.\chi(G)\leq\max_{uv\in E(G)}\left\lceil\frac{\gamma_\ell(u)+\gamma_\ell(v)}{2}\right\rceil.

This is a stronger edge-local form of the local Reed conjecture. The source says that the result holds in the fractional setting and for quasi-line graphs, while its validity for arbitrary graphs remains unresolved.

References

Primary source

Andrew D. King and Bruce A. Reed, “Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ”, arXiv:1212.3036 (2012).

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.