Balanced bipartite distance of $K_4$-free graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910195223887872 |
|---|---|
| author | Balogh, József Buczek, Ignacy Grzesik, Andrzej Kuc, Piotr |
| author_facet | Balogh, József Buczek, Ignacy Grzesik, Andrzej Kuc, Piotr |
| contents | We show that every $K_4$-free graph on $n$ vertices can be made balanced bipartite by removing at most $\frac{n^2}{9}$ edges. This proves a conjecture of Balogh, Clemen, and Lidický, and generalizes both Sudakov's result on the bipartite distance of $K_4$-free graphs and Reiher's result on the sparse half of $K_4$-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05346 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Balanced bipartite distance of $K_4$-free graphs Balogh, József Buczek, Ignacy Grzesik, Andrzej Kuc, Piotr Combinatorics We show that every $K_4$-free graph on $n$ vertices can be made balanced bipartite by removing at most $\frac{n^2}{9}$ edges. This proves a conjecture of Balogh, Clemen, and Lidický, and generalizes both Sudakov's result on the bipartite distance of $K_4$-free graphs and Reiher's result on the sparse half of $K_4$-free graphs. |
| title | Balanced bipartite distance of $K_4$-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.05346 |