TBA
TBA
TBA
TBA
TBA
TBA
Please Note: Note the unusual time!
TBA
TBA
A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex of degree at least 4. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of $G'$ from the cycles of $G$, where $G'$ is obtained from $G$ by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay's isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with $n$ vertices and $m$ edges from the non-isomorphic minimally 3-connected graphs with $n-1$ vertices and $m-2$ edges, $n-1$ vertices and $m-3$ edges, and $n-2$ vertices and $m-3$ edges. In this talk I will focus primarily on the theorems behind the algorithm. This is joint work with Joao Costalonga and Robert Kingan.
By the well-known theorem of Brooks, every graph of maximum degree Δ ≥ 3 and clique number at most Δ has chromatic number at most Delta. It is natural to ask (and is the subject of a conjecture of Borodin and Kostochka) whether this bound can be improved for graphs of clique number at most Δ - 1. While there has been little progress on this conjecture, there is a number of interesting results on the analogous question for the fractional chromatic number. We will report on some of them, including a result by myself Bernard Lidický and Luke Postle that except for a finite number of counterexamples, every connected subcubic triangle-free graph has fractional chromatic number at most 11/4.
Georgia Institute of Technology
North Avenue, Atlanta, GA 30332
Phone: 404-894-2000
