Georgia Institute of Technology College of Sciences

A graph is k-critical if it is not (k-1)-colorable but every proper subgraph is. In 1963, Gallai conjectured that every k-critical graph G of order n has at least (k-1)n/2 + (k-3)(n-k)/(2k-2) edges. The currently best known results were given by Krivelevich for k=4 and 5, and by Kostochka and Stiebitz for k>5. When k=4, Krivelevich's bound is 11n/7, and the bound in Gallai's conjecture is 5n/3 -2/3. Recently, Farzad and Molloy proved Gallai's conjecture for k=4 under the extra condition that the subgraph induced by veritces of degree three is connected. We will review the proof given by Krivelevich, and the proof given by Farzad and Molloy in the seminar.

This will be a continuation from last week. We extend the theory of infinite matroids recently developed by Bruhn et al to a well-known classical result in finite matroids while using the theory of connectivity for infinitematroids of Bruhn and Wollan. We prove that every infinite connected matroid M determines a graph-theoretic decomposition tree whose vertices correspond to minors of M that are3-connected, circuits, or cocircuits, and whose edges correspond to 2-separations of M. Tutte and many other authors proved such a decomposition for finite graphs; Cunningham andEdmonds proved this for finite matroids and showed that this decomposition is unique if circuits and cocircuits are also allowed. We do the same for infinite matroids. The knownproofs of these results, which use rank and induction arguments, do not extend to infinite matroids. Our proof avoids such arguments, thus giving a more first principles proof ofthe finite result. Furthermore, we overcome a number of complications arising from the infinite nature of the problem, ranging from the very existence of 2-sums to proving the treeis actually graph-theoretic.

We discuss open research questions surrounding the traveling salesman problem. A focus will be on topics having potential impact on the computational solution of large-scale problem instances.

Rota asked in the 1960's how one might construct an axiom system for infinite matroids. Among the many suggested answers were the B-matroids of Higgs. In 1978, Oxley proved that any infinite matroid system with the notions of duality and minors must be equivalent to B-matroids. He also provided a simpler mixed basis-independence axiom system for B-matroids, as opposed to the complicated closure system developed by Higgs. In this talk, we examine a recent paper of Bruhn et al that gives independence, basis, circuit, rank, and closure axiom systems for B-matroids. We will also discuss some open problems for infinite matroids.