Now showing items 1-20 of 33

    • On Subgraphs of Large Girth 

      Rodl, Vojtech (Georgia Institute of Technology, 2012-05)
    • On Some Chi-Bounded Classes of Graphs 

      Thomasse, Stephan (Georgia Institute of Technology, 2012-05)
    • Unavoidable Minors of Large 2- and 3-Connected Matroids 

      Oxley, James (Georgia Institute of Technology, 2012-05)
      It is well known that every sufficiently large 2-connected 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 

      Liu, Chun-Hung (Georgia Institute of Technology, 2012-05)
      An (a:b)-coloring of a graph G is a function f which maps the vertices of G into b-element 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 Verdiere-Type Invariant and Odd-K_4- and Odd-K^2_3-Free Signed Graphs 

      Van der Holst, Hein (Georgia Institute of Technology, 2012-05)
      We introduced a new Colin de Verdiere-type 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 Three-Edge-Colouring Conjecture 

      Seymour, Paul (Georgia Institute of Technology, 2012-05)
      The four-colour theorem is equivalent to the statement that every planar cubic graph with no cut-edge is 3-edge-colourable. What about non-planar cubic graphs? The Petersen graph is not 3-edge-colourable, and in 1966 Tutte ...
    • Separators, Brambles, Tree Decompositions and Excluding Clique Minors 

      Reed, Bruce (Georgia Institute of Technology, 2012-05)
      The talk surveys the relationships between these topics highlighting the fundamental contributions of Robin Thomas.
    • Braces and Pfaffian Orientations 

      Whalen, Peter (Georgia Institute of Technology, 2012-05)
      Robertson, Seymour, Thomas and simultaneously McCuaig answered several equivalent questions. Specifically, when can some of the 1's of a 0-1 square matrix, A, be changed to -1's so that the permanent of A equals the ...
    • Embeddability of Infinite Graphs 

      Salazar, Gelasio (Georgia Institute of Technology, 2012-05)
    • Planarity and Dimension for Graphs and Posets 

      Trotter, William T (Georgia Institute of Technology, 2012-05)
      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 

      Whittle, Geoff (Georgia Institute of Technology, 2012-05)
      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 

      Mubayi, Dhruv (Georgia Institute of Technology, 2012-05)
      Finite extremal set theory is concerned with the following general problem: Suppose we have a collection F of subsets of an n-element set and we have some restriction on the possible intersection sizes of pairs of sets in ...
    • Graphs of Small Rank-Width are Pivot-Minors of Graphs of Small Tree-Width 

      Oum, Sang-il (Georgia Institute of Technology, 2012-05)
      We prove that every graph of rank-width k is a pivot-minor of a graph of tree-width at most 2k. We also prove that graphs of rank-width at most 1, also known as distance-hereditary graphs, are exactly vertex-minors of ...
    • Subgraph Statistics for Geometric Graphs 

      Nesetril, Jaroslav (Georgia Institute of Technology, 2012-05)
      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 

      Seymour, Paul (Georgia Institute of Technology, 2012-05)
      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 

      Matousek, Jiri (Georgia Institute of Technology, 2012-05)
      Recently Nikhil Bansal found a polynomial-time algorithm for computing low-discrepancy 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 

      Kang, Mihyun (Georgia Institute of Technology, 2012-05)
      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 ...
    • Growth-Rates of Matroid Classes 

      Geelen, Jim (Georgia Institute of Technology, 2012-05)
      For a minor-closed class of matroids, we consider the maximum number, h(n), of elements in a simple rank-n matroid in the class. This growth-rate function, when finite, is known to be either linear, quadratic, or exponential. ...
    • Topologically Well-quasi-ordered Classes of Graphs 

      Robertson, Neil (Georgia Institute of Technology, 2012-05)
      The defining question is when is a topologically closed class of finite graphs a well-quasi-order (for short wqo).
    • Deciding Properties in Sparse Combinatorial Structures 

      Kral, Daniel (Georgia Institute of Technology, 2012-05)
      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 ...