Sharp bounds for decomposing graphs into edges and triangles

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Sharp bounds for decomposing graphs into edges and triangles

Popis výsledku v původním jazyce

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).

Název v anglickém jazyce

Sharp bounds for decomposing graphs into edges and triangles

Popis výsledku anglicky

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).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/EF16_019%2F0000778" target="_blank" >EF16_019/0000778: Centrum pokročilých aplikovaných přírodních věd</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název periodika

Combinatorics, Probability and Computing

ISSN

0963-5483

e-ISSN

1469-2163

Svazek periodika

30

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

17

Strana od-do

271-287

Kód UT WoS článku

000625213500007

EID výsledku v databázi Scopus

2-s2.0-85095310345