10 Problems for Partitions of Triangle-free Graphs

File

2022-Lidicky-ProblemsPartitionsPreprint.pdf (350.29 KB)

Date

2022

Authors

Balogh, József
Clemen, Felix Christian
Lidicky, Bernard

Publisher

Altmetrics

Authors

Lidicky, Bernard

Person

Organizational Units

Mathematics

Organizational Unit

Department

Mathematics

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.

Comments

This preprint is made available through arXiv at doi:https://doi.org/10.48550/arXiv.2203.15764. Posted with permission. This work is licensed under the Creative Commons Attribution 4.0 License.