Katona–Xiao conjecture for the path-and-clique Turán problem

Let PkP_k be a path on kk vertices, let KmK_m be the complete graph on mm vertices, and let T(n,r)T(n,r) denote the Turán graph on nn vertices with independence number at most rr. Write IsI_s for the edgeless graph on ss vertices, δk\delta_k for the relevant path parameter, and GHG\vee H for the join of graphs GG and HH. Assume m+1k2m1m+1\leq k\leq 2m-1.

Katona–Xiao conjecture. If kk is odd and (k1)n(k-1)\mid n, then the disjoint union of n/(k1)n/(k-1) copies of T(k1,m1)T(k-1,m-1) gives the maximum number of edges in a graph containing neither PkP_k nor KmK_m, while for even kk, T(δk,m2)InδkT(\delta_k,m-2)\vee I_{n-\delta_k} is extremal for sufficiently large nn.

This conjecture concerns the remaining range m<k2m1m<k\leq 2m-1 in the generalized Turán problem forbidding both a path and a clique. The corresponding connected and unrestricted extremal values are known when k>2m1k>2m-1, but this intermediate range remains unresolved.

Sources & referencesView supporting material

Primary source

Xiaona Fang, Xiutao Zhu and Yaojun Chen, “Generalized Turán problem for a path and a clique”, arXiv:2409.10129 (2024).

Additional references

2 papers in this index state this conjecture (2023–2024). The statement above is taken from the most recent of them; the others are arXiv:2312.00620.

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.