6 papers
Two Relaxations of the Dominating Hadwiger's Conjecture
António Girão, Sergey Norin, Youri Tamitegama +1
Illingworth and Wood recently proposed the Dominating Hadwiger's Conjecture, a strengthening of Hadwiger's Conjecture which asserts that every graph with no dominating -model…
The Dominating 4-Colour Theorem
António Girão, Freddie Illingworth, Bojan Mohar +6
A "dominating -model" in a graph is a sequence of pairwise vertex-disjoint connected subgraphs of , such that whenever every vertex…
A Recolouring Version of a Conjecture of Reed
Lucas De Meyer, Clément Legrand-Duchesne, Jared León +2
Reed conjectured that the chromatic number of any graph is closer to its clique number than to its maximum degree plus one. We consider a recolouring version of this conjecture, wi…
Tight Bounds for Hypercube Minor-Universality
Emma Hogan, Lukas Michel, Alex Scott +3
Benjamini, Kalifa and Tzalik recently proved that there is an absolute constant such that any graph with at most edges and no isolated vertices is a minor of th…
Clustered Colouring of Graph Products
Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +5
A colouring of a graph has clustering if the maximum number of vertices in a monochromatic component equals . Motivated by recent results showing that many natural graph…
Small families of partially shattering permutations
António Girão, Lukas Michel, Youri Tamitegama
We say that a family of permutations -shatters a set if it induces at least distinct permutations on that set. What is the minimum number of permutations of $\{1,…