Sergey Norin

Professor and Peter Redpath Chair of Pure Mathematics

Department of Mathematics and Statistics, McGill University

99 papers · 16 preprints

All preprints are on arXiv; see also the CV.

Graph Minors

  1. preprintA proof of the linear Hadwiger conjecture (with R. Steiner). arXiv:2610.05291.
  2. preprintEvery graph with no K7= minor is 6-colorable (with Z. Dvořák and N. Rahman). arXiv:2609.17760.
  3. preprintTwo relaxations of the dominating Hadwiger's conjecture (with A. Girão, Y. Tamitegama and J. Tan). arXiv:2608.12126.
  4. preprintEvery graph with no K7∨-minor is 6-colorable (with A. Totschnig). arXiv:2507.03244.
  5. preprintDensities of minor-closed graph classes are rational (with R. Kapadia). arXiv:2009.13482.
  6. preprintIslands in minor-closed classes. I. Bounded treewidth and separators (with Z. Dvořák). arXiv:1710.02727.
  7. 2026The dominating 4-colour theorem (with A. Girão, F. Illingworth, B. Mohar, R. Steiner, Y. Tamitegama, J. Tan, D. R. Wood and J. H. Yip). Int. Math. Res. Not. IMRN, to appear.
  8. 2026Dense minors of graphs with independence number two (with P. Seymour). J. Combin. Theory Ser. B 176 (2026), 101–110.
  9. 2025Limits of degeneracy for colouring graphs with forbidden minors (with J. Turcotte). Trans. Amer. Math. Soc. 378 (2025), 6425–6451.
  10. 2025Finding dense minors using average degree (with K. Hendrey, R. Steiner and J. Turcotte). J. Graph Theory 108 (2025), 205–223.
  11. 2024On an induced version of Menger's theorem (with K. Hendrey, R. Steiner and J. Turcotte). Electron. J. Combin. 31(4) (2024), #P4.28.
  12. 2023Recent progress towards Hadwiger's conjecture. In Proc. Int. Congr. Math. 2022, Vol. 6, EMS Press (2023), 4606–4620.
  13. 2023Breaking the degeneracy barrier for coloring graphs with no Kt minor (with L. Postle and Z.-X. Song). Adv. Math. 422 (2023), 109020.
  14. 2023On 2-cycles of graphs (with R. Thomas and H. van der Holst). J. Combin. Theory Ser. B 162 (2023), 184–222.
  15. 2023Connectivity and choosability of graphs with no Kt minor (with L. Postle). J. Combin. Theory Ser. B 158 (2023), 283–300.
  16. 2023Clustered colouring of graph classes with bounded treedepth or pathwidth (with A. Scott and D. R. Wood). Combin. Probab. Comput. 32 (2023), 122–133.
  17. 2022Testability and local certification of monotone properties in minor-closed classes (with L. Esperet). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), LIPIcs 229 (2022), 58:1–58:15.
  18. 2022Extremal functions for sparse minors (with K. Hendrey and D. R. Wood). Adv. Comb. 2022:5, 43 pp.
  19. 2022A new upper bound on the chromatic number of graphs with no odd Kt minor (with Z.-X. Song). Combinatorica 42 (2022), 137–149.
  20. 2022Obstructions for partitioning into forests and outerplanar graphs (with R. Kim and S. Oum). Discrete Appl. Math. 312 (2022), 15–28.
  21. 2021Asymptotic density of graphs excluding disconnected minors (with R. Kapadia and Y. Qian). J. Combin. Theory Ser. B 146 (2021), 151–175.
  22. 2020A lower bound on the average degree forcing a minor (with B. Reed, A. Thomason and D. R. Wood). Electron. J. Combin. 27(2) (2020), #P2.4.
  23. 2019Clustered colouring in minor-closed classes (with A. Scott, P. Seymour and D. R. Wood). Combinatorica 39 (2019), 1387–1412.
  24. 2019K6 minors in 6-connected graphs of bounded tree-width (with K. Kawarabayashi, R. Thomas and P. Wollan). J. Combin. Theory Ser. B 136 (2019), 1–32.
  25. 2018K6 minors in large 6-connected graphs (with K. Kawarabayashi, R. Thomas and P. Wollan). J. Combin. Theory Ser. B 129 (2018), 158–203.
  26. 2017The extremal function for disconnected minors (with E. Csóka, I. Lo, H. Wu and L. Yepremyan). J. Combin. Theory Ser. B 126 (2017), 162–174.
  27. 2016Non-planar extensions of subdivisions of planar graphs (with R. Thomas). J. Combin. Theory Ser. B 121 (2016), 326–366.
  28. 2015New tools and results in graph minor structure theory. In Surveys in Combinatorics 2015, London Math. Soc. Lecture Note Ser. 424, Cambridge Univ. Press (2015), 221–260.
  29. 2006Proper minor-closed families are small (with P. Seymour, R. Thomas and P. Wollan). J. Combin. Theory Ser. B 96 (2006), 754–757.

Extremal Combinatorics

  1. preprintOptimizing the CGMS upper bound on Ramsey numbers (with P. Gupta, N. Ndiaye and L. Wei). arXiv:2407.19026.
  2. preprintOn the density of matroids omitting a complete-graphic minor (with P. Nelson and F. Rivera Omana). arXiv:2306.15061.
  3. preprintAsymptotics of Ramsey numbers of double stars (with Y. R. Sun and Y. Zhao). arXiv:1605.03612.
  4. preprintTriangle-independent sets vs. cuts (with Y. R. Sun). arXiv:1602.04370.
  5. 2026Small hitting sets for longest paths and cycles (with R. Steiner, S. Thomassé and P. Wollan). Proc. Amer. Math. Soc. 154 (2026), 2319–2335.
  6. 2025Twin-width of sparse random graphs (with K. Hendrey, R. Steiner and J. Turcotte). Combin. Probab. Comput. 34 (2025), 401–420.
  7. 2024The inducibility of oriented stars (with P. Hu, J. Ma and H. Wu). J. Combin. Theory Ser. B 168 (2024), 11–46.
  8. 2023Crossing numbers of complete bipartite graphs (with J. Balogh, B. Lidický, F. Pfender, G. Salazar and S. Spiro). Procedia Comput. Sci. 223 (2023), 78–87.
  9. 2023Every graph is eventually Turán-good (with N. Morrison, J. D. Nir, P. Rzążewski and A. Wesolek). J. Combin. Theory Ser. B 162 (2023), 231–243.
  10. 2023The spectrum of triangle-free graphs (with J. Balogh, F. C. Clemen, B. Lidický and J. Volec). SIAM J. Discrete Math. 37 (2023), 1173–1179.
  11. 2022Non-bipartite k-common graphs (with D. Král', J. A. Noel, J. Volec and F. Wei). Combinatorica 42 (2022), 87–114.
  12. 2021The smallest matroids with no large independent flat (with P. Nelson). Electron. J. Combin. 28(1) (2021), #P1.31.
  13. 2021Bounding the number of cycles in a graph in terms of its degree sequence (with Z. Dvořák, N. Morrison, J. A. Noel and L. Postle). European J. Combin. 91 (2021), 103206.
  14. 2019A Turán theorem for extensions via an Erdős–Ko–Rado theorem for Lagrangians (with A. Bene Watts and L. Yepremyan). Combinatorica 39 (2019), 1149–1171.
  15. 2019On the boundary of the region defined by homomorphism densities (with H. Hatami). J. Comb. 10 (2019), 203–219.
  16. 2019A bound on the inducibility of cycles (with D. Král' and J. Volec). J. Combin. Theory Ser. A 161 (2019), 359–363.
  17. 2018Turán numbers of extensions (with L. Yepremyan). J. Combin. Theory Ser. A 155 (2018), 476–492.
  18. 2017Counting flags in triangle-free digraphs (with J. Hladký and D. Král'). Combinatorica 37 (2017), 49–76.
  19. 2017Turán number of generalized triangles (with L. Yepremyan). J. Combin. Theory Ser. A 146 (2017), 312–343.
  20. 2016Erdős–Szekeres without induction (with Y. Yuditsky). Discrete Comput. Geom. 55 (2016), 963–971.
  21. 2015Sparse halves in dense triangle-free graphs (with L. Yepremyan). J. Combin. Theory Ser. B 115 (2015), 1–25.
  22. 2014The inducibility of blow-up graphs (with H. Hatami and J. Hirst). J. Combin. Theory Ser. B 109 (2014), 196–212.
  23. 2013On the number of pentagons in triangle-free graphs (with H. Hatami, J. Hladký, D. Král' and A. Razborov). J. Combin. Theory Ser. A 120 (2013), 722–732.
  24. 2012Non-three-colorable common graphs exist (with H. Hatami, J. Hladký, D. Král' and A. Razborov). Combin. Probab. Comput. 21 (2012), 734–742.
  25. 2011Undecidability of linear inequalities in graph homomorphism densities (with H. Hatami). J. Amer. Math. Soc. 24 (2011), 547–565.
  26. 2011Turán graphs and the number of colorings. SIAM J. Discrete Math. 25 (2011), 260–266.

Sparse Graph Classes

  1. preprintNerve-type and invariance theorems for asymptotic dimension (with C.-H. Liu). arXiv:2607.24146.
  2. preprintDisproof of the tree product conjecture via the Heisenberg group (with F. Illingworth and R. Steiner). arXiv:2607.03041.
  3. preprintTrade-off between spread and width for tree decompositions (with H. L. Bodlaender, C. Groenland and N. Rahman). arXiv:2601.04040.
  4. preprintProduct structure and tree-decompositions (with C.-H. Liu and D. R. Wood). arXiv:2410.20333.
  5. 2025Asymptotic dimension of intersection graphs (with Z. Dvořák). European J. Combin. 123 (2025), 103631.
  6. 2024Three-dimensional graph products with unbounded stack-number (with D. Eppstein, R. Hickingbotham, L. Merker, M. T. Seweryn and D. R. Wood). Discrete Comput. Geom. 71 (2024), 1210–1237.
  7. 2021Sublinear separators in intersection graphs of convex shapes (with Z. Dvořák and R. McCarty). SIAM J. Discrete Math. 35 (2021), 1149–1164.
  8. 2019Treewidth of graphs with balanced separations (with Z. Dvořák). J. Combin. Theory Ser. B 137 (2019), 137–144.
  9. 2018Treewidth of grid subsets (with E. Berger and Z. Dvořák). Combinatorica 38 (2018), 1337–1352.
  10. 2018Orthogonal tree decompositions of graphs (with V. Dujmović, G. Joret, P. Morin and D. R. Wood). SIAM J. Discrete Math. 32 (2018), 839–863; corrigenda, ibid. 32 (2018), 3003–3004, and 38 (2024), 3220–3221.
  11. 2016Strongly sublinear separators and polynomial expansion (with Z. Dvořák). SIAM J. Discrete Math. 30 (2016), 1095–1101.
  12. 2010Small graph classes and bounded expansion (with Z. Dvořák). J. Combin. Theory Ser. B 100 (2010), 171–175.

Hereditary Graph Classes

  1. 2025Typical structure of hereditary graph families. II. Exotic examples (with Y. Yuditsky). Random Structures Algorithms 66 (2025), e21272.
  2. 2025Typical structure of hereditary graph families. I. Apex-free families (with Y. Yuditsky). Random Structures Algorithms 66 (2025), e21271.
  3. 2024Typical structure of hereditary properties of binary matroids (with S. Grosser, H. Hatami and P. Nelson). J. Combin. Theory Ser. B 167 (2024), 283–302.
  4. 2024Cops and robbers on P5-free graphs (with M. Chudnovsky, P. Seymour and J. Turcotte). SIAM J. Discrete Math. 38 (2024), 845–856.
  5. 2015Excluding a substar and an antisubstar (with M. Chudnovsky, B. Reed and P. Seymour). SIAM J. Discrete Math. 29 (2015), 297–308.
  6. 2013The entropy of random-free graphons and properties (with H. Hatami). Combin. Probab. Comput. 22 (2013), 517–526.

Matching Theory and Pfaffian Orientations

  1. 2013Holographic algorithms without matchgates (with J. M. Landsberg and J. Morton). Linear Algebra Appl. 438 (2013), 782–795.
  2. 2011Exponentially many perfect matchings in cubic graphs (with L. Esperet, F. Kardoš, A. King and D. Král'). Adv. Math. 227 (2011), 1646–1664.
  3. 2009Drawing 4-Pfaffian graphs on the torus. Combinatorica 29 (2009), 109–119.
  4. 2008Minimally non-Pfaffian graphs (with R. Thomas). J. Combin. Theory Ser. B 98 (2008), 1038–1055.
  5. 2008Pfaffian labelings and signs of edge-colorings (with R. Thomas). Combinatorica 28 (2008), 99–111.
  6. 2008Pfaffian graphs, T-joins and crossing numbers. Combinatorica 28 (2008), 89–98.Conference version: Drawing Pfaffian graphs, in Graph Drawing (GD 2004), Lecture Notes in Comput. Sci. 3383 (2005), 371–376.
  7. 2007Generating bricks (with R. Thomas). J. Combin. Theory Ser. B 97 (2007), 769–817.
  8. 2006Minimal bricks (with R. Thomas). J. Combin. Theory Ser. B 96 (2006), 505–513.
  9. 2006Unions of perfect matchings in cubic graphs (with T. Kaiser and D. Král'). In Topics in Discrete Mathematics (M. Klazar, J. Kratochvíl, M. Loebl, J. Matoušek, R. Thomas and P. Valtr, eds.), Algorithms Combin. 26, Springer (2006), 225–230.
  10. 2005Matching structure and Pfaffian orientations of graphs. Ph.D. thesis, Georgia Institute of Technology (2005).
  11. 2004A new proof of a characterisation of Pfaffian bipartite graphs (with C. H. C. Little and K. L. Teo). J. Combin. Theory Ser. B 91 (2004), 123–126.

Graph Coloring and Flows

  1. preprintNowhere-zero flow reconfiguration (with L. Esperet, K. Hendrey, A. Lagoutte, M. Marseloo and R. Steiner). arXiv:2512.17342.
  2. preprint3-colouring planar graphs (with V. Dujmović, P. Morin and D. R. Wood). arXiv:2507.03163.
  3. 2026Strong parity edge-colorings of graphs (with P. Bradshaw and D. B. West). European J. Combin. 134 (2026), 104343.
  4. 2026Defective coloring of blowups (with R. Steiner). Electron. J. Combin. 33(1) (2026), #P1.17.
  5. 2025Sparsity of 3-flow-critical graphs (with Z. Dvořák). European J. Combin. 128 (2025), 104174.
  6. 2024Weak diameter coloring of graphs on surfaces (with Z. Dvořák). European J. Combin. 121 (2024), 103845.
  7. 2022Counterexamples to a conjecture of Harris on Hall ratio (with A. Blumenthal, B. Lidický, R. R. Martin, F. Pfender and J. Volec). SIAM J. Discrete Math. 36 (2022), 1678–1686.
  8. 2019List coloring with requests (with Z. Dvořák and L. Postle). J. Graph Theory 92 (2019), 191–206.
  9. 2011Circular consecutive choosability of k-choosable graphs (with D. Liu, Z. Pan and X. Zhu). J. Graph Theory 67 (2011), 178–197.
  10. 2008Circular choosability via combinatorial Nullstellensatz (with T.-L. Wong and X. Zhu). J. Graph Theory 59 (2008), 190–204.
  11. 2008Graphs with full rank 3-color matrix and few 3-colorings (with J.-S. Sereni). J. Combin. Theory Ser. B 98 (2008), 1115–1116.
  12. 2008Circular degree choosability (with X. Zhu). Electron. J. Combin. 15(1) (2008), #R100.
  13. 2008On two questions about circular choosability. J. Graph Theory 58 (2008), 261–269.
  14. 2006The circular chromatic index of flower snarks (with M. Ghebleh, D. Král' and R. Thomas). Electron. J. Combin. 13(1) (2006), #N20.

Analogies Between Graphs and Riemann Surfaces

  1. 2013Rank of divisors on tropical curves (with J. Hladký and D. Král'). J. Combin. Theory Ser. A 120 (2013), 1521–1538.
  2. 2011Jacobians of nearly complete and threshold graphs (with P. Whalen). European J. Combin. 32 (2011), 1368–1376.
  3. 2009Harmonic morphisms and hyperelliptic graphs (with M. Baker). Int. Math. Res. Not. IMRN 2009, no. 15, 2914–2955.
  4. 2007Riemann–Roch and Abel–Jacobi theory on a finite graph (with M. Baker). Adv. Math. 215 (2007), 766–788.

Game Theory

  1. 2021Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality? (with N. Ndiaye and A. Vetta). In Algorithmic Game Theory (SAGT 2021), Lecture Notes in Comput. Sci. 12885 (2021), 281–295.
  2. 2015Large supports are required for well-supported Nash equilibria (with Y. Anbalagan, H. Huang, S. Lovett, A. Vetta and H. Wu). In APPROX/RANDOM 2015, LIPIcs 40 (2015), 78–84.
  3. 2014A near-optimal mechanism for impartial selection (with N. Bousquet and A. Vetta). In Web and Internet Economics (WINE 2014), Lecture Notes in Comput. Sci. 8877 (2014), 133–146.
  4. 2013A counterexample to a conjecture of Schwartz (with F. Brandt, M. Chudnovsky, I. Kim, G. Liu, A. Scott, P. Seymour and S. Thomassé). Soc. Choice Welf. 40 (2013), 739–743.
  5. 2013Polylogarithmic supports are required for approximate well-supported Nash equilibria below 2/3 (with Y. Anbalagan, R. Savani and A. Vetta). In Web and Internet Economics (WINE 2013), Lecture Notes in Comput. Sci. 8289 (2013), 15–23.
  6. 2010Voting in agreeable societies (with D. E. Berg, F. E. Su, R. Thomas and P. Wollan). Amer. Math. Monthly 117 (2010), 27–39.

Other Topics

  1. 2024The burning number conjecture holds asymptotically (with J. Turcotte). J. Combin. Theory Ser. B 168 (2024), 208–235.
  2. 2022Torsion groups do not act on 2-dimensional CAT(0) complexes (with D. Osajda and P. Przytycki). Duke Math. J. 171 (2022), 1379–1415.
  3. 2021Virtually fibering right-angled Coxeter groups (with K. Jankiewicz and D. T. Wise). J. Inst. Math. Jussieu 20 (2021), 957–987.
  4. 2019A distribution on triples with maximum entropy marginal. Forum Math. Sigma 7 (2019), e46.
  5. 2018Distribution of coefficients of rank polynomials for random sparse graphs (with D. Jakobson, C. MacRury and L. Turner). Electron. J. Combin. 25(4) (2018), #P4.50.
  6. 2016Flag algebras and the stable coefficients of the Jones polynomial (with S. Garoufalidis and T. Vuong). European J. Combin. 51 (2016), 165–189.
  7. 2010Markov bases of binary graph models of K4-minor free graphs (with D. Král' and O. Pangrác). J. Combin. Theory Ser. A 117 (2010), 759–765.
  8. 2003A polynomial lower bound for the size of a k-min-wise independent set of permutations. J. Math. Sci. (N.Y.) 118 (2003), 4994–5000.
  9. manuscriptConnectivity of addable classes of forests. Manuscript.
  10. manuscriptHigh dimensional bramble lemma. Manuscript.