ROBIN THOMAS' PUBLISHED JOURNAL PAPERS

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

    CONFERENCE PAPERS

  88. Dvorak, Zdenek; Kral, Daniel; Thomas, Robin Coloring triangle-free graphs on surfaces. Extended abtract Proceedings of SODA 09.
  89. Dvorak, Zdenek; Kawarabayashi, Ken-ichi; Thomas, Robin Three-coloring triangle-free planar graphs in linear time, Proceedings of SODA 09.
  90. 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.
  91. Thomas, Robin A survey of Pfaffian orientations of graphs. International Congress of Mathematicians. Vol. III, 963--984, Eur. Math. Soc., Zurich, 2006.
  92. 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

  93. Thomas, Robin The tree-width compactness theorem for hypergraphs
  94. Fernandes, Cristina; Thomas, Robin Edge-coloring series-parallel multigraphs
  95. Thomas, Robin Planarity in linear time. Class notes
  96. Robertson, Neil; Seymour, Paul; Thomas, Robin Reducibility in the four-color theorem, arXiv:1401.6481
  97. Robertson, Neil; Seymour, Paul; Thomas, Robin Discharging cartwheels, arXiv:1401.6485