8 citations · 11 across the 9 of their papers we have counts for
6 papers · 1 filter
On the Minimal Edge Density of -free 6-critical Graphs
Wenbo Gao, Luke Postle
Kostochka and Yancey resolved a famous conjecture of Ore on the asymptotic density of -critical graphs by proving that every -critical graph satisfies $|E(G)| \geq (\frac…
Improved Bounds for Randomly Sampling Colorings via Linear Programming
Sitan Chen, Michelle Delcourt, Ankur Moitra +2
A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of -colorings of a graph on vertices with maximum degree is r…
Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications
Marthe Bonamy, Thomas Perrett, Luke Postle
Let be a graph with chromatic number , maximum degree and clique number . Reed's conjecture states that for…
The structure of binary matroids with no induced claw or Fano plane restriction
Marthe Bonamy, Frantisek Kardos, Tom Kelly +2
An 'induced restriction' of a simple binary matroid is a restriction , where is a flat of . We consider the class of all simple binary matroids co…
Rapid mixing of Glauber dynamics for colorings below Vigoda's threshold
Michelle Delcourt, Guillem Perarnau, Luke Postle
A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of -colorings of a graph on vertices with maximum degree is r…
Bounding by a fraction of for graphs without large cliques
Marthe Bonamy, Tom Kelly, Peter Nelson +1
The greedy coloring algorithm shows that a graph of maximum degree at most has chromatic number at most , and this is tight for cliques. Much attention has been devoted t…