Dense halves in balanced 2-partition of K4-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913616671801344 |
|---|---|
| author | Xu, Yue Zhang, Xiao-Dong |
| author_facet | Xu, Yue Zhang, Xiao-Dong |
| contents | A balanced 2-partition of a graph is a bipartition $A,A^c$ of $V(G)$ such that $|A|=|A^c|$. Balogh, Clemen, and Lidický conjectured that for every $K_4$-free graph on $n$ (even) vertices, there exists a balanced 2-partition $A,A^c$ such that $\max\{e(A),e(A^c)\}\leq n^2/16$ edges. In this paper, we present a family of counterexamples to the conjecture and provide a new upper bound ($0.074n^2$) for every sufficiently large even integer $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13485 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dense halves in balanced 2-partition of K4-free graphs Xu, Yue Zhang, Xiao-Dong Combinatorics 05C35, 05C69 A balanced 2-partition of a graph is a bipartition $A,A^c$ of $V(G)$ such that $|A|=|A^c|$. Balogh, Clemen, and Lidický conjectured that for every $K_4$-free graph on $n$ (even) vertices, there exists a balanced 2-partition $A,A^c$ such that $\max\{e(A),e(A^c)\}\leq n^2/16$ edges. In this paper, we present a family of counterexamples to the conjecture and provide a new upper bound ($0.074n^2$) for every sufficiently large even integer $n$. |
| title | Dense halves in balanced 2-partition of K4-free graphs |
| topic | Combinatorics 05C35, 05C69 |
| url | https://arxiv.org/abs/2412.13485 |