Luke Postle

I am a fifth year PhD student enrolled in Georgia Tech's, Algorithms, Combinatorics and Optimization doctoral program. My advisor is Robin Thomas.

Contact Information:

Luke Postle
1816 Harper St
Atlanta, GA 30308, USA
Email: ljpostle(at)math.gatech.edu
Phone: 404-281-5388
Office: Skiles 138

Research Interests

Research sponsored by the National Science Foundation.

Curriculum Vitae

News

Teaching

Awards and Fellowships

Publications and Manuscripts

Journal Publications
  1. Five Coloring Graphs on the Klein Bottle (with N. Chenette, N. Streib, R. Thomas and C. Yerger), J. Combin. Theory Ser. B, submitted.
  2. Pebbling Graphs of Diameter Three and Four (with N. Streib and C. Yerger), J. Graph Theory, accepted, 2011.
  3. Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs (with A. Asadi, Z. Dvorak and R. Thomas), J. Combin. Theory Ser. B, submitted.
  4. Pebbling Graphs of Fixed Diameter, J. Graph Theory, submitted.
  5. Decomposing Infinite Matroids into 3-connected blocks. (with E.Aigner-Horev and R. Diestel), J. Combin. Theory Ser. B, submitted.
  6. A Linear Upper Bound for 6-Critical Graphs on Surfaces (with R. Thomas), manuscript.
  7. A short proof of Archdeacon's Theorem. Part I: 3-connected non-projective planar graphs with a nontrivial 3-cut (with A. Asadi and R. Thomas), in preparation.
  8. 5-list-coloring planar graphs with distant precolored vertices (with Z. Dvorak, B. Lidicky, and B. Mohar), in preparation.
Refereed Conference Papers
  1. Six-critical graph on the Klein bottle. Extended abstract (with N. Chenette, K. Kawarabayashi, D. Kral, J. Kyncl, B. Lidicky, N. Streib, R. Thomas and C. Yerger), Electronic Notes in Discrete Mathematics 31 (2008), 235--240
  2. Pebbling Graphs of Diameter Three and Four (with N. Streib and C. Yerger), Electronic Notes in Discrete Math 34 (2009), 21--28.
  3. Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs (with A. Asadi and R. Thomas), Electronic Notes in Discrete Math 34 (2009), 81--87.

Research Projects to Date

Five Coloring Graphs on the Klein Bottle

Objective: Find the list of six-critical graphs on the Klein Bottle.

Collaborators: Nathan Chenette, Noah Streib, Robin Thomas, Carl Yerger

Overview: A six-critical graph is a graph that is not five-colorable but every subgraph is. This work furthers that of Carsten Thomassen who found the list of six-critical graphs on the Torus in 1994. Our techniques are similar to Thomassen's. We prove that all six-regular graphs on the Klein Bottle are five-colorable. By Euler's formula, we may assume a vertex of degree five. We idenitfy non-adjacent vertices in its neighborhood. The resulting graph must contain a six-critical graph on our list. Reversing this procedure, we split open graphs on our conjectured list to show that there are no new candidates. While our techniques are similar to Thomassen, we had to develop new techniques to handle the Klein Bottle. Also our final list has nine graphs as opposed to the four on the Torus.

Results: We found a list of nine six-critical graphs on the Klein Bottle. As corollary this implies a result of Kral et al that every eurlerian triangluation of the Klein Bottle that is not five-colorable must contain K6 as subdivision.


Pebbling Graphs of Diameter Three and Four

Objective: To prove an upper bound on the pebbling number of graphs of diameter three and four

Collaborators: Noah Streib, Carl Yerger

Overview: The pebbling number of a graph is defined to be the minimum integer k such that given any configuration of k pebbles on the graph and any vertex v on the graph, pebbling moves can be made to give the vertex v a pebble. A pebbling move is removing two pebbles from one vertex and placing a pebble on an adjacent vertex. The pebbling number of a graph is at least n pebbles since we can place a pebble on all but one vertex and not be able to pebble it. Moreover, the pebbling number is linked to diameter, since long paths require exponentially many pebbles to send from one end to the other. The maximum pebbling number of graphs of diameter two is n + 1. We improve on the work of Bukh to give an exact bound for graphs of diameter three: 3n/2 + 2, which is best possible. Moreover, we developed new techniques that decompose a graph into 'irreducible branches'. This allowed us to improve the bound for the general diamter as well as prove an upper bound of 3n/2 + O(1) for graphs of diameter four, which is also best possible.This last two results combine the technique of branches used for diameter three with a discharging argument developed for the general diameter case.

Results: We prove an exact bound of 3n/2 + 2 for the maximum pebbling number of graphs of diameter three. We prove an asymptotic bound of 3n/2 + O(1) for graphs of diameter four. Both are best possible.

Pebbling Graphs of Fixed Diameter

Objective: To prove the best possible upper bound on the pebbling number of graphs of fixed diameter

Overview: In a previous work with N. Streib and C. Yerger, we proved that the pebbling number of graph of diamter 3 is at most 3n/2+1. We also exhibit examples for every n where this is tight. Similarly, the pebbling number of a graph of diameter 4 is 3n/2+O(1). This bound is aymptotically tight. In this work, I extended the asymptotic results to graphs of arbitrary diameter d. I combined the decomposition into irreducible branches with the notion of dominating sets. In this way, I showed that the intuitive worst case of a central hub and many paths of length d/2 coming out of it (i.e. a "star") gives the worst bound asymptotically. Furthermore, I generalized this work to the mth pebbling number (the number needed ot place m pebbles on any given vertex). The main lemma generalizes a result of Chan and Godbole. Namely, it gives a bound of the pebbling number of a graph in terms of the size of the smallest k-domintaing set.

Results: We prove a upper bound of f(d)n + O(n^.5) for the maximum pebbling number of graphs of diameter d, where f(d)=(2^k-1)/k where k is the floor of d/2. For odd d, we show that the bound can be tightened to f(d)n+O(1), which is aymptotically best possible.

Sub-Exponentially Many 3-Colorings of Triangle-Free Plane Graphs

Objective: To prove a conjecture of Thomassen that every triangle-free planar graph has exponenitially many 3-colorings.

Collaborators: Arash Asadi, Robin Thomas

Overview: A classical theorem of Grotzsch states that every triangle-free planar graph has a 3-coloring. Thomassen proved that every triangle-free planar graph has at least 2^(n^(1/12) / 20000) distinct 3-colorings. Thomassen conjectured that every triangle-free planar graph has at least 2^O(n) distinct 3-colorings. We noted that a vertex v that is not in any 5-cycles gives a reduction. Namely if G' is obtained from G by deleting v and identifying its neighbors, then the number of 3-colorings of G is at least double that of G'. We then show that if every vertex is in a 5-cycle, then there exist a laminar family of 5-cycles covering all the vertices (laminar meaning non-crossing in the plane). That is, there exists a "good" reduction or a linear sized laminar family of 5-cycles. We use Dilworth's theorem for posets to break such a laminar family into chains and antichains. We obtain either a chain of size n^.5 or an antichain of size n^.5.Using an idea of Thomassen it is easy to show that G has at least 2^O(a) 3-colorings where G has an antichain of 5-cycles of size a. Finally, using complicated discharging arguments we show that if G has a chain of 5-cycles of size c, then G has at least 2^O(c) 3-colorings. Such a proof using Dilworth's theorem also suggests the examples that might give a counterexample to the conjecture; though none has been found.

Results: We proved that every triangle free plane graph has at least 2^O(n^.5) 3-colorings.

A Linear Upper Bound for 6-Critical Graphs in Surfaces

Objective: To prove that if G is a 6-critical graph embeddable on a surface S, then |V(G)|=O(g(s)) where g(S) is the genus of S.

Collaborators: Robin Thomas

Overview:We say a graph G is k-critical if G cannot be colored with k-1 colors but every subgraph can be. Euler's formula shows that there are only finitely many k-critical graphs embeddable on a fixed surface where k is greater than or equal to 8. Gallai showed that there are only finitely many 7-critical graphs embeddable on a fixed surface. A deep theorem of Thomassen states that there only finitely many 6-critical graphs embeddable on a fixed surface. There are infinitely many 3-critical graphs (odd cycles) and 4-critical graphs embeddable on the plane. This makes sense since testing the 3-colorability of planar graphs is NP-hard. A construction of Fisk shows that there infinitely many toroidal 5-critical graphs. The previous results give a linear time algorithm for testing the k-colorability of graphs embeddable on a fixed surface for all k >= 6.

A natural question to ask is what is the maximum number of vertices of a k-critical graph embeddable on a fized surface. For k at least seven, it is not hard to prove that this number is linear in the size of the genus. For k=6, Thomassen's proof gives a doubly exponential bound. A recent work of Kawarabayshi and Yerger gives a shorter proof of Thomassen's result and an exponential bound. In this paper, we use discharging to give a linear bound! We use a form of discharging that tracks the size of faces as well as vertices. This method, developed by Robin Thomas, has also been applied to 4-critical graphs embeddable on a fixed surface. Dvorak, Kral, and Thomas proved that there are only finitely many 4-critical graphs of girth at least five on a fized surface. Thomas and Yerger also applied it to prove a weaker version of Steinberg's conjecture for surfaces. One last thing to note is that our concise discharging proof gives a new and much shorter proof of Thomassen's result. This follows since if 6-critical graphs have at most O(g) vertices there can be at most 2^O(g) 6-crtical graphs!

Results: We prove using discharging that a planar C-6-critical graph has at most O(|C|) vertices where G is critical with respect to an outer pre-colored cycle C. We then extend this result to an arbitrary number of cycles and arbitrary genus. The bound proved shows that a 6-critical graph on a surface S has at most O(g(S)) vertices where g(S) is the genus of S.

Conferences Attended

  1. New Trends in Structural Graph Theory, Sep 5-10, 2010, Banff, AB, Canada.
  2. Second Workshop on Graphs and Matroids, Aug 1-7, 2010, Maastricht, The Netherlands. Presented "Number of Vertices in a Six-Critical Graph is Linear in Genus" (Joint work with R. Thomas)
  3. SIAM DM 10, June 13-17, 2010, Austin, TX. Presented "Number of Vertices in a Six-Critical Graph is Linear in Genus" (Joint work with R. Thomas) in the Structural Graph Theory minisymposium
  4. Oberworlfach Workshop on Graph Theory, Feb 22-26, 2010, Germany.
  5. AMS Sectional Meeting, Oct 30-Nov 1, 2009, Boca Raton, FL. Presented "Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs" (Joint work with A.Asadi and R.Thomas)
  6. EuroComb '09, Sep 7-11, 2009, Bordeaux, France. Presented "Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs" (Joint work with A.Asadi and R.Thomas)
  7. DIMACS Workshop on Graph Coloring and Structure, May 7-11, 2009, Princeton, NJ.
  8. BIRS workshop on Graph Minors, Sep 28-Oct 3, 2008, Banff, Canada.
  9. Netherlands Workshop on Graphs and Matroids, Jul 19-22, 2008, Sittard, The Netherlands
  10. Topological and Geometric Graph Theory, May 19-23, 2008, Paris, France. Presented "Five-Coloring Graphs on the Klein Bottle" (Joint work with N. Chenette, N. Streib, R. Thomas, C. Yerger)
  11. 21st Cumberland Conference, May 15-17, 2008, Vanderbilt University, Nashville, TN. Presented "Five-Coloring Graphs on the Klein Bottle" (Joint work with N. Chenette, N. Streib, R. Thomas, C. Yerger)
  12. New Directions in Algorithms, Combinatorics, and Optimization, May 5-9, 2008, Georgia Tech, Atlanta, GA.
  13. ADONET-CIRM School on Graphs and Algorithms, Oct 22-26, 2007, Levico Terme, Italy.
  14. Fall School on Algorithmic Graph Structure Theory, Oct 4-7, 2007, Schloss Blankensee, Germany.

Links