On the number of triangles in $K_4$-free graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916950124265472 |
|---|---|
| author | He, Jialin Ma, Jie Wang, Yan Zu, Chunlei |
| author_facet | He, Jialin Ma, Jie Wang, Yan Zu, Chunlei |
| contents | Erdős asked whether for any $n$-vertex graph $G$, the parameter $p^*(G)=\min \sum_{i\ge 1} (|V(G_i)|-1)$ is at most $\lfloor n^2/4\rfloor$, where the minimum is taken over all edge decompositions of $G$ into edge-disjoint cliques $G_i$. In a restricted case (also conjectured independently by Erdős), Győri and Keszegh [Combinatorica, 37(6) (2017), 1113--1124] proved that $p^*(G)\leq \lfloor n^2/4\rfloor$ for all $K_4$-free graphs $G$. Motivated by their proof approach, they conjectured that for any $n$-vertex $K_4$-free graph $G$ with $e$ edges, and any greedy partition $P$ of $G$ of size $r$, the number of triangles in $G$ is at least $r(e-r(n-r))$. If true, this would imply a stronger bound on $p^*(G)$. In this paper, we disprove their conjecture by constructing infinitely many counterexamples with arbitrarily large gap. We further establish a corrected tight lower bound on the number of triangles in such graphs, which would recover the conjectured bound once some small counterexamples we identify are excluded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_12100 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the number of triangles in $K_4$-free graphs He, Jialin Ma, Jie Wang, Yan Zu, Chunlei Combinatorics 05C35 05C69 05C70 Erdős asked whether for any $n$-vertex graph $G$, the parameter $p^*(G)=\min \sum_{i\ge 1} (|V(G_i)|-1)$ is at most $\lfloor n^2/4\rfloor$, where the minimum is taken over all edge decompositions of $G$ into edge-disjoint cliques $G_i$. In a restricted case (also conjectured independently by Erdős), Győri and Keszegh [Combinatorica, 37(6) (2017), 1113--1124] proved that $p^*(G)\leq \lfloor n^2/4\rfloor$ for all $K_4$-free graphs $G$. Motivated by their proof approach, they conjectured that for any $n$-vertex $K_4$-free graph $G$ with $e$ edges, and any greedy partition $P$ of $G$ of size $r$, the number of triangles in $G$ is at least $r(e-r(n-r))$. If true, this would imply a stronger bound on $p^*(G)$. In this paper, we disprove their conjecture by constructing infinitely many counterexamples with arbitrarily large gap. We further establish a corrected tight lower bound on the number of triangles in such graphs, which would recover the conjectured bound once some small counterexamples we identify are excluded. |
| title | On the number of triangles in $K_4$-free graphs |
| topic | Combinatorics 05C35 05C69 05C70 |
| url | https://arxiv.org/abs/2509.12100 |