13 citations · 115 across the 49 of their papers we have counts for
4 papers · 2 filters
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…
Characterizing 4-Critical Graphs of Ore-Degree at most Seven
Luke Postle
Dirac introduced the notion of a k-critical graph, a graph that is not (k-1)-colorable but whose every proper subgraph is (k-1)-colorable. Brook's Theorem states that every graph w…
Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs
Luke Postle, Robin Thomas
Let G be a plane graph with outer cycle C, let u,v be vertices of C and let (L(x):x in V(G)) be a family of sets such that |L(u)|=|L(v)|=2, L(x) has at least three elements for eve…