25 citations · 246 across the 55 of their papers we have counts for
9 papers · 1 filter
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…
Densities of minor-closed graph classes are rational
Rohan Kapadia, Sergey Norin
For a graph class , let denote the maximum number of edges in a graph in on vertices. We show that for every proper minor-close…
The inducibility of oriented stars
Ping Hu, Jie Ma, Sergey Norin +1
We consider the problem of maximizing the number of induced copies of an oriented star in digraphs of given size, where the center of the star has out-degree and i…
Descending the Stable Matching Lattice: How many Strategic Agents are required to turn Pessimality to Optimality?
Ndiame Ndiaye, Sergey Norin, Adrian Vetta
The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the gi…
Typical structure of hereditary graph families. II. Exotic examples
Sergey Norin, Yelena Yuditsky
A graph is -free if it does not contain an induced subgraph isomorphic to . The study of the typical structure of -free graphs was initiated by Erdős, Kleitman and Rot…
Typical structure of hereditary graph families. I. Apex-free families
Sergey Norin, Yelena Yuditsky
A family of graphs is hereditary if is closed under isomorphism and taking induced subgraphs. The speed of is the sequence $\{|\mathcal{F}…
Non-bipartite k-common graphs
Daniel Kral, Jonathan A. Noel, Sergey Norin +2
A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of K_n is asymptotically minimized by a random coloring. For every k, we construct a connected…
Connectivity and choosability of graphs with no minor
Sergey Norin, Luke Postle
In 1943, Hadwiger conjectured that every graph with no minor is -colorable for every . While Hadwiger's conjecture does not hold for list-coloring, the linear…
Sublinear separators in intersection graphs of convex shapes
Zdenek Dvorak, Rose McCarty, Sergey Norin
We give a natural sufficient condition for an intersection graph of compact convex sets in R^d to have a balanced separator of sublinear size. This condition generalizes several pr…