论文标题
平衡数字和列表平衡某些图类类的数字
The balancing number and list balancing number of some graph classes
论文作者
论文摘要
给定图表$ g $，如果我们能找到$ g $的副本，则据说$ k_n $的边缘的2个颜色包含$ g $的平衡副本，以便每个颜色类别中的一半边缘。如果存在一个整数$ k $，这样，对于$ n $，每2色$ k_n $，每种颜色的$ k $边缘都包含$ g $的平衡副本，那么我们说$ g $是可衡量的。最小的整数$ k $使得该保留称为$ g $的平衡数。 在本文中，我们通过考虑$ k_n $的2上边缘颜色来定义平衡数字的更一般的变体，即平衡数字，其中每个边缘$ e $都有关联的列表$ l（e）$，这是颜色集$ \ \ {r，b \ \} $的非平淡子集。在这种情况下，边缘$ e $带有$ l（e）= \ {r，b \} $充当开玩笑的，因为可以根据需要选择其颜色$ r $或$ b $。与平衡数字相反，每个图都有一个列表平衡数字。而且，如果存在平衡数字，则它与列表平衡数字一致。 我们给出了所有周期的列表平衡号码的确切值，除了$ 4K $ -CYCLE，我们给出了紧密的界限。此外，我们为列表提供了一般界限，该列表平衡了基于其子图的最大数量的非实用图表的数量，并研究了$ k_5 $的列表平衡数量，事实证明这很大。
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 is in each color class. If there exists an integer $k$ such that, for $n$ sufficiently large, every 2-coloring of $K_n$ with more than $k$ edges in each color contains a balanced copy of $G$, then we say that $G$ is balanceable. The smallest integer $k$ such that this holds is called the balancing number of $G$. In this paper, we define a more general variant of the balancing number, the list balancing number, by considering 2-list edge colorings of $K_n$, where every edge $e$ has an associated list $L(e)$ which is a nonempty subset of the color set $\{r,b\}$. In this case, edges $e$ with $L(e) = \{r,b\}$ act as jokers in the sense that their color can be chosen $r$ or $b$ as needed. In contrast to the balancing number, every graph has a list balancing number. Moreover, if the balancing number exists, then it coincides with the list balancing number. We give the exact value of the list balancing number for all cycles except for $4k$-cycles for which we give tight bounds. In addition, we give general bounds for the list balancing number of non-balanceable graphs based on the extremal number of its subgraphs, and study the list balancing number of $K_5$, which turns out to be surprisingly large.
