论文标题
关于某些图类的平衡性
On the balanceability of some graph classes
论文作者
论文摘要
给定图表$ g $，如果我们能找到$ g $的副本，则据说$ k_n $的边缘的2个颜色包含$ g $的平衡副本，以便每个颜色类别中的一半边缘。如果对于每个足够大的$ n $，都存在一个整数$ k $，以便每种颜色的$ k_n $的每2个颜色$ k_n $都包含$ g $的平衡副本，那么我们说$ g $是可以平衡的。 Caro，Hansberg和Montejano引入了平衡性，他们还提供了可平衡图的结构表征。 在本文中，我们通过找到可使图形是否可以平衡的新条件来扩展了对平衡性的研究。我们使用这些条件充分表征图形类别（例如矩形和三角形网格）以及特殊类别的循环图的平衡性。
Given a graph $G$, a 2-coloring of the edges of $K_n$ is said to contain a balanced copy of $G$ if we can find a copy of $G$ such that half of its edges are in each color class. If, for every sufficiently large $n$, there exists an integer $k$ such that every 2-coloring of $K_n$ with more than $k$ edges in each color class contains a balanced copy of $G$, then we say that $G$ is balanceable. Balanceability was introduced by Caro, Hansberg and Montejano, who also gave a structural characterization of balanceable graphs. In this paper, we extend the study of balanceability by finding new sufficient conditions for a graph to be balanceable or not. We use those conditions to fully characterize the balanceability of graph classes such as rectangular and triangular grids, as well as a special class of circulant graphs.
