Seminars and Colloquia by Series

Decomposition of Triangle-dense Graphs

Series
Graph Theory Seminar
Time
Wednesday, April 20, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
He GuoMath, GT
A special feature possessed by the graphs of social networks is triangle-dense. R. Gupta, T. Roughgarden and C. Seshadhri give a polynomial time graph algorithm to decompose a triangle-dense graph into some clusters preserving high edge density and high triangle density in each cluster with respect to the original graph and each cluster has radius 2. And high proportion of triangles of the original graph are preserved in these clusters. Furthermore, if high proportion of edges in the original graph is "locally triangle-dense", then additionally, high proportion of edges of the original graph are preserved in these clusters. In this talk, I will present most part of the paper "Decomposition of Triangle-dense Graphs" in SIAM J. COMPUT. Vol. 45, No. 2, pp. 197–215, 2016, by R. Gupta, T. Roughgarden and C. Seshadhri.

The Kelmans-Seymour conjecture V: no contractible edges or triangles (finding TK_5)

Series
Graph Theory Seminar
Time
Wednesday, April 13, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we study the structure of these 5-separations and 6-separations, and prove the Kelmans-Seymour conjecture.

The Kelmans-Seymour conjecture V: no contractible edges or triangles (first part)

Series
Graph Theory Seminar
Time
Wednesday, April 6, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we prove a lemma using the characterization of three paths with designated ends, which will be used in the proof of the Kelmans-Seymour conjecture.

The Kelmans-Seymour conjecture IV: 3-vertices in K_4^-

Series
Graph Theory Seminar
Time
Wednesday, March 30, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dawei HeMath, GT
Let G be a 5-connected graph and let x1, x2,y1,y2 in V(G) be distinct, such that G[{x1, x2, y1, y2}] is isomorphic to K_4^- and y1y2 is not in E(G). We show that G contains a K_4^- in which x1 is of degree 2, or G-x1 contains K_4^-, or G contains a TK_5 in which x1 is not a branch vertex, or {x2, y1, y2} may be chosen so that for any distinct w1,w2 in N(x1) - {x2, y1, y2}, G - {x1v : v is not in {w1, w2, x2, y1,y2} } contains TK_5.

On Reed's conjecture

Series
Graph Theory Seminar
Time
Wednesday, March 16, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Luke PostleDepartment of C&O, University of Waterloo
In 1998, Reed proved that the chromatic number of a graph is bounded away from its trivial upper bound, its maximum degree plus one, and towards its trivial lower bound, its clique number. Reed also conjectured that the chromatic number is at most halfway in between these two bounds. We prove that for large maximum degree, that the chromatic number is at least 1/25th in between. Joint work with Marthe Bonamy and Tom Perrett.

The Kelmans-Seymour conjecture III: 3-vertices in K_4^-

Series
Graph Theory Seminar
Time
Wednesday, March 9, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dawei HeMath, GT
Let G be a 5-connected graph and let x1, x2,y1,y2 in V(G) be distinct, such that G[{x1, x2, y1, y2}] is isomorphic to K_4^- and y1y2 is not in E(G). We show that G contains a K_4^- in which x1 is of degree 2, or G-x1 contains K_4^-, or G contains a TK_5 in which x1 is not a branch vertex, or {x2, y1, y2} may be chosen so that for any distinct w1,w2 in N(x1) - {x2, y1, y2}, G - {x1v : v is not in {w1, w2, x2, y1,y2} } contains TK_5.

The Kelmans-Seymour conjecture II: 2-vertices in K_4^- (Intermediate structure and finding TK_5)

Series
Graph Theory Seminar
Time
Wednesday, March 2, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
We use K_4^- to denote the graph obtained from K_4 by removing an edge,and use TK_5 to denote a subdivision of K_5. Let G be a 5-connected nonplanar graph and {x_1, x_2, y_1, y_2} \subseteq V (G) such that G[{x_1,x_2, y_1, y_2}] = K_4^- with y_1y_2 \in E(G). Let w_1,w_2,w_3 \in N(y_2)- {x_1,x_2} be distinct. We show that G contains a TK_5 in which y_2 is not a branch vertex, or G - y_2 contains K_4^-, or G has a special 5-separation, or G' := G - {y_2v : v \in {w_1,w_2,w_3, x_1, x_2}} contains TK_5.In this talk, we will obtain a substructure in G' and several additional paths in G', and then use this substructure to find the desired TK_5.

The Kelmans-Seymour conjecture II: 2-vertices in K_4^- (Non-separating paths)

Series
Graph Theory Seminar
Time
Wednesday, February 24, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
We use K_4^- to denote the graph obtained from K_4 by removing an edge,and use TK_5 to denote a subdivision of K_5. Let G be a 5-connected nonplanar graph and {x_1, x_2, y_1, y_2} \subseteq V (G) such that G[{x_1,x_2, y_1, y_2}] = K_4^- with y_1y_2 \in E(G). Let w_1,w_2,w_3 \in N(y_2)- {x_1,x_2} be distinct. We show that G contains a TK_5 in which y_2 is not a branch vertex, or G - y_2 contains K_4^-, or G has a special 5-separation, or G - {y_2v : v \in {w_1,w_2,w_3, x_1, x_2}} contains TK_5.In this talk, we will show the existence of a path X in G whose removal does not affect connectivity too much.

The Kelmans-Seymour conjecture II: special separations (5-separations containing a triangle)

Series
Graph Theory Seminar
Time
Friday, February 5, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of K_5. This conjecture was proved by Ma and Yu for graphs containing K_4^-. In order to establish the Kelmans-Seymour conjecture for all graphs, we need to consider 5-separations and 6-separations with less restrictive structures. We will talk about special 5-separations and 6-separations whose cut contains a triangle. Results will be used in subsequently to prove the Kelmans-Seymour conjecture.

The Kelmans-Seymour conjecture I: Special Separations

Series
Graph Theory Seminar
Time
Wednesday, January 27, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of K_5. This conjecture was proved by Ma and Yu for graphs containing K_4^-, and an important step in their proof is to deal with a 5-separation in the graph with a planar side. In order to establish the Kelmans-Seymour conjecture for all graphs, we need to consider 5-separations and 6-separations with less restrictive structures. We will talk about special 5-separations and 6-separations, including those with an apex side. Results will be used in subsequently to prove the Kelmans-Seymour conjecture.

Pages