论文标题
无三角形图的分区的10个问题
10 Problems for Partitions of Triangle-free Graphs
论文作者
论文摘要
我们将陈述10个问题，并解决其中的一些问题，以在与Erdős稀疏半猜想有关的无三角形图中进行分区。除其他外，我们证明了以下版本：对于每个足够大的整数$ n $，以下都保持着。 $ N $ VERTICES上的每个无三角形图都有一个分区$ v（g）= a \ cup b $，带有$ | a | = | = | = n/2 $，因此$ e（g [a]）+e（g [b]）\ leq n^2/16 $。该结果很清晰，因为完整的二分图$ 3N/4 $和$ n/4 $达到平等，而$ n $是4的倍数。 此外，我们讨论了$ k_4 $ free图的类似问题。
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\cup B$ 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.
