Seminars and Colloquia by Series

Wednesday, March 13, 2019 - 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. The conjecture is still open for Δ=4. We show the conjecture is true when an edge cut of size 1 or 2 exists, and in certain cases when an edge cut of size 4 or 3 exists.    
Wednesday, March 6, 2019 - 16:30 , Location: Skiles 006 , Youngho Yoo , Georgia Tech , Organizer: Xingxing Yu

Let $\nu$ denote the maximum size of a packing of edge-disjoint triangles in a graph $G$. We can clearly make $G$ triangle-free by deleting $3\nu$ edges. Tuza conjectured in 1981 that $2\nu$ edges suffice, and proved it for planar graphs. The best known general bound is $(3-\frac{3}{23})\nu$ proven by Haxell in 1997. We will discuss this proof and some related results.

Wednesday, February 20, 2019 - 16:30 , Location: Skiles 006 , Michael Wigal , Georgia Tech , Organizer: Xingxing Yu
Let $g(n) = \max_{|T| = n}|\text{Aut}(T)|$ where $T$ is a tournament. Goldberg and Moon conjectured that $g(n) \le \sqrt{3}^{n-1}$ for all $n \ge 1$ with equality holding if and only if $n$ is a power of 3. Dixon proved the conjecture using the Feit-Thompson theorem. Alspach later gave a purely combinatorial proof. We discuss Alspach's proof and and some of its applications.
Tuesday, February 19, 2019 - 16:30 , Location: Skiles 006 , Michael Wigal , Georgia Tech , Organizer: Xingxing Yu
Let $g(n) = \max_{|T| = n}|\text{Aut}(T)|$ where $T$ is a tournament. Goldberg and Moon conjectured that $g(n) \le \sqrt{3}^{n-1}$ for all $n \ge 1$ with equality holding if and only if $n$ is a power of 3. Dixon proved the conjecture using the Feit-Thompson theorem. Alspach later gave a purely combinatorial proof. We discuss Alspach's proof and and some of its applications.
Wednesday, February 6, 2019 - 16:30 , Location: Skiles 006 , Joshua Schroeder , Georgia Tech , Organizer: Xingxing Yu
<p>Strong edge coloring of a graph $G$ is a coloring of the edges of the graph such that each color class is an induced subgraph. The strong chromatic index of $G$ is the smallest number $k$ such that $G$ has a $k$-strong edge coloring. Erd&odblac;s and Ne&scaron;et&rcaron;il conjecture that the strong chromatic index of a graph of max degree $\Delta$ is at most $5\Delta^2/4$ if $\Delta$ is even and $(5\Delta^2-2\Delta + 1)/4$ if $\Delta$ is odd. It is known for $\Delta=3$ that the conjecture holds, and in this talk I will present part of Anderson's proof that the strong chromatic index of a subcubic planar graph is at most $10$</p>
Wednesday, November 28, 2018 - 16:30 , Location: Skiles 006 , Prasad Tetali , Georgia Tech , Organizer: Xingxing Yu
Continuing on the theme mentioned in my recent&nbsp;research horizons lecture, I will illustrate two techniques by deriving upper and lower&nbsp;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.&nbsp;
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&nbsp;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
&nbsp;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&nbsp;(Δ_a,&nbsp;Δ_ b)-bipartite graphs is an&nbsp;bipartite graph such that its&nbsp;components A,B has maximum degree Δ_a,&nbsp;Δ_&nbsp;b respectively.&nbsp;R.A. Brualdi and&nbsp;J.J. Quinn Massey&nbsp;&nbsp;(1993) conjectured&nbsp;that the strong chromatic index of&nbsp;(Δ_a,&nbsp;Δ_&nbsp;b)-bipartite graphs&nbsp; is bounded by&nbsp;Δ_a*Δ_&nbsp;b.&nbsp;In this talk, we focus on a&nbsp;recent result affirming the conjecture for&nbsp;(3,&nbsp;Δ)-bipartite graphs.&nbsp;

Pages