论文标题
跨越树木和汉密尔顿周期的差异
Discrepancies of Spanning Trees and Hamilton Cycles
论文作者
论文摘要
我们研究了跨越树木和汉密尔顿周期的多色差异。作为我们的主要结果，我们表明，在非常温和的条件下，$ r $ - 彩色跨越图$ g $的树的差异是相等的，直至不变，至最低$ s $，因此可以通过删除$ s $ $ $ $ s $ Vertices将$ g $相等的部分分为$ r $相等的部分。可以说，这一结果可以解决在所有感兴趣图中估算跨越树差异的问题。特别是，它使我们能够立即推断出在最近的Balogh，csaba，jing和Pluhár中出现的大多数结果，以更广泛的一般性和任何数量的颜色证明它们。我们还获得了几个新的结果，例如确定HyperCube的跨越树差异。对于具有某些扩展特性的图形的特殊情况，我们获得了精确的渐近界。 我们还研究了汉密尔顿周期的多色差异，这表明，在任何$ r $ $ r $ po的颜色中，具有$ n $ pertices的图表的边缘和至少$ \ frac {r + 1} {2r} {2r} {2r} n + d $至少有$ \ $ \ frac} + frac {rac {rac {rac { 颜色。这扩展了Balogh等人的结果，Balogh等人建立了案例$ r = 2 $。在此结果中，常数$ \ frac {r+1} {2r} $是最佳的；它不能被任何较小的常数所取代。
We study the multicolour discrepancy of spanning trees and Hamilton cycles in graphs. As our main result, we show that under very mild conditions, the $r$-colour spanning-tree discrepancy of a graph $G$ is equal, up to a constant, to the minimum $s$ such that $G$ can be separated into $r$ equal parts by deleting $s$ vertices. This result arguably resolves the question of estimating the spanning-tree discrepancy in essentially all graphs of interest. In particular, it allows us to immediately deduce as corollaries most of the results that appear in a recent paper of Balogh, Csaba, Jing and Pluhár, proving them in wider generality and for any number of colours. We also obtain several new results, such as determining the spanning-tree discrepancy of the hypercube. For the special case of graphs possessing certain expansion properties, we obtain exact asymptotic bounds. We also study the multicolour discrepancy of Hamilton cycles in graphs of large minimum degree, showing that in any $r$-colouring of the edges of a graph with $n$ vertices and minimum degree at least $\frac{r+1}{2r}n + d$, there must exist a Hamilton cycle with at least $\frac{n}{r} + 2d$ edges in some colour. This extends a result of Balogh et al., who established the case $r = 2$. The constant $\frac{r+1}{2r}$ in this result is optimal; it cannot be replaced by any smaller constant.
