10 Problems for Partitions of Triangle-free Graphs

Abstract

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.