2022/03/29 by Balogh, József, Clemen, Felix Christian, Lidický, Bernard
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2203.15764
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.