10 Problems for Partitions of Triangle-free Graphs
Date
2022
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
Preprint
Comments
This preprint is made available through arXiv at doi:https://doi.org/10.48550/arXiv.2203.15764.
Published as Balogh, József, Felix Christian Clemen, and Bernard Lidický. "10 problems for partitions of triangle-free graphs." European Journal of Combinatorics 121 (2024): 103841. doi:https://doi.org/10.1016/j.ejc.2023.103841.
Published as Balogh, József, Felix Christian Clemen, and Bernard Lidický. "10 problems for partitions of triangle-free graphs." European Journal of Combinatorics 121 (2024): 103841. doi:https://doi.org/10.1016/j.ejc.2023.103841.
Rights Statement
This preprint is licensed under the Creative Commons Attribution 4.0 License.