Graph Theory @ Georgia Tech: Recent submissions
Now showing items 120 of 33

Tangles, Trees and Flowers
(Georgia Institute of Technology, 201205)Tangles provide a means of identifying highly connected components of a graph, matroid or, more generally, a connectivity function. For a tangle of order k in such a structure, the smallest order of a separation that can ... 
A Colin de VerdiereType Invariant and OddK_4 and OddK^2_3Free Signed Graphs
(Georgia Institute of Technology, 201205)We introduced a new Colin de Verdieretype invariant \nu(G,\Sigma) for signed graphs. This invariant is closed under taking minors, and characterizes bipartite signed graphs as those signed graphs (G,\Sigma) with ... 
Intersection Theorems for Finite Sets
(Georgia Institute of Technology, 201205)Finite extremal set theory is concerned with the following general problem: Suppose we have a collection F of subsets of an nelement set and we have some restriction on the possible intersection sizes of pairs of sets in ... 
Large Clique Minors in Vertex Transitive Graphs
(Georgia Institute of Technology, 201205)An important (yet unpublished) theorem of Babai states that there exists a function f: N > N so that every finite vertex transitive graph without K_n as a minor is either (f(n),f(n))ringlike or is a vertex transitive ... 
Clique Immersion in Digraphs
(Georgia Institute of Technology, 201205)Immersion is a containment relation between graphs (or digraphs) which is defined similarly to the more familiar notion of minors, but is incomparable to it. In this talk we focus on immersing a bidirected clique \vec{K}_t ... 
Discrepancy, Bansal's Algorithm and the Determinant Bound
(Georgia Institute of Technology, 201205)Recently Nikhil Bansal found a polynomialtime algorithm for computing lowdiscrepancy colorings, based on semidefinite programming. It makes several existential bounds for the discrepancy of certain set systems, such as ... 
Extremal Problems in Eulerian Digraphs
(Georgia Institute of Technology, 201205)Graphs and digraphs behave quite differently and many natural results for graphs are often trivially false for general digraphs. It is usually necessary to consider restricted families of digraphs to obtain meaningful ... 
Extending Polynomials in Combinatorics
(Georgia Institute of Technology, 201205)Tutte polynomial is an extension of the chromatic polynomial. Fruitful source of extensions is qcommutation and determinant: qMacMahon Master theorem is an important example. I will describe the basic setting and show ... 
An Upper Bound on the Fractional Chromatic Number
(Georgia Institute of Technology, 201205)An (a:b)coloring of a graph G is a function f which maps the vertices of G into belement subsets of some set of size a in such a way that f(u) is disjoint from f(v) for every two adjacent vertices u and v in G. The ... 
Linkless Embeddings in 3space
(Georgia Institute of Technology, 201205)We consider piecewise linear embeddings of graphs in the 3space R^3. Such an embedding is "linkless" if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas ... 
Deciding Properties in Sparse Combinatorial Structures
(Georgia Institute of Technology, 201205)Algorithmic metatheorems guarantee that certain types of problems have efficient algorithms. A classical example is the result of Courcelle asserting that every MSOL property can be tested in linear time for graphs with ... 
Braces and Pfaffian Orientations
(Georgia Institute of Technology, 201205)Robertson, Seymour, Thomas and simultaneously McCuaig answered several equivalent questions. Specifically, when can some of the 1's of a 01 square matrix, A, be changed to 1's so that the permanent of A equals the ... 
Planarity and Dimension for Graphs and Posets
(Georgia Institute of Technology, 201205)There is a rich history of research relating planarity for graphs and diagrams with the dimension of posets, starting with the elegant characterization of planarity for posets with a zero and a one: they are planar if and ... 
On Some ChiBounded Classes of Graphs
(Georgia Institute of Technology, 201205) 
Tutte's ThreeEdgeColouring Conjecture
(Georgia Institute of Technology, 201205)The fourcolour theorem is equivalent to the statement that every planar cubic graph with no cutedge is 3edgecolourable. What about nonplanar cubic graphs? The Petersen graph is not 3edgecolourable, and in 1966 Tutte ... 
Induced Subgraphs and Subtournaments
(Georgia Institute of Technology, 201205)Let H be a graph and let I be the set of all graphs that do not contain H as a minor. Then H is planar if and only if there is an upper bound on the treewidth of the members of I; and there are many other similar theorems ... 
Embeddability of Infinite Graphs
(Georgia Institute of Technology, 201205) 
On Subgraphs of Large Girth
(Georgia Institute of Technology, 201205) 
Separators, Brambles, Tree Decompositions and Excluding Clique Minors
(Georgia Institute of Technology, 201205)The talk surveys the relationships between these topics highlighting the fundamental contributions of Robin Thomas. 
5ListColoring Graphs on Surfaces
(Georgia Institute of Technology, 201205)Thomassen proved that there are only finitely many 6critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5listcolorable. We develop new techniques to prove a general theorem for 5listcoloring ...