8 citations · 11 across the 8 of their papers we have counts for
19 papers · 1 filter
Five-List-Coloring Graphs on Surfaces: The Many Faces Far-Apart Generalization of Thomassen's Theorem
Luke Postle, Robin Thomas
Let be a plane graph with the boundary of the outer face and let be a family of non-empty sets. By an -coloring of a subgraph of we mean a (pr…
Triangle-free planar graphs with at most 3-colorings
Zdeněk Dvořák, Luke Postle
Thomassen conjectured that triangle-free planar graphs have exponentially many 3-colorings. Recently, he disproved his conjecture by providing examples of such graphs with vert…
Structure in sparse -critical graphs
Ron Gould, Victor Larsen, Luke Postle
Recently, Kostochka and Yancey proved that a conjecture of Ore is asymptotically true by showing that every -critical graph satisfies $|E(G)|\geq\left\lceil\left(\frac{k}{2}-\fr…
Further Progress towards the List and Odd Versions of Hadwiger's Conjecture
Luke Postle
In 1943, Hadwiger conjectured that every graph with no minor is -colorable for every . In the 1980s, Kostochka and Thomason independently proved that every gra…
On decidability of hyperbolicity
Zdeněk Dvořák, Luke Postle
We prove that a wide range of coloring problems in graphs on surfaces can be resolved by inspecting a finite number of configurations.
Fractional vertex-arboricity of planar graphs
Marthe Bonamy, František Kardoš, Tom Kelly +1
We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of…