### TBA by Chun-Hung Liu

- Series
- Graph Theory Seminar
- Time
- Tuesday, December 3, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Chun-Hung Liu – Texas A&M University

- You are here:
- Home
- News & Events

- Series
- Graph Theory Seminar
- Time
- Tuesday, December 3, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Chun-Hung Liu – Texas A&M University

- Series
- Graph Theory Seminar
- Time
- Tuesday, November 26, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Aristotelis Chaniotis – University of Waterloo

- Series
- Graph Theory Seminar
- Time
- Tuesday, November 12, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Rebecca Whitman – University of California Berkeley

Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number of a graph G and its complement is at most |G|+1. The Nordhaus-Gaddum graphs are the class of graphs satisfying this inequality with equality, and are well-understood. In this paper we consider a hereditary generalization: graphs G for which all induced subgraphs H of G satisfy that the sum of the chromatic numbers of H and its complement are at least |H|. We characterize the forbidden induced subgraphs of this class and find its intersection with a number of common classes, including line graphs. We also discuss chi-boundedness and algorithmic results.

- Series
- Graph Theory Seminar
- Time
- Tuesday, October 22, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Meike Hatzel – Institute for Basic Science (IBS)

For a group Γ, a Γ-labelled graph is an undirected graph G where every orientation of an edge is assigned an element of Γ so that opposite orientations of the same edge are assigned inverse elements. A path in G is non-null if the product of the labels along the path is not the neutral element of Γ. We prove that for every finite group Γ, non-null S–T paths in Γ-labelled graphs exhibit the half- integral Erdős-Pósa property. More precisely, there is a function f , depending on Γ, such that for every Γ-labelled graph G, subsets of vertices S and T , and integer k, one of the following objects exists:

• a family F consisting of k non-null S–T paths in G such that every vertex of G participates in at most two paths of F; or

• a set X consisting of at most f (k) vertices that meets every non-null S–T path in G.

This in particular proves that in undirected graphs S–T paths of odd length have the half-integral Erdős-Pósa property.

This is joint work with Vera Chekan, Colin Geniet, Marek Sokołowski, Michał T. Seweryn, Michał Pilipczuk, and Marcin Witkowski.

- Series
- Graph Theory Seminar
- Time
- Tuesday, October 8, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- James Davies – Cambridge University

In 1983, Furstenberg, Katznelson, and Weiss proved that for every finite measurable colouring of the plane, there exists a $d_0$ such that for every $d\geq d_0$ there is a monochromatic pair of points at distance $d$. In contrast to this, we show that there is a finite colouring avoiding arbitrarily large distances. Joint work with Rutger Campbell.

- Series
- Graph Theory Seminar
- Time
- Friday, October 4, 2024 - 15:15 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Xiaofan Yuan – Arizona State University

Let $G = (V,E)$ be a graph on $n$ vertices, and let $c : E \to P$, where $P$ is a set of colors. Let $\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}$ where $d^c(v)$ is the number of colors on edges incident to a vertex $v$ of $G$. In 2011, Fujita and Magnant showed that if $G$ is a graph on $n$ vertices that satisfies $\delta^c(G)\geq n/2$, then for every two vertices $u, v$ there is a properly-colored $u,v$-path in $G$.

In this paper, we show that the same bound for $\delta^c(G)$ implies that any two vertices are connected by a rainbow path. This is joint work with Andrzej Czygrinow.

This is to note that the graph theory seminar for Friday the 4th has been CANCELLED. This is due to the cancellation of the AMS sectional meeting due to Hurricane Helene. I apologize for any inconvenience. We intend to reschedule the talk for next semester.

- Series
- Graph Theory Seminar
- Time
- Tuesday, October 1, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Guantao Chen – Georgia State University

The Goldberg-Seymour Conjecture asserts that if the chromatic index $\chi'(G)$ of a loopless multigraph $G$ exceeds its maximum degree $\Delta(G) +1$, then it must be equal to another well known lower bound $\Gamma(G)$, defined as

$\Gamma(G) = \max\left\{\biggl\lceil \frac{ 2|E(H)|}{(|V (H)|-1)}\biggr\rceil \ : \ H \subseteq G \mbox{ and } |V(H)| \mbox{ odd }\right\}.$

In this talk, we will outline a short proof, obtained recently with Hao, Yu, and Zang.

- Series
- Graph Theory Seminar
- Time
- Tuesday, September 24, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Xiying Du – Georgia Tech

We say a class of graphs $\mathcal{F}$ is degree-bounded if there exists a function $f$ such that $\delta(G)\le f(\tau(G))$ for every $G\in\mathcal{F}$, where $\delta(G)$ denotes the minimum degree of $G$ and $\tau(G)$ is the biclique number of $G$, that is, the largest integer $t$ such that $G$ contains $K_{t,t}$ as a subgraph. Such a function $f$ is called a degree-bounding function for $\mathcal{F}$.

In joint work with Ant\'onio Gir\~ao, Zach Hunter, Rose McCarty and Alex Scott, we proved that every hereditary degree-bounded class $\mathcal{F}$ has a degree-bounding function that is singly exponential in the biclique number $\tau$. A more recent result by Ant\'onio Gir\~ao and Zach Hunter improved this bound to a polynomial function in $\tau$. In this talk, I will discuss examples and the recent results on degree-boundedness.

- Series
- Graph Theory Seminar
- Time
- Tuesday, September 24, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Xiying Du – Georgia Tech – xdu90@gatech.edu

- Series
- Graph Theory Seminar
- Time
- Tuesday, September 17, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Owen Henderschedt – Auburn University

When does a graph admit an orientation with some desired properties? This question has been studied extensively for many years and across many different properties. Specifically, I will talk about properties having to do with degree restrictions, and progress towards a conjecture of Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati dealing with a list-type of degree restriction. This is all joint work with my PhD advisor Jessica McDonald.