Dr. Luke Postle

HOME             CV             Publications             Presentations             Students             Teaching             Service            

PhD Thesis: 5-List-Coloring Graphs on Surfaces

Journal Publications

  1. T. Kelly, L. Postle. A Local Epsilon Version of Reed's Conjecture. Journal of Combinatorial Theory Ser. B., Volume 141, March 2020, pp. 181--222.
  2. M. Faron, L. Postle. On the clique number of the square of a line graph and its relation to Ore-degree. Journal of Graph Theory, Volume 92 (3), November 2019, pp. 261--274.
  3. Z. Dvorak, S. Norin, L. Postle. List coloring with requests. Journal of Graph Theory, Volume 92 (3), November 2019, pp. 191--206.
  4. M. Bonamy, F. Kardos, T. Kelly, P. Nelson, L. Postle. The structure of binary matroids with no induced claw or Fano plane restriction. Advances in Combinatorics, October 2019, https://doi.org/10.19086/aic.10256
  5. M. Merker, L. Postle. Bounded Diameter Arboricity. Journal of Graph Theory, Volume 90 (4), April 2019, pp. 629--641.
  6. M. Bonamy, D. Cranston, L. Postle. Planar graphs of girth at least five are Square $(\Delta+2)$-Choosable. Journal of Combinatorial Theory Ser. B, Volume 134, January 2019, pp. 218--238.
  7. L. Postle, R. Thomas. Hyperbolic families and coloring graphs on surfaces. Transactions of the American Mathematical Society Series B 5 (2018), pp. 167--221.
  8. M. Delcourt, L. Postle. Random 4-regular graphs have 3-star decompositions asymptotically almost surely. European Journal of Combinatorics, Volume 72, August 2018, pp. 97--111.
  9. G. Chen, Y. Gao, R. Kim, L. Postle, S. Shan. Chromatic index determined by fractional chromatic index. Journal of Combinatorial Theory Ser. B, Volume 131, July 2018, pp. 85--108.
  10. L. Postle. Characterizing 4-Critical Graphs of Ore-degree at Most Seven, Journal of Combinatorial Theory Ser. B, Volume 129, March 2018, pp. 107--147.
  11. Z. Dvorak, L. Postle. Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, Journal of Combinatorial Theory Ser. B, Volume 129, March 2018, pp. 38--54.
  12. T. Kelly, L. Postle. Exponentially Many 4-List-Colorings of Triangle-Free Graphs on Surfaces, Journal of Graph Theory, Volume 87 (2), February 2018, pp. 230--238.
  13. L. Postle, R. Thomas. 5-List-Colouring Graphs on Surfaces III: One List of Size One and One List of Size Two, Journal of Combinatorial Theory Ser. B, Volume 128, January 2018, pp. 1--16.
  14. N. Bowler, J. Carmesin, L. Postle. Reconstruction of infinite matroids from their 3-connected minors, European Journal of Combinatorics Volume 67, January 2018, pp. 126--144.
  15. L. Postle, On the Minimum Number of Edges in Triangle-Free 5-Critical Graphs, European Journal of Combinatorics, Volume 66, December 2017, pp. 264--280.
  16. C. Liu, L. Postle. On the Minimum Edge-Density of 4-Critical Graphs of Girth Five, Journal of Graph Theory, Volume 86, Issue 4, December 2017, pp. 387--405.
  17. Z. Dvorak, L. Postle. Density of 5/2-critical graphs, Combinatorica, Volume 37 (5), October 2017, pp. 863--886.
  18. Z. Dvorak, B. Lidicky, B. Mohar, L. Postle. 5-list-Coloring Planar Graphs with Distant Precolored Vertices, Journal of Combinatorial Theory Ser. B, Volume 122, January 2017, pp. 311--352.
  19. D. Cranston, L. Postle, C. Xue, C. Yerger. Modified linear programming and class 0 bounds for graph pebbling, Journal of Combinatorial Optimization, July 2016, pp. 1--19.
  20. L. Postle, R. Thomas. 5-List-Colouring Graphs on Surfaces II: A linear bound for critical graphs in a disk, Journal of Combinatorial Theory Ser. B, Volume 119, July 2016, pp. 42--65. arXiv:1505.05927
  21. L. Postle, R. Thomas. 5-List-Colouring Graphs on Surfaces I: Two with lists of size Two Theorem, Journal of Combinatorial Theory Ser. B, Volume 111, March 2015, pp. 234--241.
  22. E. Aigner-Horev, R. Diestel, L. Postle. The structure of 2-separations of infinite matroids, Journal of Combinatorial Theory, Ser. B, Volume 116, January 2016, pp. 25--56. [math.CO]
  23. L. Postle. Pebbling Graphs of Fixed Diameter, Journal of Graph Theory, Volume 75, Issue 4, April 2014, pp.302--310.
  24. A. Asadi, Z. Dvorak, L. Postle, R. Thomas. Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs. Journal of Combinatorial Theory, Ser. B, Volume 103, Issue 6, November 2013, pp.706--712.
  25. L. Postle, N. Streib, C. Yerger. Pebbling Graphs of Diameter Three and Four. Journal of Graph Theory, Volume 72, Issue 4, April 2013, pp.398--417.
  26. N. Chenette, L. Postle, N. Streib, R. Thomas, C. Yerger. Five-Coloring Graphs on the Klein Bottle. Journal of Combinatorial Theory, Ser. B, Volume 102, Issue 5, September 2012, pp. 1067--1098.

Conference Publications

  1. L. Postle, Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 929--941.
  2. L. Postle, E. Smith-Roberge, On the Density of $C_7$-critical graphs, Acta Mathematica Universitatis Comenianae, 88(3), 1009--1016.
  3. M. Bonamy, M. Delcourt, R. Lang, L. Postle, Asymptotically Good Local List Edge Colourings, accepted, Acta Mathematica Universitatis Comenianae, 88(3), 489--494.
  4. S. Chen, M. Delcourt, A. Moitra, G. Perarnau, L. Postle. Improved Bounds for Randomly Sampling Colorings via Linear Programming. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), 2216--2234.
  5. M. Delcourt, L. Postle. On Star Decomposition of Random Regular Graphs. Electronic Notes in Discrete Mathematics, Volume 61 (Eurocomb 2017 conference proceedings), pp. 339--342.
  6. M. Delcourt, L. Postle. On the List Coloring Version of Reed's Conjecture. Electronic Notes in Discrete Mathematics, Volume 61 (Eurocomb 2017 conference proceedings), pp. 343--349.
  7. T. Kelly, L. Postle. A Local Epsilon Version of Reed's Conjecture. Electronic Notes in Discrete Mathematics, Volume 61 (Eurocomb 2017 conference proceedings), pp. 719-725.
  8. On the Minimum Edge-Density of 5-Critical Triangle-Free Graphs, Electronic Notes in Discrete Mathematics 49 (2015), 667--673.
  9. Minor-Minimal Non-Projective Planar Graphs with an Internal 3-Separation (with A. Asadi and R. Thomas.), Electronic Notes in Discrete Mathematics 38 (2011), 69--75.
  10. Decomposing Infinite Matroids into their 3-Connected Minors (with E. Aigner- Horev and R. Diestel), Electronic Notes in Discrete Mathematics 38 (2011), 11--16.
  11. Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs (with A. Asadi and R. Thomas), Electronic Notes in Discrete Mathematics 34 (2009), 81--87.
  12. Pebbling Graphs of Diameter Three and Four (with N. Streib and C. Yerger), Electronic Notes in Discrete Mathematics 34 (2009), 21--28.
  13. Six-critical graphs 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.