Sergey Norin: Publications and Preprints

Matching Theory and Pfaffian Orientations:

  1. A new proof of a characterisation of Pfaffian bipartite graphs (with C. H. C. Little and Kee L. Teo),  J. Comb. Theory B 91 (2004), 123-126.
  2. Unions of perfect matchings in cubic graphs (with T. Kaiser and D. Kral'), in "Topics in Discrete Mathematics" (M. Klazar, J. Kratochvil, J. Matousek, R. Thomas, P. Valtr, eds.), Springer (2006), 225-230.
  3. Minimal bricks (with R. Thomas), J. Comb. Theory B 96 (2006), 505-513.
  4. Generating bricks (with R. Thomas), J. Comb. Theory B 97 (2007), 769-817.
  5. Pfaffian graphs, T-joins and crossing numbers, Combinatorica 28 (2008), 89-98.
      (Conference version: Drawing Pfaffian graphs, Graph Drawing, 12th International Symposium, Lecture Notes in Computer Science, 3383 (2005), 371-376.)
  6. Pfaffian labelings and signs of edge-colorings (with R. Thomas), Combinatorica 28 (2008), 99-111.
  7. Minimally non-Pfaffian graphs (with R. Thomas), J. Comb. Theory B 98 (2008), 1038-1055.
  8. Drawing 4-Pfaffian graphs on the torus, Combinatorica 29 (2009), 109-119.
  9. Exponentially many perfect matchings in cubic graphs (with L. Esperet, F. Kardos, A. King and D. Kral'), Adv. Math. 227 (2011), 1646-1664.
  10. Holographic algorithms without matchgates (with J. M. Lansberg and J. Morton), submitted.
Graph Minors:
  1. Proper minor-closed families are small (with P. Seymour, R. Thomas and P. Wollan), J. Comb. Theory B 96 (2006), 754-757.
  2. Small graph classes and bounded expansion (with Z. Dvorak), J. Comb. Theory B 100 (2010), 171-175.
  3. K6 minors in 6-connected graphs of bounded tree-width (with K. Kawarabayashi, R. Thomas and P. Wollan), submitted.
  4. K6 minors in large 6-connected graphs (with K. Kawarabayashi, R. Thomas and P. Wollan), submitted.
Graph Coloring:
  1. The circular chromatic index of flower snarks (with M. Ghebleh, D. Kral' and R. Thomas), Electronic Journal of Combinatorics, 13(1) (2006), #N20, 7pp.
  2. On two questions about circular choosability, J. Graph Theory 58 (2008), 261--269.
  3. Circular degree choosability (with X. Zhu), Electronic Journal of Combinatorics, 15(1) (2008), #R100, 8pp.
  4. Graphs with full rank 3-color matrix and few 3-colorings (with J.-S. Sereni), J. Comb. Theory B 98 (2008), 1115--1116.
  5. Circular choosability via combinatorial Nullstellensatz (with T.-L. Wong and X. Zhu), J. Graph Theory 59 (2008), 190--204.
  6. Circular consecutive choosability of k-choosable graphs (with D. Liu, Z. Pan and X. Zhu), J. Graph Theory, to appear.
Analogies Between Graphs and Riemann Surfaces:
  1. Riemann-Roch and Abel-Jacobi theory on a finite graph (with M. Baker), Adv. Math. 215(2) (2007), 766-788.
  2. Harmonic morphisms and hyperelliptic graphs (with M. Baker), Int. Math. Res. Notices (2009), 42 pp.
  3. Jacobians of near-complete and threshold graphs (with P. Whalen), European J. Combin., to appear.
  4. Rank of divisors on tropical curves (with J. Hladky and D. Kral'), submitted.
Extremal Graph Theory:
  1. Undecidability of linear inequalities in graph homomorphism densities (with H. Hatami), J. Amer. Math. Soc., 24 (2011), 547-565.
  2. Turan graphs and the number of colorings, SIAM J. Discrete Math., 25 (2011), 260--266.
  3. Counting flags in triangle-free digraphs (with J. Hladky and D. Kral'), submitted.
  4. On the number of pentagons in triangle-free graphs (with H. Hatami, J. Hladky, D. Kral' and A. Razborov), submitted.
  5. Non-three-colorable common graphs exist (with H. Hatami, J. Hladky, D. Kral' and A. Razborov).
Other Topics:
  1. A polynomial lower bound for the size of a k-min-wise independent set of permutations,  J. Math. Sci. (N. Y.) 118 (2003), no. 2, 4994-5000.
  2. Set intersections, perfect graphs, and voting in agreeable societies (with D. E. Berg, F. E. Su, R. Thomas and P. Wollan), Am. Math. Mon. 117 (2010), 27-39.
  3. Markov bases of binary graph models of K4-minor free graphs (with D. Kral' and O. Pangrac), J. Comb. Theory A 117 (2010), 759-765.