Győri–Keszegh's greedy-partition triangle conjecture for K4K_4-free graphs

Let GG be an nn-vertex K4K_4-free graph with ee edges. A greedy partition PP of GG is a partition of V(G)V(G) into disjoint cliques TiT_i such that TiTi+1|T_i|\geq |T_{i+1}| for each ii, and for every 1\ell\geq 1, the union of cliques of size at most \ell induces a K+1K_{\ell+1}-free subgraph. Write r:=r(P)r:=r(P) for the number of cliques in PP, let t(G)t(G) be the number of triangles in GG, and let te(G)t_e(G) be the maximum number of edge-disjoint triangles in GG. Define

g(G,P):=r(er(nr))t(G).g(G,P):=r(e-r(n-r))-t(G).

Győri–Keszegh's conjecture. For every such graph GG and every greedy partition PP,

t(G)r(er(nr)),equivalently g(G,P)0,t(G)\geq r\bigl(e-r(n-r)\bigr),\qquad\text{equivalently }g(G,P)\leq 0,

and consequently

te(G)er(nr).t_e(G)\geq e-r(n-r).

The conjecture strengthens the known triangle bound used by Győri and Keszegh to derive the extremal result that every K4K_4-free graph with tn,2+mt_{n,2}+m edges contains at least mm edge-disjoint triangles. A greedy-partition lemma gives te(G)t(G)/r(P)t_e(G)\geq t(G)/r(P), so the conjectured inequality would imply the stated lower bound for edge-disjoint triangles; its status is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Jialin He, Jie Ma, Yan Wang and Chunlei Zu, “On the number of triangles in K_4-free graphs”, arXiv:2509.12100 (2025).

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.