Győri–Keszegh's greedy-partition triangle conjecture for -free graphs
Győri–Keszegh's greedy-partition triangle conjecture for -free graphs
Let be an -vertex -free graph with edges. A greedy partition of is a partition of into disjoint cliques such that for each , and for every , the union of cliques of size at most induces a -free subgraph. Write for the number of cliques in , let be the number of triangles in , and let be the maximum number of edge-disjoint triangles in . Define
Győri–Keszegh's conjecture. For every such graph and every greedy partition ,
and consequently
The conjecture strengthens the known triangle bound used by Győri and Keszegh to derive the extremal result that every -free graph with edges contains at least edge-disjoint triangles. A greedy-partition lemma gives , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.