25 citations · 246 across the 55 of their papers we have counts for
65 papers
Every graph with no minor is 6-colorable
Zdeněk Dvořák, Sergey Norin, Neil Rahman
The first open case of Hadwiger's conjecture states that every -minor-free graph is 6-colorable. We prove that this is the case for -minor-free graphs, where de…
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, She…
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…
Optimizing the CGMS upper bound on Ramsey numbers
Parth Gupta, Ndiame Ndiaye, Sergey Norin +1
In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the diagonal Ramsey numbers since 1935. We shor…
Sparsity of 3-flow critical graphs
Zdeněk Dvořák, Sergey Norin
A connected graph G is 3-flow-critical if G does not have a nowhere-zero 3-flow, but every proper contraction of G does. We prove that every n-vertex 3-flow-critical graph other th…
Finding dense minors using average degree
Kevin Hendrey, Sergey Norin, Raphael Steiner +1
Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible -vertex minor in graphs of average degree at least . We show that if has averag…
On the density of matroids omitting a complete-graphic minor
Peter Nelson, Sergey Norin, Fernanda Rivera Omana
We show that, if is a simple rank- matroid with no -point line minor and no minor isomorphic to the cycle matroid of a -vertex complete graph, then the ratio $|M| /…
Limits of degeneracy for colouring graphs with forbidden minors
Sergey Norin, Jérémie Turcotte
Motivated by Hadwiger's conjecture, Seymour asked which graphs have the property that every non-null graph with no minor has a vertex of degree at most . We s…
Cops and robbers on -free graphs
Maria Chudnovsky, Sergey Norin, Paul Seymour +1
We prove that every connected -free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected -free grap…
Every graph is eventually Turán-good
Natasha Morrison, JD Nir, Sergey Norin +2
Let be a graph. We show that if is large enough as a function of , then the -partite Turán graph maximizes the number of copies of among all -free graphs…
The Burning Number Conjecture Holds Asymptotically
Sergey Norin, Jérémie Turcotte
The burning number of a graph is the smallest number of turns required to burn all vertices of a graph if at every turn a new fire is started and existing fires spread t…
Dense minors of graphs with independence number two
Sergey Norin, Paul Seymour
Motivated by Hadwiger's conjecture, we prove that every -vertex graph with no independent set of size three contains an -vertex simple minor with $$0.9…
The Spectrum of Triangle-free Graphs
József Balogh, Felix Christian Clemen, Bernard Lidický +2
Denote by the smallest eigenvalue of the signless Laplacian matrix of an -vertex graph . Brandt conjectured in 1997 that for regular triangle-free graphs $q_n(G) \le…
Three-dimensional graph products with unbounded stack-number
David Eppstein, Robert Hickingbotham, Laura Merker +3
We prove that the stack-number of the strong product of three -vertex paths is . The best previously known upper bound was . No non-trivial lower bound was kno…
Asymptotic dimension of intersection graphs
Zdeněk Dvořák, Sergey Norin
We show that intersection graphs of compact convex sets in R^n of bounded aspect ratio have asymptotic dimension at most 2n+1. More generally, we show this is the case for intersec…
Testability and local certification of monotone properties in minor-closed classes
Louis Esperet, Sergey Norin
The main problem in the area of graph property testing is to understand which graph properties are \emph{testable}, which means that with constantly many queries to any input graph…
Weak diameter coloring of graphs on surfaces
Zdeněk Dvořák, Sergey Norin
Consider a graph drawn on a fixed surface, and assign to each vertex a list of colors of size at least two if is triangle-free and at least three otherwise. We prove that w…
Extremal functions for sparse minors
Kevin Hendrey, Sergey Norin, David R. Wood
The "extremal function" of a graph is the supremum of densities of graphs not containing as a minor, where the "density" of a graph is the ratio of the number of…
Typical structure of hereditary properties of binary matroids
Stefan Grosser, Hamed Hatami, Peter Nelson +1
We prove an arithmetic analogue of the typical structure theorem for graph hereditary properties due to Alon, Balogh, Bollobás and Morris.
Clustered colouring of graph classes with bounded treedepth or pathwidth
Sergey Norin, Alex Scott, David R. Wood
The "clustered chromatic number" of a class of graphs is the minimum integer such that for some integer every graph in the class is -colourable with monochromatic compon…