Seminars and Colloquia by Series

The Grid Theorem for Vertex Minors

Series
Graph Theory Seminar
Time
Thursday, August 30, 2018 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCartyUniversity of Waterloo
Vertex minors are a weakening of the notion of induced subgraphs that benefit from many additional nice properties. In particular, there is a vertex minor version of Menger's Theorem proven by Oum. This theorem gives rise to a natural analog of branch-width called rank-width. Similarly to the Grid Theorem of Robertson and Seymour, we prove that a class of graphs has unbounded rank-width if and only if it contains all "comparability grids'' as vertex minors. This is joint work with Jim Geelen, O-joung Kwon, and Paul Wollan.

The Generalized Györi-Lovasz Theorem

Series
Graph Theory Seminar
Time
Thursday, April 19, 2018 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Alexander HoyerMath, GT
Györi and Lovasz independently proved that a k-connected graph can be partitioned into k subgraphs, with each subgraph connected, containing a prescribed vertex, and with a prescribed vertex count. Lovasz used topological methods, while Györi found a purely graph theoretical approach. Chen et al. later generalized the topological proof to graphs with weighted vertices, where the subgraphs have prescribed weight sum rather than vertex count. The weighted result was recently proven using Györi's approach by Chandran et al. We will use the Györi approach to generalize the weighted result slightly further. Joint work with Robin Thomas.

The extremal functions for triangle-free graphs with excluded minors

Series
Graph Theory Seminar
Time
Thursday, April 12, 2018 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho YooMath, GT
A classic theorem of Mader gives the extremal functions for graphs that do not contain the complete graph on p vertices as a minor for p up to 7. Motivated by the study of linklessly embeddable graphs, we present some results on the extremal functions of apex graphs with respect to the number of triangles, and on triangle-free graphs with excluded minors. Joint work with Robin Thomas.

Four edge-independent spanning trees

Series
Graph Theory Seminar
Time
Thursday, March 8, 2018 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Alexander HoyerMath, GT
For a graph G, a set of subtrees of G are edge-independent with root r ∈ V(G) if, for every vertex v ∈ V(G), the paths between v and r in each tree are edge-disjoint. A set of k such trees represent a set of redundant broadcasts from r which can withstand k-1 edge failures. It is easy to see that k-edge-connectivity is a necessary condition for the existence of a set of k edge-independent spanning trees for all possible roots. Itai and Rodeh have conjectured that this condition is also sufficient. This had previously been proven for k=2, 3. We prove the case k=4 using a decomposition of the graph similar to an ear decomposition. Joint work with Robin Thomas.

Induced subgraphs in graphs without linear and polynomial-size anticomplete sets

Series
Graph Theory Seminar
Time
Thursday, February 8, 2018 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sophie SpirklPrinceton University
The celebrated Erdos-Hajnal conjecture states that for every graph H, there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of size at least n^c, where n = |V(G)|. One approach for proving this conjecture is to prove that in every H-free graph G, there are two linear-size sets A and B such that either there are no edges between A and B, or every vertex in A is adjacent to every vertex in B. As is turns out, this is not true unless both H and its complement are trees. In the case when G contains neither H nor its complement as an induced subgraph, the conclusion above was conjectured to be true for all trees (Liebenau & Pilipczuk), and I will discuss a proof of this for a class of tree called "caterpillars". I will also talk about results and open questions for some variants, including allowing one or both of A and B to have size n^c instead of linear size, and requiring the bipartite graph between A and B to have high or low density instead of being complete or empty. In particular, our results improve the bound on the size of the largest clique or stable that must be present in a graph with no induced five-cycle. Joint work with Maria Chudnovsky, Jacob Fox, Anita Liebenau, Marcin Pilipczuk, Alex Scott, and Paul Seymour.

Two-three linked graphs

Series
Graph Theory Seminar
Time
Thursday, November 30, 2017 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Shijie XieMath, Gt
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). In this talk, we will complete a sketch of our arguments for characterizing when (G, a0, a1, a2, b1, b2) is feasible. Joint work with Changong Li, Robin Thomas, and Xingxing Yu.

Two-three linked graphs

Series
Graph Theory Seminar
Time
Thursday, November 9, 2017 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Shijie XieMath, GT
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). In this talk, we will prove the existence of 5-edge configurations in (G, a0, a1, a2, b1, b2). Joint work with Changong Li, Robin Thomas, and Xingxing Yu.

Two-three linked graphs

Series
Graph Theory Seminar
Time
Thursday, November 2, 2017 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Shijie XieMath, GT
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). In this talk, we will introduce ideal frames, slim connectors and fat connectors. We will first deal with the ideal frames without fat connectors, by studying 3-edge and 5-edge configurations. Joint work with Changong Li, Robin Thomas, and Xingxing Yu.

Two-three linked graphs

Series
Graph Theory Seminar
Time
Thursday, October 5, 2017 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Shijie XieMath, GT
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). In this talk, we will describe the structure of G when (G, a0, a1, a2, b1, b2) is infeasible, using frames and connectors. Joint work with Changong Li, Robin Thomas, and Xingxing Yu.

Pages