Graph Theory

  • notes on the Borodin-Kostochka conjecture (pdf)
  • Conjectures that should be true. (pdf)
Incomplete
  • Coloring graphs with Δ - 1 colors.
  • An improved Ore-type version of Brooks' theorem for list coloring.
  • An Alon-Tarsi version of Dirac's theorem on the number of edges in critical graphs
  • A fast parallel algorithm for edge-coloring extension. (abstract)
Under Review
  • The Hilton--Zhao Conjecture is True for Graphs with Maximum Degree 4 (with Dan Cranston (pdf)
  • A better lower bound on average degree of k-list-critical graphs.  (pdf)
  • Improved lower bounds on the number of edges in list critical and online list critical graphs. (with Hal Kierstead (pdf)
Finalized
  • Beyond Degree Choosability (with Dan CranstonElectron. J. Combin., Accepted. (pdf)
  • Planar graphs are 9/2-colorable. (with Dan CranstonJ. Combin. Theory Ser. B, Accepted. (pdf)
  • Short fans and the 5/6 bound for line graphs. (with Dan CranstonSIAM J. Discrete Math., Accepted. (pdf)
  • Extracting list colorings from large independent sets. (with Hal KiersteadJ. Graph Theory, Accepted. (pdf)
  • Subcubic edge chromatic critical graphs have many edges (with Dan CranstonJ. Graph Theory, Accepted. (pdf)
  • List-coloring claw-free graphs with Δ - 1 colors. SIAM J. Discrete Math., Accepted. (with Dan Cranston (pdf)
  • Edge Lower Bounds for List Critical Graphs, via Discharging.  Combinatorica, Accepted. (with Dan Cranston(pdf)
  • A better lower bound on average degree of 4-list-critical graphs.  Electron. J. Combin., Accepted. (pdf) (ejc)
  • Planar graphs have independence ratio at least 3/13 (with Dan CranstonElectron. J. Combin., Accepted. (pdf)
  • Painting squares in Δ^2 - 1 shades. (with Dan Cranston Electron. J. Combin.,  Volume 23(2), 2016. (pdf)
  • Stiebitz's proof of Gallai's conjecture on the number of components in the high and low vertex subgraphs of critical graphs.  (pdf)
  • The union of a forest and a star forest is 3-colorable. (pdf)
  • The combinatorial nullstellensatz and Schauz's coefficient formula. (pdf)
  •  Haxell's independent transversal lemma (pdf)
  • Graphs with χ = Δ have big cliques. (with Dan CranstonSIAM J. Discrete Math., 29(4), 1792–1814.  (pdf) (doi) 
  • The fractional chromatic number of the plane. (with Dan CranstonCombinatorica, Accepted. (pdf)
  • A note on coloring vertex-transitive graphs.  (with Dan CranstonElectron. J. Combin.Volume 22(2), 2015. (pdf)
  • Conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker. (with Dan CranstonEuropean J. Combinatorics., Volume 44, Part A, February 2015, Pages 23–42 (pdf) (doi) 
  • The list-chromatic index of K_8 and K_10.  (pdf)
  • Yet another proof of Brooks' theorem.  (pdf)
  • A game generalizing Hall's Theorem. Discrete Math., 320(6):87-91, 2014.  (pdf) (doi)  
  • Coloring graphs with dense neighborhoods. J. Graph Theory,  76(4):323-340, 2014. (pdf) (doi) 
  • Coloring graphs from almost maximum degree sized 
  • palettes.
  • Dissertation. (pdf)
  • Partitioning and coloring graphs with degree constraints. Discrete Math., 313(9):1028-1034, 2013. (pdf) (doi)  
  • A different short proof of Brooks' theorem. Discuss. Math. Graph Theory,  34(3), 2014. (pdf) (shorter) (shortest)
  • Coloring claw-free graphs with Δ - 1 colors. (with Dan Cranston) SIAM J. Discrete Math., 27(1):534-549, 2013. (pdf) (doi)
  • A note on vertex partitions. (pdf)
  • Destroying non-complete regular components in graph partitions. J. Graph Theory, 72(2):123-127, 2013. (pdf(doi)
  • A strengthening of Brooks' Theorem for line graphs. Electron. J. Combin.N145, Volume 18(1), 2011(pdf)
  • Δ-Critical graphs with small high vertex cliques. J. Combin. Theory Ser. B,  102(1):126-130, 2012.  (pdf(doi)

  • On hitting all maximum cliques with an independent set.   J. Graph Theory, 66(1):32-37, 2011. (pdf(doi)

  • The Borodin-Kostochka conjecture for graphs containing a doubly critical edge.  Electron. J. Combin., N22, Volume 14(1), 2007. (pdf)

     

  • A note on Reed’s conjecture. SIAM J. Discrete Math., 22(2):820-827, 2008. (pdf(doi)

  • On graph associations. SIAM J. Discrete Math., 20(2):529–535, 2006. (pdf (doi)

Unclassified 
  • A similar shorter proof of Brooks' theorem. (pdf) (for list coloring)
  • Dissertation prospectus. (pdf)
  • Playing cards with Vizing's demon. (pdf)
  • An improvement on Brooks' Theorem. (pdf)