The locally dense induced-subgraph conjecture for P5P_5-free graphs

From papers

Let GG be a finite simple graph. For an induced subgraph FF of GG and vV(F)v\in V(F), let NF(v)N_F(v) be the neighbours of vv in FF. P5P_5 local-density conjecture. There exists δ>0\delta>0 such that every P5P_5-free graph GG has an induced subgraph FF satisfying

χ(F)δχ(G)\chi(F)\ge\delta\chi(G)

and

χ(NF(v))δχ(F)\chi(N_F(v))\ge\delta\chi(F)

for every vV(F)v\in V(F). This is presented as a weaker, particularly interesting special case of the colourful induced-subgraph conjecture; 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

Tung H. Nguyen, “On polynomially high-chromatic pure pairs”, arXiv:2504.21127 (2026).

Solutions 0

No solutions have been posted yet.