Now showing items 1-20 of 33

    • 5-List-Coloring Graphs on Surfaces 

      Postle, Luke (Georgia Institute of Technology, 2012-05)
      Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. We develop new techniques to prove a general theorem for 5-list-coloring ...
    • 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 ...
    • Clique Immersion in Digraphs 

      McDonald, Jessica (Georgia Institute of Technology, 2012-05)
      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 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 ...
    • Coloring Graphs on Surfaces 

      Dvorak, Zdenek (Georgia Institute of Technology, 2012-05)
      We give an overview of the recent progress on coloring embedded graphs.
    • 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 ...
    • 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 ...
    • Embeddability of Infinite Graphs 

      Salazar, Gelasio (Georgia Institute of Technology, 2012-05)
    • Excluded Forest Minors and the Erdos-Posa Property 

      Joret, Gwenael (Georgia Institute of Technology, 2012-05)
      A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the so-called Erdos-Posa property; namely, there exists a function f depending only on H such that, ...
    • Extending Polynomials in Combinatorics 

      Loebl, Martin (Georgia Institute of Technology, 2012-05)
      Tutte polynomial is an extension of the chromatic polynomial. Fruitful source of extensions is q-commutation and determinant: q-MacMahon Master theorem is an important example. I will describe the basic setting and show ...
    • Extremal Problems in Eulerian Digraphs 

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

      Chudnovsky, Maria (Georgia Institute of Technology, 2012-05)
      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 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 ...
    • 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. ...
    • 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 ...
    • 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 ...
    • Large Clique Minors in Vertex Transitive Graphs 

      Mohar, Bojan (Georgia Institute of Technology, 2012-05)
      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))-ring-like or is a vertex transitive ...
    • Linkless Embeddings in 3-space 

      Kreutzer, Stephan (Georgia Institute of Technology, 2012-05)
      We consider piecewise linear embeddings of graphs in the 3-space 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 

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

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