10 problems for partitions of triangle-free graphs

József Balogh, Felix Christian Clemen, Bernard Lidický

Research output: Contribution to journalArticlepeer-review


We will state 10 problems, and solve some of them, for partitions in triangle-free graphs related to Erdős’ Sparse Half Conjecture. Among others we prove the following variant of it: For every sufficiently large even integer n the following holds. Every triangle-free graph on n vertices has a partition V(G)=A∪B with |A|=|B|=n/2 such that e(G[A])+e(G[B])≤n2/16. This result is sharp since the complete bipartite graph with class sizes 3n/4 and n/4 achieves equality, when n is a multiple of 4. Additionally, we discuss similar problems for K4-free graphs.

Original languageEnglish (US)
Article number103841
JournalEuropean Journal of Combinatorics
StateAccepted/In press - 2023

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of '10 problems for partitions of triangle-free graphs'. Together they form a unique fingerprint.

Cite this