2-colouring shift-chains
Abstract
A shift-chain is an $ r $-uniform hypergraph $ \mathcal{H} $ on vertex set $ [n] $ with the property that, for any two edges $ \{ e_1, \ldots, e_r \} $ and $ \{ f_1, \ldots, f_r \} $ with $ e_1 < \cdots < e_r $ and $ f_1 < \cdots < f_r $, either $ e_i \le f_i $ for all $ i \in [r] $ or $ f_i \le e_i $ for all $ i \in [r] $. It is known that all shift-chains are properly vertex-colourable with three colours (that is, such that no edge is monochromatic), which is optimal for $ r \in \{ 2, 3 \} $. It was asked by Pálvölgyi in 2010 whether all shift-chains of sufficiently large uniformity are properly $ 2 $-colourable. We answer this question in a strong form, proving that in fact all shift-chains of uniformity at least $ 4 $ are properly $ 2 $-colourable. The colouring is obtained via a natural algorithm with linear running time.
Related
- The List Total Colouring Conjecture is False
- The Partial List Colouring Conjecture is False
- The forced colouring function of a graph
- Isomorphisms of abelian Cayley graphs with their natural edge-colouring
- Degreewise Cut-Semigroup Saturation for K5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
BibTeX
@misc{smith20262colouring,
title = {{2-colouring shift-chains}},
author = {Zak Smith},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31549},
eprint = {2609.31549},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31549},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - 2-colouring shift-chains
AU - Zak Smith
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31549
UR - https://arxiv.org/abs/2609.31549
AB - A shift-chain is an $ r $-uniform hypergraph $ \mathcal{H} $ on vertex set $ [n] $ with the property that, for any two edges $ \{ e_1, \ldots, e_r \} $ and $ \{ f_1, \ldots, f_r \} $ with $ e_1 < \cdots < e_r $ and $ f_1 < \cdots < f_r $, either $ e_i \le f_i $ for all $ i \in [r] $ or $ f_i \le e_i $ for all $ i \in [r] $. It is known that all shift-chains are properly vertex-colourable with three colours (that is, such that no edge is monochromatic), which is optimal for $ r \in \{ 2, 3 \} $. It was asked by Pálvölgyi in 2010 whether all shift-chains of sufficiently large uniformity are properly $ 2 $-colourable. We answer this question in a strong form, proving that in fact all shift-chains of uniformity at least $ 4 $ are properly $ 2 $-colourable. The colouring is obtained via a natural algorithm with linear running time.
ER -