Publications (60)
Three-coloring triangle-free graphs on surfaces III. Graphs of girth five
ZdenÄk DvoÅák, Daniel Kráľ, Robin Thomas
We show that the size of a 4-critical graph of girth at least five is bounded by a linear function of its genus. This strengthens the previous bound on the size of such graphs give…
Non-Embeddable Extensions of Embedded Minors
Rajneesh Hegde, Robin Thomas
A graph G is weakly 4-connected if it is 3-connected, has at least five vertices, and for every pair of sets (A,B) with union V(G) and intersection of size three such that no edge…
Voting in agreeable societies
Deborah E. Berg, Serguei Norine, Francis Edward Su +2
When can a majority of voters find common ground, that is, a position they all agree upon? How does the shape of the political spectrum influence the outcome? When mathematical obj…
Edge-coloring series-parallel multigraphs
Cristina G. Fernandes, Robin Thomas
We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can…
Five-list-coloring graphs on surfaces III. One list of size one and one list of size two
Luke Postle, Robin Thomas
Let be a plane graph with outer cycle and let be a family of non-empty sets. By an -coloring of we mean a (proper) coloring of such that…
Excluding A Grid Minor In Planar Digraphs
Thor Johnson, Neil Robertson, Paul Seymour +1
In [Directed tree-width, J. Combin. Theory Ser. B 82 (2001), 138-154] we introduced the notion of tree-width of directed graphs and presented a conjecture, formulated during discus…