Sharp bounds for decomposing graphs into edges and triangles

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F21%3A00347568" target="_blank" >RIV/68407700:21340/21:00347568 - isvavai.cz</a>
Result on the web
<a href="http://hdl.handle.net/10467/99562" target="_blank" >http://hdl.handle.net/10467/99562</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1017/S0963548320000358" target="_blank" >10.1017/S0963548320000358</a>

Result language
angličtina
Original language name
Sharp bounds for decomposing graphs into edges and triangles
Original language description
In 1966, Erdos, Goodman and Posa proved that the edges of an n-vertex graph can be decomposed into at most n^2/4 cliques. Moreover, such a decomposition may consist of edges and triangles only. In 1980s, Gyori and Kostochka and independently Chung strengthened the first result in order to answer a question of Katona and Tarjan by proving that the minimum sum of the clique-orders in such decompositions is at most n^2/2. In 1987, these results led Gyori and Tuza to conjecture that the edge-set of an n-vertex graph can be decomposed into m edges and t triangles with 2m+3t <= n^2/2 + O(1). Recently, Kral, Lidicky, Martins and Pehova proved the conjecture asymptotically, i.e., found an edge-decomposition of any n-vertex graph into m edges and t triangles with 2m+3t<=n^2/2 + o(n^2). In this work, we fully resolve the conjecture of Gyori and Tuza. Specifically, we prove the only large enough n-vertex graphs that cannot be decomposed into m edges and t triangles with 2m+3t <= n^2/2 are n-vertex cliques with n congruent to 4 (mod 6).
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
<a href="/en/project/EF16_019%2F0000778" target="_blank" >EF16_019/0000778: Center for advanced applied science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)