10 Problems for Partitions of Triangle-free Graphs

MaRDI QIDQ6395065zbMATH OpenFDO

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

Publication date 29 March 2022

Abstract: We will state 10 problems, and solve some of them, for partitions in triangle-free graphs related to ErdH{o}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)=AcupB$ with $|A|=|B|=n/2$ such that $e(G[A])+e(G[B])leq{n}^2/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 $K_4$-free graphs.

This page was built for publication: 10 Problems for Partitions of Triangle-free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6395065)