Seminars and Colloquia by Series

Finding small simple cycle separators for 2-connected planar graphs

Series
Graph Theory Working Seminar
Time
Wednesday, November 7, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Michael Wigal – Georgia Tech
For a graph on $n$ vertices, a vertex partition $A,B,C$ is a $f(n)$-vertex separator if $|C| \le f(n)$ and $|A|,|B| \le \frac{2}{3}n$ and $(A,B) = \emptyset$. A theorem from Gary Miller states for an embedded 2-connected planar graph with maximum face size $d$ there exists a simple cycle such that it is vertex separator of size at most $2\sqrt{dn}$. This has applications in divide and conquer algorithms.

(2P2, K4)-Free Graphs are 4-Colorable

Series
Graph Theory Working Seminar
Time
Wednesday, October 31, 2018 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Shijie Xie – Georgia Tech
A graph G is H-free if H is not isomorphic to an induced subgraph of G. Let Pt denote the path on t vertices, and let Kn denote the complete graph on n vertices. For a positive integer r, we use rG to denote the disjoint union of r copies of G. In this talk, we will discuss the result, by Gaspers and Huang, that (2P2, K4)-free graphs are 4-colorable, where the bound is attained by the five-wheel and the complement of seven-cycle. It answers an open question by Wagon in 1980s.

Strong chromatic index for (3, Δ)-bipartite graphs

Series
Graph Theory Working Seminar
Time
Wednesday, October 24, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Chi-Nuo Lee – Georgia Tech
Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most (5/4)Δ^2 colors. A (Δ_a, Δ_ b)-bipartite graphs is an bipartite graph such that its components A,B has maximum degree Δ_a, Δ_ b respectively. R.A. Brualdi and J.J. Quinn Massey (1993) conjectured that the strong chromatic index of (Δ_a, Δ_ b)-bipartite graphs is bounded by Δ_a*Δ_ b. In this talk, we focus on a recent result affirming the conjecture for (3, Δ)-bipartite graphs.

Induced matching and strong chromatic index in bipartite graphs

Series
Graph Theory Working Seminar
Time
Wednesday, October 17, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Chi-Nuo Lee – Georgia Tech
Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most (5/4)Δ^2 colors. In this talk, we focus on a conjecture by R.J. Faudree et al, that Δ^2 holds as a bound for strong chromatic index in bipartite graphs, and related results where a bound is known.

Strong Chormatic Index on Graphs with Maximal Degree Four

Series
Graph Theory Working Seminar
Time
Wednesday, October 3, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
James Anderson – Georgia Tech
Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most (5/4)Δ^2 colors. In this talk we discuss recent progress made in the case of Δ=4, and go through the method used to improve the upper bound to 21 colors, one away from the conjectured 20.

Hypergraph cuts above the average

Series
Graph Theory Working Seminar
Time
Wednesday, September 26, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Dantong Zhu – Georgia Tech
A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω(√m), and this is best possible. We will continue our discussion about recent results on analogues of Edwards’ result and related problems in hypergraphs.

Hypergraph cuts above the average

Series
Graph Theory Working Seminar
Time
Wednesday, September 19, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Dantong Zhu – Georgia Tech
An $r$-cut of a $k$-uniform hypergraph $H$ is a partition of the vertex set of $H$ into $r$ parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every $m$-edge graph has a 2-cut of size $m/2+\Omega(\sqrt{m})$, and this is best possible. In this talk we will discuss recent results on analogues of Edwards’ result and related problems in hypergraphs.

Gallai’s path decomposition conjecture

Series
Graph Theory Working Seminar
Time
Wednesday, September 12, 2018 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Youngho Yoo – Georgia Tech
Gallai conjectured in 1968 that the edges of a connected graph on n vertices can be decomposed into at most (n+1)/2 edge-disjoint paths. This conjecture is still open, even for planar graphs. In this talk we will discuss some related results and special cases where it is known to hold.

Independent sets in hypergraphs

Series
Graph Theory Working Seminar
Time
Wednesday, September 5, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Xiaofan Yuan – Georgia Tech
We will go through the proof of the hypergraph container result of Balogh, Morris, and Samotij. We will also discuss some applications of this container result.

Independent sets in hypergraphs

Series
Graph Theory Working Seminar
Time
Wednesday, August 29, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skile 006
Speaker
Xiaofan Yuan – Georgia Tech
Many combinatorial questions can be formulated as problems about independent sets in uniform hypegraphs, including questions about number of sets with no $k$-term arithmetic progression and questions about typical structure of $H$-free graphs. Balogh, Morris, and Samotij and, independently, Saxton and Thomason gave an approximate structural characterization of all independent sets in uniform hypergraphs with natural contitions on edge distributions, using something called "containers". We will go through the proof of the hypergraph container result of Balogh, Morris, and Samotij. We will also discuss some applications of this container result.

Pages