Two-three linked graphs

Series
Graph Theory Seminar
Time
Thursday, September 7, 2017 - 1:30pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Shijie Xie – School of Mathematics, Georgia Tech
Organizer
Xingxing Yu
Let G be a graph containing 5 different vertices a0,a1,a2,b1 and b2. We say that (G,a0,a1,a2,b1,b2) is feasible if G contains disjoint connected subgraphs G1,G2, such that {a0,a1,a2}V(G1) and {b1,b2}V(G2). We give a characterization for (G,a0,a1,a2,b1,b2) to be feasible, answering a question of Robertson and Seymour. This is joint work with Changong Li, Robin Thomas, and Xingxing Yu.In this talk, we will discuss the operations we will use to reduce (G,a0,a1,a2,b1,b2) to (G,a0,a1,a2,b1,b2) with |V(G)|+|E(G)|>|V(G)|+E(G), such that (G,a0,a1,a2,b1,b2) is feasible iff (G,a0,a1,a2b1,b2) is feasible.