Seminars and Colloquia by Series

Separators in sphere intersection graphs

Series
Graph Theory Seminar
Time
Tuesday, January 28, 2025 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Rose McCartyGeorgia Tech

We discuss the sphere dimension of a graph. This is the smallest integer $d$ such that the graph can be represented as the intersection graph of a collection of spheres in $\mathbb{R}^d$. We show that graphs with small sphere dimension have small balanced separators, as long as they exclude a complete bipartite graph $K_{t,t}$. This property is connected to forbidding shallow minors and can be used to develop divide-and-conquer algorithms. This is joint work with James Davies, Agelos Georgakopoulos, and Meike Hatzel.

Disjoint paths problem with group-expressable constraints (Chun-Hung Liu)

Series
Graph Theory Seminar
Time
Tuesday, December 3, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
246 Classroom Guggenheim
Speaker
Chun-Hung LiuTexas A&M University

(Note the unusual location!)

We study an extension of the k-Disjoint Paths Problem where, in addition to finding k disjoint paths joining k given pairs of vertices in a graph, we ask that those paths satisfy certain constraints expressable by abelian groups. We give an O(n^8) time algorithm to solve this problem under the assumption that the constraint can be expressed as avoiding a bounded number of group elements; moreover, our O(n^8) algorithm allows any bounded number of such constraints to be combined. Group-expressable constraints include, but not limited to: (1) paths of length r modulo m for any fixed r and m, (2) paths passing through any bounded number of prescribed sets of edges and/or vertices, and (3) paths that are long detours (paths of length at least r more than the distance between their ends for fixed r). The k=1 case with the modularity constraint solves problems of Arkin, Papadimitriou and Yannakakis from 1991. Our work also implies a polynomial time algorithm for testing the existence of a subgraph isomorphic to a subdivision of a fixed graph, where each path of the subdivision between branch vertices satisfies any combination of a bounded number of group-expressable constraints. In addition, our work implies similar results addressing edge-disjointness. It is joint work with Youngho Yoo.

Induced subgraphs of graphs of large K_r-free chromatic number (Aristotelis Chaniotis)

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

For an integer $r\geq 2$, the $K_{r}$-free chromatic number of a graph $G$, denoted by $\chi_{r}(G)$, is the minimum size of a partition of the set of vertices of $G$ into parts each of which induces a $K_{r}$-free graph. In this setting, the $K_{2}$-free chromatic number is the usual chromatic number.

Which are the unavoidable induced subgraphs of graphs of large $K_{r}$-free chromatic number? Generalizing the notion of $\chi$-boundedness, we say that a hereditary class of graphs is $\chi_{r}$-bounded if there exists a function which provides an upper bound for the $K_{r}$-free chromatic number of each graph of the class in terms of the graph's clique number. 

With an emphasis on a generalization of the Gy\'arf\'as-Sumner conjecture for $\chi_{r}$-bounded classes of graphs and on polynomial $\chi$-boundedness, I will discuss some recent developments on $\chi_{r}$-boundedness and related open problems. 

Based on joint work with Mathieu Rundstr\"om and Sophie Spirkl, and with Bartosz Walczak.
 

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. 

Pages