School of Mathematics

Georgia Institute of Technology

Atlanta, Georgia 30332

thomas(at)math.gatech.edu

FAX: 404-894-4409

Graph theory (including infinite graphs), Combinatorics, Combinatorial Optimization, Algorithms

The Four Color Theorem and its generalizations, Hamiltonian graphs on surfaces, embeddings of graphs, topological and structural graph theory, disjoint paths in graphs, matchings and Pfaffian orientations, efficient algorithms, perfect graphs. Research sponsored by the National Science Foundation.

- Girth six cubic graphs have Petersen minors (with N.Robertson and P.D.Seymour).
- K_6 minors in 6-connected graphs of bounded tree-width (with K. Kawarabayashi, S. Norin and P. Wollan), arXiv:1203.2171
- K_6 minors in large 6-connected graphs (with K. Kawarabayashi, S. Norin and P. Wollan), arXiv:1203.2192
- Coloring planar graphs with triangles far apart (with Z. Dvorak and D. Kral), arXiv:0911.0885.
- Sub-exponentially many 3-colorings of triangle-free planar graphs (with A. Asadi, Z. Dvorak and L. Postle), J. Combin. Theory Ser. B (2013), http://dx.doi.org/10.1016/j.jctb.2013.09.001, arXiv:1007.1430.
- Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle (with Z. Dvorak and D. Kral), arXiv:1010.2472.
- Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk (with Z. Dvorak and D. Kral), arXiv:1302.2158.
- Testing first-order properties for subclasses of sparse graphs (with Z. Dvorak and D. Kral), to appear in J. Assoc. Comp. Machinery, arXiv:1109.5036. Here is a FOCS 2010 version.
- A New Proof of the Flat Wall Theorem (with K. Kawarabayashi and P. Wollan), arXiv:1207.6927.
- Deploying robots with two sensors in K_{1,6}-free graphs (with W. Abbas, M. Egerstedt, C.-H. Liu and P. Whalen), arXiv:1308.5450.
- Odd K_3,3 subdivisions in bipartite graphs (with P. Whalen), arXiv:1309.5336.
- Non-planar extensions of planar graphs (with S. Norin), arXiv:1402.1999.
- Non-embeddable extensions of embedded minors (with R. Hegde), arXiv:1401.2973.
- Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs (with L. Postle), arXiv:1402.1813.
- List-coloing apex-minor-free graphs (with Z. Dvorak), arXiv:1401.1399.
- Three-coloring triangle-free graphs on surfaces III. Graphs of girth five (with Z. Dvorak and D. Kral), arXiv:1402.4710.
- Excluded minors in cubic graphs (with N.Robertson and P.D.Seymour), arXiv:1403.2118.

- Editor, Journal of Combinatorial Theory Series B
- Editor, Journal of Graph Theory
- Editor, Graphs and Combinatorics

- MATH 7014 Advanced Graph Theory

- Daniel P. Sanders, Ph.D. 1993. Member of Technical Staff, Renaissance Technologies
- Tom Fowler, Ph.D. 1998. Assistant Professor, Palm Beach Atlantic University.
- Petr Hlineny, Ph.D. 1999. Associate Professor, Masaryk University, Brno, Czech Republic.
- Barrett Walls, Ph.D. 1999. Associate Professor, Georgia Perimeter College
- Christopher Carl Heckman, Ph.D. 2000. Lecturer, Arizona State University
- Jan Thomson, Ph.D. 2000. Instructor, University of Utah.
- Zixia Song, Ph.D. 2004. Associate Professor, University of Central Florida.
- Paul Wollan, Ph.D. 2005. Assistant Professor, University of Rome "La Sapienza".
- Sergey Norin, Ph.D. 2005. Assistant Professor, McGill University.
- Rajneesh Hegde, Ph.D. 2006. Software Design Engineer, Microsoft Corporation.
- Torsten Inkmann, Ph.D. 2008. Member of Technical Staff, INFORM.
- Carl Yerger, Ph.D. 2010. Assistant Professor, Davidson College.
- Luke Postle, Ph.D. 2012. Emory Fellow, Emory University.
- Arash Asadi, Ph.D. 2012. Member of Technical Staff, Walmart Labs.
- Peter Whalen, Ph.D. in progress.
- Chun-Hung Liu, Ph.D. in progress.

- My family: Sigrun, Misha, Klara, and Martin.
- The ACO program. Ph.D. program in Algorithms, Combinatorics and Optimization.
- Information for ACO students.
- American Mathematical Society Ethical Guidelines
- Code of Practice of the European Mathematical Society.
- Transparencies for some of my talks
- An article about my work in Research Horizons, a Georgia Tech publication.
- An article about my work in the Science Magazine.
- Chvatal's Perfect Problems
- Computer data pertaining to the proof of the Four Color Theorem.
- Tree-decompositions of graphs, lecture notes for the Catlin Memorial Workshop.
- Planarity in linear time, an exposition of a planarity algorithm of Shih and Hsu.
- Talks from the 2010 SIAM Meeting on Discrete Mathematics
- American Institute of Mathematics
- Georgia Tech Catalog
- Georgia Tech campus map