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

On Subgraphs of Large Girth
(Georgia Institute of Technology, 201205) 
On Some ChiBounded Classes of Graphs
(Georgia Institute of Technology, 201205) 
Unavoidable Minors of Large 2 and 3Connected Matroids
(Georgia Institute of Technology, 201205)It is well known that every sufficiently large 2connected loopless graph has a big cycle or a big bond. Twenty years ago, at the Seattle Graph Minors Conference, Robin Thomas asked whether the analogous result is true for ... 
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 ... 
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 ... 
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 ... 
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. 
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 ... 
Embeddability of Infinite Graphs
(Georgia Institute of Technology, 201205) 
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 ... 
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 ... 
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 ... 
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 ... 
Subgraph Statistics for Geometric Graphs
(Georgia Institute of Technology, 201205)We determine the asymptotics logorithmic density of subgraphs of large geometric graphs and of some large sparse graphs (from a nowhere dense class). This also leads to a unified approach to graph limits for both sparse ... 
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 ... 
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 ... 
On the Connectivity of Random Graphs from Addable Classes
(Georgia Institute of Technology, 201205)A class \mathcal G of graphs is called weakly addable if for any G\in \mathcal G and any two distinct components C_1 and C_2 in G, any graph that can be obtained by adding an edge between C_1 and C_2 is also in \mathcal ... 
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. ... 
Topologically Wellquasiordered Classes of Graphs
(Georgia Institute of Technology, 201205)The defining question is when is a topologically closed class of finite graphs a wellquasiorder (for short wqo). 
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 ...