1 citations · 1 across the 9 of their papers we have counts for
6 papers · 1 filter
Exponentially Many Correspondence Colourings of Planar and Locally Planar Graphs
Luke Postle, Evelyne Smith-Roberge
We show that there exists a constant such that if is a planar graph with 5-correspondence assignment , then has at least distinct -c…
Hyperbolicity Theorems for Correspondence Colouring
Luke Postle, Evelyne Smith-Roberge
We generalize a framework of list colouring results to correspondence colouring. Correspondence colouring is a generalization of list colouring wherein we localize the meaning of t…
Five-list-coloring graphs on surfaces III. One list of size one and one list of size two
Luke Postle, Robin Thomas
Let be a plane graph with outer cycle and let be a family of non-empty sets. By an -coloring of we mean a (proper) coloring of such that $…
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…
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…
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…