- 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′,a′0,a′1,a′2,b′1,b′2) with |V(G)|+|E(G)|>|V(G′)|+E(G′), such that (G,a0,a1,a2,b1,b2) is feasible iff (G′,a′0,a′1,a′2b′1,b′2) is feasible.