Georgia Institute of Technology College of Sciences

A graph $G$ contains a graph $H$ as an immersion if there exist distinct vertices $\pi(v) \in V(G)$ for every vertex $v \in V(H)$ and paths $P(e)$ in $G$ for every $e \in E(H)$ such that the path $P(uv)$ connects the vertices $\pi(u)$ and $\pi(v)$ in $G$ and furthermore the paths $\{P(e):e \in E(H)\}$ are pairwise edge disjoint. Thus, graph immersion can be thought of as a generalization of subdivision containment where the paths linking the pairs of branch vertices are required to be pairwise edge disjoint instead of pairwise internally vertex disjoint. We will present a simple structure theorem for graphs excluding a fixed $K_t$ as an immersion. The structure theorem gives rise to a model of tree-decompositions based on edge cuts instead of vertex cuts. We call these decompositions tree-cut decompositions, and give an appropriate definition for the width of such a decomposition. We will present a ``grid" theorem for graph immersions with respect to the tree-cut width. This is joint work with Paul Seymour.

In the node-connectivity augmentation problem, we want to add a minimum number of new edges to an undirected graph to make it k-node-connected. The complexity of this question is still open, although the analogous questions of both directed and undirected edge-connectivity and directed node-connectivity augmentation are known to be polynomially solvable. I present a min-max formula and a polynomial time algorithm for the special case when the input graph is already (k-1)-connected. The formula has been conjectured by Frank and Jordan in 1994. In the first lecture, I shall investigate the background, present some results on the previously solved connectivity augmentation cases, and exhibit examples motivating the complicated min-max formula of my paper.

We consider intersection graphs of families of straight line segments in the euclidean plane and show that for every integer k, there is a family S of line segments so that the intersection graph G of the family S is triangle-free and has chromatic number at least k. This result settles a conjecture of Erdos and has a number of applications to other classes of intersection graphs.

Chudnovsky and Seymour's structure theorem for quasi-line graphs has led to a multitude of recent results that exploit two structural operations: compositions of strips and thickenings. In this paper we prove that compositions of linear interval strips have a unique optimal strip decomposition in the absence of a specific degeneracy, and that every claw-free graph has a unique optimal antithickening, where our two definitions of optimal are chosen carefully to respect the structural foundation of the graph. Furthermore, we give algorithms to find the optimal strip decomposition in O(nm) time and find the optimal antithickening in O(m2) time. For the sake of both completeness and ease of proof, we prove stronger results in the more general setting of trigraphs. This gives a comprehensive "black box" for decomposing quasi-line graphs that is not only useful for future work but also improves the complexity of some previous algorithmic results. Joint work with Maria Chudnovsky.