Georgia Institute of Technology College of Sciences

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$. We show that for sufficiently large graphs $G$ 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.

Caleb McFarland: We prove a structure theorem for Γ-labeled graphs G which forbid a fixed Γ-labeled graph H as an immersion in the case that Γ is a finite abelian group. Joint work with Rose McCarty and Paul Wollan.
Richter Jordaan: In this expository talk I will give introduce an approach to the cycle double cover based on the more general problem of finding specific cycle covers of cubic graphs. After stating the basics of the cycle double cover conjecture and structure of a minimal counterexample, I'll try to describe the setup and basic intuition behind how the general cyle cover problem could be used to approach the cycle double cover conjecture.
Owen Huang: We will discuss some recent work with Rose McCarty concerning the product structure of Cayley graphs. We also introduce an integer-valued invariant of finitely generated groups and note its relevance in geometric group theory. 

(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.

 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.