Luke Postle

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

Contact Information:

Luke Postle
2735 Defoors Ferry Rd
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.

News

Awards and Fellowships

Publications and Manuscripts

Papers
  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), manuscript.
  3. Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs (with A. Asadi and R. Thomas), manuscript.
  4. Pebbling Graphs of Fixed Diameter, manuscript.
Extended Abstracts
  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), EuroComb 09, accepted.
  3. Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs (with A. Asadi and R. Thomas), EuroComb 09, accepted.

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 placee 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:

Results:

Sub-Exponentially Many 3-Colorings of Triangle-Free Plane Graphs
Objective: To prove that every triangle-free planar graph has exponenitially many 3-colorings.

Overview:

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

Conferences Attended

  1. 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)
  2. 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)
  3. DIMACS Workshop on Graph Coloring and Structure, May 7-11, 2009, Princeton, NJ.
  4. BIRS workshop on Graph Minors, Sep 28-Oct 3, 2008, Banff, Canada.
  5. Netherlands Workshop on Graphs and Matroids, Jul 19-22, 2008, Sittard, The Netherlands
  6. 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)
  7. 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)
  8. New Directions in Algorithms, Combinatorics, and Optimization, May 5-9, 2008, Georgia Tech, Atlanta, GA.
  9. ADONET-CIRM School on Graphs and Algorithms, Oct 22-26, 2007, Levico Terme, Italy.
  10. Fall School on Algorithmic Graph Structure Theory, Oct 4-7, 2007, Schloss Blankensee, Germany.

Curriculum Vitae

Coming Soon.

Links