Faron–Postle Ore-degree conjecture for line-graph cliques

Less than 1 year old · traced to

Let GG be a finite simple graph. For a non-empty subgraph HH of GG, define its Ore-degree in GG by

σG(H):=max⁡xy∈E(H)(deg⁡G(x)+deg⁡G(y)),\sigma_G(H):=\max_{xy\in E(H)}(\deg_G(x)+\deg_G(y)),

with σG(H)=0\sigma_G(H)=0 when HH is empty. Suppose that HH is a bipartite subgraph of GG and that E(H)E(H) forms a clique in L(G)2L(G)^2. Faron–Postle conjecture. Then

∣E(H)∣≤14σG(H)2.|E(H)|\le \frac{1}{4}\sigma_G(H)^2.

This stronger Ore-degree statement implies the Faudree–Gyárfás–Schelp–Tuza strong clique index conjecture. The paper proves a substantial partial result with coefficient 6201987\frac{620}{1987}, but the conjectured coefficient 14\frac14 remains open.

References

Primary source

Hitesh Kumar, Bojan Mohar and Shivaramakrishna Pragada, “An improved bound for the strong clique index of graphs”, arXiv:2607.02698 (2026).

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.