Edwards–King edge-local conjecture for graph coloring

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)maxuvE(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.

Sources & referencesView supporting material

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.