TY - JOUR

T1 - 10 problems for partitions of triangle-free graphs

AU - Balogh, József

AU - Clemen, Felix Christian

AU - Lidický, Bernard

N1 - Publisher Copyright:
© 2023 Elsevier Ltd

PY - 2023

Y1 - 2023

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

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103841

ER -