Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be such that every graph on vertices and edges can be partitioned into at most edge-disjoint complete graphs. Estimate for .
Source: erdosproblems.com/1017
No claim settles this problem.
Open. What is known: the universal bound with edges and triangles only (Theorem 4 (Erdős, Goodman and Pósa 1966) of [EGP66], Canad. J. Math. 1966, refereed); the origin passages of 1966 and 1971 with Lovász's covering bound quoted by Erdős (Lovász's paper [Lo68] is not held); and the -free case, in which a partition uses only edges and triangles and minimizing pieces is the same as packing edge-disjoint triangles: Theorem 1 (Győri and Keszegh 2017) of [GyKe17] (Combinatorica 2017, refereed; cited from arXiv v1) gives at least edge-disjoint triangles in every -free graph with edges, sharp for up to about (equality for a Turán graph with a triangle-free graph inside one side), so such a graph is partitioned into at most pieces (a one-line conversion made below), the exact -free minimum in that range; between about and the -free maximum only this upper bound is known, and the authors conjecture a stronger one. The same conversion holds for every graph: edge-disjoint triangles leave a partition into triangles and edges, so packing theorems for general graphs sharpen . Write for the number of edges. Győri's exact result as [BaWi25] restates it on p. 10 ( edge-disjoint triangles when for odd or for even ; Erdős stated the case in item 3 of [Er71], naming the method but printing no proof) gives in that range. Equality is attained by the Győri--Keszegh equality graphs: a Turán graph with a triangle-free graph of edges inside one side, in which every triangle uses one of those edges. Győri's Theorem 1.6 as [BaWi25] restates it gives for . Conjecture 1.4, which [BaWi25] proves from its Theorem 1.8, gives for every . These are authored conversions. For of order no estimate beyond these bounds was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness.