Discrepancies of spanning trees and Hamilton cycles
OPEN ACCESS
Loading...
Author / Producer
Date
2022-05
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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 [Formula presented], there must exist a Hamilton cycle with at least [Formula presented] edges in some colour. This extends a result of Balogh et al., who established the case r=2. The constant [Formula presented] in this result is optimal; it cannot be replaced by any smaller constant.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
154
Pages / Article No.
262 - 291
Publisher
Academic Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Discrepancy; Spanning tree; Hamilton cycle
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin