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…
Nerve-type and invariance theorems for asymptotic dimension
Chun-Hung Liu, Sergey Norin
Asymptotic dimension of metric spaces is a large-scale analog of covering dimension of topological spaces. An intersection graph of a family of sets is the graph whose vertices are…
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…
Every graph with no -minor is -colorable
Sergey Norin, Agnes Totschnig
Let denote the graph obtained from the complete graph on seven vertices by deleting two edges with a common end. Motivated by Hadwiger's conjecture, we prove that ever…
3-Colouring Planar Graphs
Vida DujmoviÄ, Pat Morin, Sergey Norin +1
We show that every -vertex planar graph is 3-colourable with monochromatic components of size . The best previous bound was due to Linial, MatouÅ¡ek, Sh…
Product Structure and Tree-Decompositions
Chun-Hung Liu, Sergey Norin, David R. Wood
This paper explores the structure of graphs defined by an excluded minor or an excluded odd minor through the lens of graph products and tree-decompositions. We prove that every gr…