TY - JOUR
T1 - 10 problems for partitions of triangle-free graphs
AU - Balogh, József
AU - Clemen, Felix Christian
AU - Lidický, Bernard
N1 - Research is partially supported by National Science Foundation Grant DMS-1764123, NSF RTG grant DMS 1937241, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan Scholar Fund (UIUC), and the Simons Fellowship.Research of this author is partially supported by National Science Foundation grant DMS-1855653 and Scott Hanna fellowship.We thank anonymous referees for useful comments and suggestions on the manuscript. This work used the computing resources at the Center for Computational Mathematics, University of Colorado Denver, including the Alderaan cluster, supported by the National Science Foundation, United States award OAC-2019089.
We thank anonymous referees for useful comments and suggestions on the manuscript. This work used the computing resources at the Center for Computational Mathematics, University of Colorado Denver, including the Alderaan cluster, supported by the National Science Foundation award OAC-2019089 .
PY - 2024/10
Y1 - 2024/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85173241389&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85173241389&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2023.103841
DO - 10.1016/j.ejc.2023.103841
M3 - Article
AN - SCOPUS:85173241389
SN - 0195-6698
VL - 121
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103841
ER -