ROBIN THOMAS' PUBLISHED JOURNAL PAPERS

  1. Dvořák, Zdeněk; Král', Daniel; Thomas, Robin Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk. J. Combin. Theory Ser. B 132 (2018), 1–46. arXiv:1302.2158.
  2. Hegde, Rajneesh; Thomas, Robin Non-embeddable extensions of embedded minors. J. Combin. Theory Ser. B 131 (2018), 55–84. arXiv:1401.2973
  3. Kawarabayashi, Ken-ichi; Thomas, Robin;Wollan, Paul A new proof of the flat wall theorem. J. Combin. Theory Ser. B 129 (2018), 204–238. arXiv:1207.6927.
  4. Kawarabayashi, Ken-ichi; Norine, Serguei;Thomas, Robin; Wollan, Paul K6 minors in large 6-connected graphs. J. Combin. Theory Ser. B 129 (2018), 158–203. arXiv:1203.2192
  5. Hoyer, Alexander; Thomas, Robin Four edge-independent spanning trees. SIAM J. Discrete Math. 32 (2018), no. 1,233–248. arXiv:1705.01199.
  6. Postle, Luke; Thomas, Robin Five-list-coloring graphs on surfaces III. One list of size one and one list of size two. J. Combin. Theory Ser. B 128 (2018), 1–16. arXiv:1608.05759.
  7. Robertson, Neil; Seymour, P. D.; Thomas, Robin Cyclically five-connected cubic graphs. J. Combin. Theory Ser. B125 (2017), 132–167. arXiv:1503.02298.
  8. Norin, Sergey; Thomas, Robin Non-planar extensions of subdivisions of planar graphs. J. Combin. Theory Ser. B121 (2016), 326–366. arXiv:1402.1999.
  9. Dvorak, Zdeněk; Kral', Daniel; Thomas, Robin Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle. J. Combin. Theory Ser. B 120 (2016), 1-17. arXiv:1010.2472.
  10. Abbas, Waseem; Egerstedt, Magnus; Liu, Chun-Hung; Thomas, Robin; Whalen, Peter Deploying robots with two sensors in K1,6-free graphs. J. Graph Theory 82 (2016), no. 3, 236-252. arXiv:1308.5450.
  11. Edwards, Katherine; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin Three-edge-colouring doublecross cubic graphs. J. Combin. Theory Ser. B 119 (2016), 66-95. arXiv:1411.4352.
  12. Postle, Luke; Thomas, Robin Five-list-coloring graphs on surfaces II. A linear bound for critical graphs in a disk. J. Combin. Theory Ser. B 119 (2016), 42-65.arXiv:1505.05927.
  13. Thomas, Robin; Whalen, Peter Odd K3,3 subdivisions in bipartite graphs. J. Combin. Theory Ser. B 118 (2016), 76-87.  arXiv:1309.5336
  14. Postle, Luke; Thomas, Robin Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs. J. Combin. Theory Ser. B 111 (2015), 234-241. arXiv:1402.1813.
  15. Dvořak, Zdeněk; Kral', Daniel; Thomas, Robin Testing first-order properties for subclasses of sparse graphs. J. ACM 60 (2013), no. 5, Art. 36, 24 pp.  arXiv:1109.5036. Here is a FOCS 2010 version.
  16. Asadi, Arash; Dvořak, Zdeněk; Postle, Luke; Thomas, Robin Sub-exponentially many 3-colorings of triangle-free planar graphs. J. Combin. Theory Ser. B 103 (213), no. 6, 706--712.  arXiv:1007.1430.
  17. Chenette, Nathan; Postle, Luke; Streib, Noah; Thomas, Robin; Yerger, Carl Five-coloring graphs on the Klein bottle. J. Combin. Theory Ser. B 102 (2012), no. 5, 1067--1098. arXiv:1201.5361.
  18. Hernandez-Velez, Cesar; Salazar, Gelasio; Thomas, Robin Nested cycles in large triangulations and crossing-critical graphs. J. Combin. Theory Ser. B 102 (2012), no. 1, 86--92. arXiv:0911.4690.
  19. Guenin, Bertrand; Thomas, Robin Packing directed circuits exactly. Combinatorica 31 (2011), no. 4, 397--421.  arXiv:1012.2749.
  20. Dvorak, Zdenek; Kawarabayashi, Ken-Ichi; Thomas, Robin Three-coloring triangle-free planar graphs in linear time. ACM Trans. Algorithms 7 (2011), no. 4, Art. 41, 14 pp. arXiv:1302.5121.
  21. Shapira, Asaf; Thomas, Robin Color-critical graphs have logarithmic circumference. Adv. Math. 227 (2011), no. 6, 2309--2326. arXiv:0908.3169
  22. Ding, Guoli; Oporowski, Bogdan; Thomas, Robin; Vertigan, Dirk Large non-planar graphs and an application to crossing-critical graphs. J. Combin. Theory Ser. B 101 (2011), no. 2, 111--121. arXiv:0912.4778
  23. Inkmann, Torsten; Thomas, Robin Minor-minimal planar graphs of even branch-width. Combin. Probab. Comput. 20 (2011), no. 1, 73--82.  arXiv:1007.0373
  24. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin K_4-free graphs with no odd holes. J. Combin. Theory Ser. B 100 (2010), no. 3, 313--331.
  25. Berg, Deborah E.; Norine, Serguei; Su, Francis Edward; Thomas, Robin; Wollan, Paul Voting in agreeable societies. Amer. Math. Monthly 117 (2010), no. 1, 27--39. arXiv:0811.3245
  26. Norine, Serguei; Thomas, Robin Minimally non-Pfaffian graphs. J. Combin. Theory Ser. B 98 (2008), no. 5, 1038--1055.
  27. Thomas, Robin; Wollan, Paul The extremal function for 3-linked graphs. J. Combin. Theory Ser. B 98 (2008), no. 5, 939--971.
  28. Kral, Daniel; Thomas, Robin Coloring even-faced graphs in the torus and the Klein bottle. Combinatorica 28 (2008), no. 3, 325--341.
  29. Norine, Serguei; Thomas, Robin Pfaffian labelings and signs of edge colorings. Combinatorica 28 (2008), no. 1, 99--111.
  30. Norine, Serguei; Thomas, Robin Generating bricks. J. Combin. Theory Ser. B 97 (2007), no. 5, 769--817.
  31. Ghebleh, Mohammad; Král, Daniel; Norine, Serguei; Thomas, Robin The circular chromatic index of flower snarks. Electron. J. Combin. 13 (2006), no. 1, Note 20, 7 pp. (electronic). The Journal of Graph Theory refused to publish this article. Read more...
  32. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin The strong perfect graph theorem. Ann. of Math. (2) 164 (2006), no. 1, 51--229.
  33. Norine, Serguei; Seymour, Paul; Thomas, Robin; Wollan, Paul Proper minor-closed families are small. J. Combin. Theory Ser. B 96 (2006), no. 5, 754--757.
  34. Norine, Serguei; Thomas, Robin Minimal bricks. J. Combin. Theory Ser. B 96 (2006), no. 4, 505--513.
  35. Heckman, Christopher Carl; Thomas, Robin Independent sets in triangle-free cubic planar graphs. J. Combin. Theory Ser. B 96 (2006), 253--275.
  36. Song, Zi-Xia; Thomas, Robin The extremal function for K_9 minors. J. Combin. Theory Ser. B 96 (2006), 240--252.
  37. Brinkmann, Gunnar; Greenberg, Sam; Greenhill, Catherine; McKay, Brendan D.; Thomas, Robin; Wollan, Paul Generation of simple quadrangulations of the sphere. Discrete Math. 305 (2005), 33--54.
  38. Thomas, Robin; Yu, Xingxing; Zang, Wenan Hamilton paths in toroidal graphs. J. Combin. Theory Ser. B 94 (2005), no. 2, 214--236.
  39. Thomas, Robin; Wollan, Paul An improved linear edge bound for graph linkages. European J. Combin. 26 (2005), no. 3-4, 309--324.
  40. Thomas, Robin; Walls, Barrett Three-coloring Klein bottle graphs of girth five. J. Combin. Theory Ser. B 92 (2004), no. 1, 115--135.
  41. Hlineny, Petr; Thomas, Robin On possible counterexamples to Negami's planar cover conjecture. J. Graph Theory 46 (2004), no. 3, 183--206.
  42. Kauffman, Louis; Thomas, Robin Temperley-Lieb algebras and the four-color theorem. Combinatorica 23 (2003), no. 4, 653--667.
  43. Chudnovsky, Maria; Robertson, Neil; Seymour, P. D.; Thomas, Robin Progress on perfect graphs. Math. Program. 97 (2003), no. 1-2, Ser. B, 405--422.
  44. Johnson, Thor; Thomas, Robin Generating internally four-connected graphs. J. Combin. Theory Ser. B 85 (2002), no. 1, 21--58.
  45. Alon, Noga; Mubayi, Dhruv; Thomas, Robin Large induced forests in sparse graphs. J. Graph Theory 38 (2001), no. 3, 113--123.
  46. Johnson, Thor; Robertson, Neil; Seymour, P. D.; Thomas, Robin Directed tree-width. J. Combin. Theory Ser. B 82 (2001), no. 1, 138--154. An addendum.
  47. Heckman, Christopher Carl; Thomas, Robin A new proof of the independence ratio of triangle-free cubic graphs. Discrete Math. 233 (2001), no. 1-3, 233--237.
  48. Thomas, Robin; Thomson, Jan McDonald Excluding minors in nonplanar graphs of girth at least five. Combin. Probab. Comput. 9 (2000), no. 6, 573--585.
  49. Reed, Bruce; Thomas, Robin Clique minors in graphs and their complements. J. Combin. Theory Ser. B 78 (2000), no. 1, 81--85.
  50. Robertson, Neil; Seymour, P. D.; Thomas, Robin Permanents, Pfaffian orientations, and even directed circuits. Ann. of Math. (2) 150 (1999), no. 3, 929--975. Extended abstract
  51. Juvan, Martin; Mohar, Bojan; Thomas, Robin List edge-colorings of series-parallel graphs. Electron. J. Combin. 6 (1999), no. 1, Research Paper 42, 6 pp.
  52. Thomas, Robin Recent excluded minor theorems for graphs. Surveys in combinatorics, 1999 (Canterbury), 201--222, London Math. Soc. Lecture Note Ser., 267, Cambridge Univ. Press, Cambridge, 1999.
  53. Diestel, Reinhard; Thomas, Robin Excluding a countable clique. J. Combin. Theory Ser. B 76 (1999), no. 1, 41--67.
  54. Thomas, Robin An update on the four-color theorem. Notices Amer. Math. Soc. 45 (1998), no. 7, 848--859.
  55. Robertson, Neil; Seymour, Paul; Thomas, Robin Tutte's edge-colouring conjecture. J. Combin. Theory Ser. B 70 (1997), no. 1, 166--183.
  56. Robertson, Neil; Sanders, Daniel; Seymour, Paul; Thomas, Robin The four-colour theorem. J. Combin. Theory Ser. B 70 (1997), no. 1, 2--44. Survey paper. Web survey. The computer files can be downloaded from here or from arXiv:1401.6481 and arXiv:1401.6485.
  57. Thomas, Robin; Yu, Xingxing Five-connected toroidal graphs are Hamiltonian. J. Combin. Theory Ser. B 69 (1997), no. 1, 79--96.
  58. Rodl, Vojtech; Thomas, Robin Arrangeability and clique subdivisions. The mathematics of Paul Erdos, II, 236--239, Algorithms Combin., 14, Springer, Berlin, 1997.
  59. Reed, Bruce; Robertson, Neil; Seymour, Paul; Thomas, Robin Packing directed circuits. Combinatorica 16 (1996), no. 4, 535--554.
  60. Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin Efficiently four-coloring planar graphs. Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), 571--575, ACM, New York, 1996.
  61. Seymour, P. D.; Thomas, Robin Uniqueness of highly representative surface embeddings. J. Graph Theory 23 (1996), no. 4, 337--349.
  62. Dean, Nathaniel; Thomas, Robin; Yu, Xingxing Spanning paths in infinite planar graphs. J. Graph Theory 23 (1996), no. 2, 163--174.
  63. Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin A new proof of the four-colour theorem. Electron. Res. Announc. Amer. Math. Soc. 2 (1996), no. 1, 17--25.
  64. Rodl, Vojtech; Thomas, Robin On the genus of a random graph. Random Structures Algorithms 6 (1995), no. 1, 1--12.
  65. Robertson, Neil; Seymour, Paul; Thomas, Robin Sachs' linkless embedding conjecture. J. Combin. Theory Ser. B 64 (1995), no. 2, 185--227.
  66. Robertson, Neil; Seymour, Paul; Thomas, Robin Petersen family minors. J. Combin. Theory Ser. B 64 (1995), no. 2, 155--184.
  67. Robertson, Neil; Seymour, Paul; Thomas, Robin Kuratowski chains. J. Combin. Theory Ser. B 64 (1995), no. 2, 127--154.
  68. Robertson, Neil; Seymour, Paul; Thomas, Robin Excluding infinite clique minors. Mem. Amer. Math. Soc. 118 (1995), no. 566, vi+103 pp.
  69. Robertson, Neil; Seymour, Paul; Thomas, Robin Quickly excluding a planar graph. J. Combin. Theory Ser. B 62 (1994), no. 2, 323--348.
  70. Thomas, Robin; Yu, Xingxing 4-connected projective-planar graphs are Hamiltonian. J. Combin. Theory Ser. B 62 (1994), no. 1, 114--132.
  71. Seymour, P. D.; Thomas, R. Call routing and the ratcatcher. Combinatorica 14 (1994), no. 2, 217--241.
  72. Alon, Noga; Seymour, Paul; Thomas, Robin Planar separators. SIAM J. Discrete Math. 7 (1994), no. 2, 184--193.
  73. Robertson, Neil; Seymour, Paul; Thomas, Robin Hadwiger's conjecture for K_6-free graphs. Combinatorica 13 (1993), no. 3, 279--361.
  74. Robertson, Neil; Seymour, P. D.; Thomas, Robin Structural descriptions of lower ideals of trees. Graph structure theory (Seattle, WA, 1991), 525--538, Contemp. Math., 147, Amer. Math. Soc., Providence, RI, 1993.
  75. Robertson, Neil; Seymour, P. D.; Thomas, Robin A survey of linkless embeddings. Graph structure theory (Seattle, WA, 1991), 125--136, Contemp. Math., 147, Amer. Math. Soc., Providence, RI, 1993.
  76. Seymour, P. D.; Thomas, Robin Graph searching and a min-max theorem for tree-width. J. Combin. Theory Ser. B 58 (1993), no. 1, 22--33.
  77. Oporowski, Bogdan; Oxley, James; Thomas, Robin Typical subgraphs of 3- and 4-connected graphs. J. Combin. Theory Ser. B 57 (1993), no. 2, 239--257.
  78. Robertson, Neil; Seymour, P. D.; Thomas, Robin Linkless embeddings of graphs in 3-space. Bull. Amer. Math. Soc. (N.S.) 28 (1993), no. 1, 84--89.
  79. Seymour, P. D.; Thomas, Robin Excluding infinite trees. Trans. Amer. Math. Soc. 335 (1993), no. 2, 597--630.
  80. Lefmann, Hanno; Rodl, Vojtech; Thomas, Robin Monochromatic vs multicolored paths. Graphs Combin. 8 (1992), no. 4, 323--332.
  81. Matousek, Jiri; Thomas, Robin On the complexity of finding iso- and other morphisms for partial k-trees. Topological, algebraical and combinatorial structures. Froli­k's memorial volume. Discrete Math. 108 (1992), no. 1-3, 343--364.
  82. Robertson, Neil; Seymour, P. D.; Thomas, Robin Excluding subdivisions of infinite cliques. Trans. Amer. Math. Soc. 332 (1992), no. 1, 211--223.
  83. Robertson, Neil; Seymour, Paul; Thomas, Robin Excluding infinite minors. Directions in infinite graph theory and combinatorics (Cambridge, 1989). Discrete Math. 95 (1991), no. 1-3, 303--319.
  84. Kriz, Igor; Thomas, Robin Analyzing Nash-Williams' partition theorem by means of ordinal types. Directions in infinite graph theory and combinatorics (Cambridge, 1989). Discrete Math. 95 (1991), no. 1-3, 135--167.
  85. Robertson, Neil; Thomas, Robin On the orientable genus of graphs embedded in the Klein bottle. J. Graph Theory 15 (1991), no. 4, 407--419.
  86. Bienstock, Dan; Robertson, Neil; Seymour, Paul; Thomas, Robin Quickly excluding a forest. J. Combin. Theory Ser. B 52 (1991), no. 2, 274--283.
  87. Kriz, Igor; Thomas, Robin The Menger-like property of the tree-width of infinite graphs. J. Combin. Theory Ser. B 52 (1991), no. 1, 86--91.
  88. Matousek, Jiri; Thomas, Robin Algorithms finding tree-decompositions of graphs. J. Algorithms 12 (1991), no. 1, 1--22.
  89. Seymour, Paul; Thomas, Robin An end-faithful spanning tree counterexample. Proc. Amer. Math. Soc. 113 (1991), no. 4, 1163--1171. Reprinted in Discr. Math. 95 (1991), 321--330.
  90. Kriz, Igor; Thomas, Robin Ordinal types in Ramsey theory and well-partial-ordering theory. Mathematics of Ramsey theory, 57--95, Algorithms Combin., 5, Springer, Berlin, 1990.
  91. Alon, Noga; Seymour, Paul; Thomas, Robin A separator theorem for nonplanar graphs. J. Amer. Math. Soc. 3 (1990), no. 4, 801--808.
  92. Kriz, Igor; Thomas, Robin On well-quasi-ordering finite structures with labels. Graphs Combin. 6 (1990), no. 1, 41--49.
  93. Kriz, Igor; Thomas, Robin Clique-sums, tree-decompositions and compactness. Discrete Math. 81 (1990), no. 2, 177--185.
  94. Thomas, Robin A Menger-like property of tree-width: the finite case. J. Combin. Theory Ser. B 48 (1990), no. 1, 67--76.
  95. Thomas, Robin Well-quasi-ordering infinite graphs with forbidden finite planar minor. Trans. Amer. Math. Soc. 312 (1989), no. 1, 279--313.
  96. Matousek, J.; Nesetril, J.; Thomas, R. On polynomial time decidability of induced-minor-closed classes. Comment. Math. Univ. Carolin. 29 (1988), no. 4, 703--710.
  97. Thomas, Robin A counterexample to "Wagner's conjecture" for infinite graphs. Math. Proc. Cambridge Philos. Soc. 103 (1988), no. 1, 55--57.
  98. Nesetril, Jaroslav; Thomas, Robin Well quasi-orderings, long games and a combinatorial study of undecidability. Logic and combinatorics (Arcata, Calif., 1985), 281--293, Contemp. Math., 65, Amer. Math. Soc., Providence, RI, 1987.
  99. Thomas, Robin Optimal stopping and impulsive control of one-dimensional diffusion processes. Czechoslovak Math. J. 37(112) (1987), no. 2, 271--292.
  100. Nesetril, Jaroslav; Thomas, Robin A note on spatial representation of graphs. Comment. Math. Univ. Carolin. 26 (1985), no. 4, 655--659.
  101. Thomas, Robin Graphs without K_4 and well-quasi-ordering. J. Combin. Theory Ser. B 38 (1985), no. 3, 240--247.
  102. Thomas, Robin A combinatorial construction of a nonmeasurable set. Amer. Math. Monthly 92 (1985), no. 6, 421--422.
  103. Thomas, Robin Series-parallel graphs and well- and better-quasi-orderings. Comment. Math. Univ. Carolin. 25 (1984), no. 4, 719--723.

CONFERENCE PAPERS

  1. Dvorak, Zdenek; Kral, Daniel; Thomas, Robin Coloring triangle-free graphs on surfaces. Extended abtract Proceedings of SODA 09.
  2. Dvorak, Zdenek; Kawarabayashi, Ken-ichi; Thomas, Robin Three-coloring triangle-free planar graphs in linear time, Proceedings of SODA 09.
  3. Chenette, Nathan; Postle, Luke; Streib, Noah; Thomas, Robin; Yerger, Carl; Kawarabayashi, Ken-ichi; Kral, Daniel; Kyncl, Jan; Lidicky, Bernard Six-critical graphs on the Klein bottle. The International Conference on Topological and Geometric Graph Theory, 235--240, Electron. Notes Discrete Math., 31, Elsevier Sci. B. V., Amsterdam, 2008.
  4. Thomas, Robin A survey of Pfaffian orientations of graphs. International Congress of Mathematicians. Vol. III, 963--984, Eur. Math. Soc., Zurich, 2006.
  5. Chudnovsky, Maria; Robertson, Neil; Seymour, P. D.; Thomas, Robin Progress on perfect graphs. Math. Program. 97 (2003), no. 1-2, Ser. B, 405--422.

UNPUBLISHED PAPERS

  1. Thomas, Robin The tree-width compactness theorem for hypergraphs
  2. Fernandes, Cristina; Thomas, Robin Edge-coloring series-parallel multigraphs, arXiv:1107.5370.
  3. Thomas, Robin Planarity in linear time. Class notes
  4. Robertson, Neil; Seymour, Paul; Thomas, Robin Reducibility in the four-color theorem, arXiv:1401.6481
  5. Robertson, Neil; Seymour, Paul; Thomas, Robin Discharging cartwheels, arXiv:1401.6485
  6. Johnson, Thor; Robertson, Neil; Seymour, P. D.; Thomas, Robin Excluding A Grid Minor In Planar Digraphs, arXiv:1510.00473.