2025/12/15 by Finbow, Stephen, MacGillivray, Gary
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2512.13864
For a graph G and a positive integer k, the k-Bell colour graph of G is the graph whose vertices are the partitions of V into at most k independent sets, with two of these being adjacent if there exists a vertex x such that the partitions are identical when restricted to V - \x\. The k-Stirling Colour graph of G is defined similarly, but for partitions into exactly k independent sets. We show that every graph on n vertices, except Kn and Kn - e, has a Hamiltonian n-Bell colour graph, and this result is best possible. It is also shown that, for k ≥ 4, the k-Stirling colour graph of a tree with at least k+1 vertices is Hamiltonian, and the 3-Bell colour graph of a tree with at least 3 vertices is Hamiltonian.