Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 23 min ago
PreprintCC BY 4.0arXiv

Seeking the dense half in K4-free graphs

  • Ignacy Buczek
  • Andrzej Grzesik
  • Piotr Kuc
Open at sourcePDFDOICite

Abstract

We show that every K4-free graph on n vertices has a balanced bipartition such that neither part contains more than 0.0671n2 + o(n2) edges. This improves the previous best bound of 0.074n2 by Xu and Zhang. We also formulate a conjecture that the tight bound for this problem is 425/6498n2 ≈ 0.0654n2, and present a construction showing that it would be best possible.

Related

  1. A new infinite family of covers of complete graphs that admit a half-transitive action of a Suzuki simple group
    Ludmila Yu. Tsiovkina
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. The singularity probability of dense random regular graphs
    Zeyan Song, Hanchao Wang, Shengyan Yin +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  3. The Erd\H os-Sós conjecture in dense graphs
    Bruce Reed, Maya Stein
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Counting cographs in locally dense graphs
    Hyunwoo Lee
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Faster high-accuracy multicommodity flow in dense graphs
    Chenxin Dai, Alicia Stepin, Colin Tang
    arXivPreprintCC BY-NC-SA 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{buczek2026seeking,
  title = {{Seeking the dense half in $K_4$-free graphs}},
  author = {Ignacy Buczek and Andrzej Grzesik and Piotr Kuc},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.07082},
  eprint = {2611.07082},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07082},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Seeking the dense half in K_4-free graphs
AU  - Ignacy Buczek
AU  - Andrzej Grzesik
AU  - Piotr Kuc
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.07082
UR  - https://arxiv.org/abs/2611.07082
AB  - We show that every K_4-free graph on n vertices has a balanced bipartition such that neither part contains more than 0.0671n^2 + o(n^2) edges. This improves the previous best bound of 0.074n^2 by Xu and Zhang. We also formulate a conjecture that the tight bound for this problem is 425/6498n^2 ≈ 0.0654n^2, and present a construction showing that it would be best possible.
ER  -