ROBIN THOMAS' PUBLISHED JOURNAL PAPERS

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Thomas, Robin; Whalen, Peter Odd K3,3 subdivisions in bipartite graphs. J. Combin. Theory Ser. B 118 (2016), 76-87.  arXiv:1309.5336
  6. 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.
  7. 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.
  8. Asadi, Arash; Dvořak, ZdeněkPostle, 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.
  9. 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.
  10. 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.
  11. Guenin, Bertrand; Thomas, Robin Packing directed circuits exactly. Combinatorica 31 (2011), no. 4, 397--421.  arXiv:1012.2749.
  12. 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.
  13. Shapira, Asaf; Thomas, Robin Color-critical graphs have logarithmic circumference. Adv. Math. 227 (2011), no. 6, 2309--2326. arXiv:0908.3169
  14. 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
  15. Inkmann, Torsten; Thomas, Robin Minor-minimal planar graphs of even branch-width. Combin. Probab. Comput. 20 (2011), no. 1, 73--82.  arXiv:1007.0373
  16. 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.
  17. 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
  18. Norine, Serguei; Thomas, Robin Minimally non-Pfaffian graphs. J. Combin. Theory Ser. B 98 (2008), no. 5, 1038--1055.
  19. Thomas, Robin; Wollan, Paul The extremal function for 3-linked graphs. J. Combin. Theory Ser. B 98 (2008), no. 5, 939--971.
  20. Kral, Daniel; Thomas, Robin Coloring even-faced graphs in the torus and the Klein bottle. Combinatorica 28 (2008), no. 3, 325--341.
  21. Norine, Serguei; Thomas, Robin Pfaffian labelings and signs of edge colorings. Combinatorica 28 (2008), no. 1, 99--111.
  22. Norine, Serguei; Thomas, Robin Generating bricks. J. Combin. Theory Ser. B 97 (2007), no. 5, 769--817.
  23. 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...
  24. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin The strong perfect graph theorem. Ann. of Math. (2) 164 (2006), no. 1, 51--229.
  25. 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.
  26. Norine, Serguei; Thomas, Robin Minimal bricks. J. Combin. Theory Ser. B 96 (2006), no. 4, 505--513.
  27. Heckman, Christopher Carl; Thomas, Robin Independent sets in triangle-free cubic planar graphs. J. Combin. Theory Ser. B 96 (2006), 253--275.
  28. Song, Zi-Xia; Thomas, Robin The extremal function for K_9 minors. J. Combin. Theory Ser. B 96 (2006), 240--252.
  29. 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.
  30. Thomas, Robin; Yu, Xingxing; Zang, Wenan Hamilton paths in toroidal graphs. J. Combin. Theory Ser. B 94 (2005), no. 2, 214--236.
  31. Thomas, Robin; Wollan, Paul An improved linear edge bound for graph linkages. European J. Combin. 26 (2005), no. 3-4, 309--324.
  32. Thomas, Robin; Walls, Barrett Three-coloring Klein bottle graphs of girth five. J. Combin. Theory Ser. B 92 (2004), no. 1, 115--135.
  33. Hlineny, Petr; Thomas, Robin On possible counterexamples to Negami's planar cover conjecture. J. Graph Theory 46 (2004), no. 3, 183--206.
  34. Kauffman, Louis; Thomas, Robin Temperley-Lieb algebras and the four-color theorem. Combinatorica 23 (2003), no. 4, 653--667.
  35. Chudnovsky, Maria; Robertson, Neil; Seymour, P. D.; Thomas, Robin Progress on perfect graphs. Math. Program. 97 (2003), no. 1-2, Ser. B, 405--422.
  36. Johnson, Thor; Thomas, Robin Generating internally four-connected graphs. J. Combin. Theory Ser. B 85 (2002), no. 1, 21--58.
  37. Alon, Noga; Mubayi, Dhruv; Thomas, Robin Large induced forests in sparse graphs. J. Graph Theory 38 (2001), no. 3, 113--123.
  38. 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.
  39. 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.
  40. Thomas, Robin; Thomson, Jan McDonald Excluding minors in nonplanar graphs of girth at least five. Combin. Probab. Comput. 9 (2000), no. 6, 573--585.
  41. Reed, Bruce; Thomas, Robin Clique minors in graphs and their complements. J. Combin. Theory Ser. B 78 (2000), no. 1, 81--85.
  42. 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
  43. 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.
  44. 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.
  45. Diestel, Reinhard; Thomas, Robin Excluding a countable clique. J. Combin. Theory Ser. B 76 (1999), no. 1, 41--67.
  46. Thomas, Robin An update on the four-color theorem. Notices Amer. Math. Soc. 45 (1998), no. 7, 848--859.
  47. Robertson, Neil; Seymour, Paul; Thomas, Robin Tutte's edge-colouring conjecture. J. Combin. Theory Ser. B 70 (1997), no. 1, 166--183.
  48. 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.
  49. Thomas, Robin; Yu, Xingxing Five-connected toroidal graphs are Hamiltonian. J. Combin. Theory Ser. B 69 (1997), no. 1, 79--96.
  50. Rodl, Vojtech; Thomas, Robin Arrangeability and clique subdivisions. The mathematics of Paul Erdos, II, 236--239, Algorithms Combin., 14, Springer, Berlin, 1997.
  51. Reed, Bruce; Robertson, Neil; Seymour, Paul; Thomas, Robin Packing directed circuits. Combinatorica 16 (1996), no. 4, 535--554.
  52. 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.
  53. Seymour, P. D.; Thomas, Robin Uniqueness of highly representative surface embeddings. J. Graph Theory 23 (1996), no. 4, 337--349.
  54. Dean, Nathaniel; Thomas, Robin; Yu, Xingxing Spanning paths in infinite planar graphs. J. Graph Theory 23 (1996), no. 2, 163--174.
  55. 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.
  56. Rodl, Vojtech; Thomas, Robin On the genus of a random graph. Random Structures Algorithms 6 (1995), no. 1, 1--12.
  57. Robertson, Neil; Seymour, Paul; Thomas, Robin Sachs' linkless embedding conjecture. J. Combin. Theory Ser. B 64 (1995), no. 2, 185--227.
  58. Robertson, Neil; Seymour, Paul; Thomas, Robin Petersen family minors. J. Combin. Theory Ser. B 64 (1995), no. 2, 155--184.
  59. Robertson, Neil; Seymour, Paul; Thomas, Robin Kuratowski chains. J. Combin. Theory Ser. B 64 (1995), no. 2, 127--154.
  60. Robertson, Neil; Seymour, Paul; Thomas, Robin Excluding infinite clique minors. Mem. Amer. Math. Soc. 118 (1995), no. 566, vi+103 pp.
  61. Robertson, Neil; Seymour, Paul; Thomas, Robin Quickly excluding a planar graph. J. Combin. Theory Ser. B 62 (1994), no. 2, 323--348.
  62. Thomas, Robin; Yu, Xingxing 4-connected projective-planar graphs are Hamiltonian. J. Combin. Theory Ser. B 62 (1994), no. 1, 114--132.
  63. Seymour, P. D.; Thomas, R. Call routing and the ratcatcher. Combinatorica 14 (1994), no. 2, 217--241.
  64. Alon, Noga; Seymour, Paul; Thomas, Robin Planar separators. SIAM J. Discrete Math. 7 (1994), no. 2, 184--193.
  65. Robertson, Neil; Seymour, Paul; Thomas, Robin Hadwiger's conjecture for K_6-free graphs. Combinatorica 13 (1993), no. 3, 279--361.
  66. 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.
  67. 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.
  68. 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.
  69. 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.
  70. 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.
  71. Seymour, P. D.; Thomas, Robin Excluding infinite trees. Trans. Amer. Math. Soc. 335 (1993), no. 2, 597--630.
  72. Lefmann, Hanno; Rodl, Vojtech; Thomas, Robin Monochromatic vs multicolored paths. Graphs Combin. 8 (1992), no. 4, 323--332.
  73. 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.
  74. Robertson, Neil; Seymour, P. D.; Thomas, Robin Excluding subdivisions of infinite cliques. Trans. Amer. Math. Soc. 332 (1992), no. 1, 211--223.
  75. 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.
  76. 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.
  77. Robertson, Neil; Thomas, Robin On the orientable genus of graphs embedded in the Klein bottle. J. Graph Theory 15 (1991), no. 4, 407--419.
  78. Bienstock, Dan; Robertson, Neil; Seymour, Paul; Thomas, Robin Quickly excluding a forest. J. Combin. Theory Ser. B 52 (1991), no. 2, 274--283.
  79. 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.
  80. Matousek, Jiri; Thomas, Robin Algorithms finding tree-decompositions of graphs. J. Algorithms 12 (1991), no. 1, 1--22.
  81. 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.
  82. 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.
  83. Alon, Noga; Seymour, Paul; Thomas, Robin A separator theorem for nonplanar graphs. J. Amer. Math. Soc. 3 (1990), no. 4, 801--808.
  84. Kriz, Igor; Thomas, Robin On well-quasi-ordering finite structures with labels. Graphs Combin. 6 (1990), no. 1, 41--49.
  85. Kriz, Igor; Thomas, Robin Clique-sums, tree-decompositions and compactness. Discrete Math. 81 (1990), no. 2, 177--185.
  86. Thomas, Robin A Menger-like property of tree-width: the finite case. J. Combin. Theory Ser. B 48 (1990), no. 1, 67--76.
  87. Thomas, Robin Well-quasi-ordering infinite graphs with forbidden finite planar minor. Trans. Amer. Math. Soc. 312 (1989), no. 1, 279--313.
  88. 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.
  89. Thomas, Robin A counterexample to "Wagner's conjecture" for infinite graphs. Math. Proc. Cambridge Philos. Soc. 103 (1988), no. 1, 55--57.
  90. 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.
  91. Thomas, Robin Optimal stopping and impulsive control of one-dimensional diffusion processes. Czechoslovak Math. J. 37(112) (1987), no. 2, 271--292.
  92. Nesetril, Jaroslav; Thomas, Robin A note on spatial representation of graphs. Comment. Math. Univ. Carolin. 26 (1985), no. 4, 655--659.
  93. Thomas, Robin Graphs without K_4 and well-quasi-ordering. J. Combin. Theory Ser. B 38 (1985), no. 3, 240--247.
  94. Thomas, Robin A combinatorial construction of a nonmeasurable set. Amer. Math. Monthly 92 (1985), no. 6, 421--422.
  95. 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
  1. Johnson, Thor; Robertson, Neil; Seymour, P. D.; Thomas, Robin Excluding A Grid Minor In Planar Digraphs, arXiv:1510.00473.