Browsing Graph Theory @ Georgia Tech by Title
Now showing items 120 of 33

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 ... 
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 ... 
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 ... 
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 ... 
Coloring Graphs on Surfaces
(Georgia Institute of Technology, 201205)We give an overview of the recent progress on coloring embedded graphs. 
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 ... 
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 ... 
Embeddability of Infinite Graphs
(Georgia Institute of Technology, 201205) 
Excluded Forest Minors and the ErdosPosa Property
(Georgia Institute of Technology, 201205)A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the socalled ErdosPosa property; namely, there exists a function f depending only on H such that, ... 
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 ... 
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 ... 
Forcing Large Transitive Subtournamets
(Georgia Institute of Technology, 201205)The Erdos Hajnal Conjecture states roughly that a graph with some induced subgraph excluded has a large clique or a large stable set. A similar statement can be formulated for tournaments (a tournament is an orientation ... 
Graphs of Small RankWidth are PivotMinors of Graphs of Small TreeWidth
(Georgia Institute of Technology, 201205)We prove that every graph of rankwidth k is a pivotminor of a graph of treewidth at most 2k. We also prove that graphs of rankwidth at most 1, also known as distancehereditary graphs, are exactly vertexminors of ... 
GrowthRates of Matroid Classes
(Georgia Institute of Technology, 201205)For a minorclosed class of matroids, we consider the maximum number, h(n), of elements in a simple rankn matroid in the class. This growthrate function, when finite, is known to be either linear, quadratic, or exponential. ... 
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 ... 
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 ... 
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 ... 
Nonrepetitive Colourings
(Georgia Institute of Technology, 201205)A vertex colouring of a graph is nonrepetitive if there is no path whose first half receives the same sequence of colours as the second half. This talk will present some results on nonrepetitive colourings of planar graphs ... 
On Matchings and Covers
(Georgia Institute of Technology, 201205)Let H be a hypergraph. A matching in H is a set of pairwise disjoint edges of H. A cover of H is a set C of vertices that meets all edges of H. We discuss a number of conjectures and results that bound the minimum size of ...