## Seminars and Colloquia by Series

Wednesday, November 28, 2018 - 16:30 , Location: Skiles 006 , Prasad Tetali , Georgia Tech , Organizer: Xingxing Yu
Continuing on the theme mentioned in my recent research horizons lecture, I will illustrate two techniques by deriving upper and lower bounds on the number of independent sets in bipartite and triangle-free graphs.
Wednesday, November 14, 2018 - 16:30 , Location: Skiles 006 , Michael Wigal , Georgia Tech , Organizer: Xingxing Yu
Continuation of last week's talk. For a graph on n vertices, a vertex partition A,B,C is a f(n)-vertex separator if |C|≤f(n) and |A|,|B|≤2n/3 and (A,B)=∅. 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√dn. This has applications in divide and conquer algorithms.
Wednesday, November 7, 2018 - 16:30 , Location: Skiles 006 , Michael Wigal , Georgia Tech , Organizer: Xingxing Yu
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.
Wednesday, October 31, 2018 - 16:30 , Location: Skiles 006 , Shijie Xie , Georgia Tech , Organizer: Xingxing Yu
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.
Wednesday, October 24, 2018 - 16:30 , Location: Skiles 006 , Chi-Nuo Lee , Georgia Tech , Organizer: Xingxing Yu
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.
Wednesday, October 17, 2018 - 16:30 , Location: Skiles 006 , Chi-Nuo Lee , Georgia Tech , Organizer: Xingxing Yu
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.
Wednesday, October 3, 2018 - 16:30 , Location: Skiles 006 , James Anderson , Georgia Tech , Organizer: Xingxing Yu
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.
Wednesday, September 26, 2018 - 16:30 , Location: Skiles 006 , Dantong Zhu , Georgia Tech , Organizer: Xingxing Yu
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.
Wednesday, September 19, 2018 - 16:30 , Location: Skiles 006 , Dantong Zhu , Georgia Tech , Organizer: Xingxing Yu
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.
Wednesday, September 12, 2018 - 16:30 , Location: Skiles 006 , Youngho Yoo , Georgia Tech , Organizer: Xingxing Yu
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.