Seminars and Colloquia by Series

TBA by Xiaonan Liu

Series
Graph Theory Working Seminar
Time
Tuesday, September 29, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Xiaonan LiuGeorgia Institute of Technology

TBA

Packing A-paths and cycles in undirected group-labelled graphs

Series
Graph Theory Working Seminar
Time
Tuesday, September 22, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Youngho YooGeorgia Institute of Technology

An $A$-path is a path whose intersection with a vertex set $A$ is exactly its endpoints. We show that, for all primes $p$, the family of $A$-paths of length $0 \,\mathrm{mod}\, p$ satisfies an approximate packing-covering duality known as the Erdős-Pósa property. This answers a recent question of Bruhn and Ulmer. We also show that, if $m$ is an odd prime power, then for all integers $L$, the family of cycles of length $L \,\mathrm{mod}\, m$ satisfies the Erdős-Pósa property. This partially answers a question of Dejter and Neumann-Lara from 1987 on characterizing all such integer pairs $L$ and $m$. Both results are consequences of a structure theorem which refines the Flat Wall Theorem of Robertson and Seymour to undirected group-labelled graphs analogously to a result of Huynh, Joos, and Wollan in the directed setting. Joint work with Robin Thomas.

Chromatic number of graphs with no indeuced 3-matching

Series
Graph Theory Working Seminar
Time
Thursday, March 5, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Joshua SchroederGeorgia Tech
In 1980, Wagon showed that $\chi(G) \leq f_m(n)$ for any $\{mK_2, K_n\}$-free graph $G$, where $f_m$ is a polynomial and $mK_2$ is an induced matching of size $m$. However this bound is not known to be sharp. Recently, Gaspers and Huang helped sharpen this bound by showing for any $\{2K_2, K_4\}$-free graph $G$, that $\chi(G) \leq 4$. This resolves the question raised by Wagon for $m=2$, $n=4$. For the case where $m = 3$, it was shown by Brandt in 2002 that $(K_3, 3K_2)$-free graphs are 4-colorable.  In this talk, I will provide the outline for an alternate proof of this fact, as a byproduct of my research project.

Maximum Weight Internal Spanning Tree Problem

Series
Graph Theory Working Seminar
Time
Thursday, February 20, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Arti Pandey Indian Institute of Technology Ropar

Given a vertex-weighted graph G= (V, E), the MaximumWeight Internal Spanning Tree (MWIST) problem is to find a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted version of this problem, known as Maxi-mum Internal Spanning Tree (MIST) problem, is a generalization of the Hamiltonian path problem, and hence, it is NP-hard. In the literature lot of research has been done on designing approximation algorithms to achieve an approximation ratio close to 1. The best known approximation algorithm achieves an approximation ratio of 17/13 for the MIST problem for general graphs. For the MWIST problem, the current best approximation algorithm achieves an approximation ratio of 2 for general graphs. Researchers have also tried to design exact/approximation algorithms for some special classes of graphs. The MIST problem parameterized by the number of internal vertices k, and its special cases and variants, have also been extensively studied in the literature. The best known kernel for the general problem has size 2k, which leads to the fastest known exact algorithm with running time O(4^kn^{O(1)}). In this talk, we will talk about some selected recent results on the MWIST problem.

Introduction to algebraic graph theory

Series
Graph Theory Working Seminar
Time
Wednesday, February 12, 2020 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
James AndersonGeorgia Tech
In this introductory talk, we explore the first 5 chapters of Biggs's Algebraic Graph Theory. We discuss the properties of the adjacency matrix  of graph G, as well as the relationship between the incidence matrix of G and the cycle space and cut space. We also include several other small results. This talk will be followed by later talks in the semester continuing from Biggs's book.

Large cycles in essentially 4-connected planar graphs

Series
Graph Theory Working Seminar
Time
Thursday, January 30, 2020 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michael WigalGeorgia Tech

Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but
there are 3-connected $n$-vertex graphs whose longest cycles have length
$\Theta(n^{\log_32})$. On the other hand,  Jackson and Wormald proved that an
essentially 4-connected $n$-vertex planar graph contains a cycle of
length at least $(2n+4)/5$, which was improved to $5(n+2)/8$ by Fabrici {\it et al}.  We improve this bound to $\lceil (2n+6)/3\rceil$ for $n\ge 6$ by proving a quantitative version of a result of Thomassen,
and the bound is best possible.

Tangles and approximate packing-covering duality

Series
Graph Theory Working Seminar
Time
Thursday, October 10, 2019 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho YooGeorgia Tech

Tangles capture a notion of high-connectivity in graphs which differs from $k$-connectivity. Instead of requiring that a small vertex set $X$ does not disconnect the graph $G$, a tangle “points” to the connected component of $G-X$ that contains most of the “highly connected part”. Developed initially by Robertson and Seymour in the graph minors project, tangles have proven to be a fundamental tool in studying the general structure of graphs and matroids. Tangles are also useful in proving that certain families of graphs satisfy an approximate packing-covering duality, also known as the Erd\H{o}s-P\'osa property. In this talk I will give a gentle introduction to tangles and describe some basic applications related to the Erd\H{o}s-P\'osa property.

The Combinatorial Nullstellensatz and its applications

Series
Graph Theory Working Seminar
Time
Thursday, September 5, 2019 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho YooGeorgia Tech

In 1999, Alon proved the “Combinatorial Nullstellensatz” which resembles Hilbert’s Nullstellensatz and gives combinatorial structure on the roots of a multivariate polynomial. This method has numerous applications, most notably in additive number theory, but also in many other areas of combinatorics. We will prove the Combinatorial Nullstellensatz and give some of its applications in graph theory.

Caterpillars in Erods-Hajnal

Series
Graph Theory Working Seminar
Time
Wednesday, April 17, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michail SarantisGeorgia Tech

The well known Erdos-Hajnal Conjecture states that every graph has the Erdos-Hajnal (EH) property. That is, for every $H$, there exists a $c=c(H)>0$ such that every graph $G$ with no induced copy of $H$ has the property $hom(G):=max\{\alpha(G),\omega(G)\}\geq |V(G)|^{c}$. Let $H,J$ be subdivisions of caterpillar graphs. Liebenau, Pilipczuk, Seymour and Spirkl proved that the EH property holds if we forbid both $H$ and $\overline{J}.$ We will discuss the proof of this result.

Strong edge colorings and edge cuts

Series
Graph Theory Working Seminar
Time
Wednesday, March 13, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
James AndersonGeorgia 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. 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.