3 papers
math.CO2014
Density of 5/2-critical graphs
Zdenek Dvorak, Luke Postle
A graph G is 5/2-critical if G has no circular 5/2-coloring (or equivalently, homomorphism to C_5), but every proper subgraph of G has one. We prove that every 5/2-critical graph o…
math.CO2014
On the Minimum Edge-Density of 4-Critical Graphs of Girth Five
Chun-Hung Liu, Luke Postle
We prove that if G is a 4-critical graph of girth at least five then |E(G)|>=(5|V(G)|+2)/3. As a corollary, graphs of girth at least five embeddable in the Klein bottle or torus ar…
math.CO2010
Sub-exponentially many 3-colorings of triangle-free planar graphs
Arash Asadi, Zdenek Dvorak, Luke Postle +1
Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least 2^[n^(1/12)/20000] distinct 3-coloring…