Seminars and Colloquia by Series

A Hereditary Generalization of the Nordhaus-Gaddum Graphs (Rebecca Whitman)

Series
Graph Theory Seminar
Time
Tuesday, November 12, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rebecca WhitmanUniversity 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.

Half-integral Erdős-Pósa property for non-null S–T paths (Meike Hatzel)

Series
Graph Theory Seminar
Time
Tuesday, October 22, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Meike HatzelInstitute 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.

Non-measurable colourings avoiding large distances (James Davies)

Series
Graph Theory Seminar
Time
Tuesday, October 8, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
James DaviesCambridge 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.

CANCELLED - Tight minimum colored degree condition for rainbow connectivity

Series
Graph Theory Seminar
Time
Friday, October 4, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xiaofan YuanArizona 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.

Proof of the Goldberg-Seymour conjecture (Guantao Chen)

Series
Graph Theory Seminar
Time
Tuesday, October 1, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Guantao ChenGeorgia 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. 

Degree-boundedness (Xiying Du)

Series
Graph Theory Seminar
Time
Tuesday, September 24, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xiying DuGeorgia 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. 

 On orientations of graphs with forbidden out-degrees (Owen Henderschedt, Auburn)

Series
Graph Theory Seminar
Time
Tuesday, September 17, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Owen HenderschedtAuburn 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.

Pages