G. Perarnau

activity

20112026

most citedLarge subgraphs without short cycles

22 citations · 112 across the 37 of their papers we have counts for

collaborators

Showing 2018 · cs.DSShow all

2 papers · 2 filters

cs.DS2018

The Glauber dynamics for edge-colourings of trees

Michelle Delcourt, Marc Heinrich, Guillem Perarnau

Let $T$ be a tree on $n$ vertices and with maximum degree $Δ$ . We show that for $k \geq Δ + 1$ the Glauber dynamics for $k$ -edge-colourings of $T$ mixes in polynomial time in $n$ . The…

cs.DS2018★ 2 cited

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 $k$ -colorings of a graph $G$ on $n$ vertices with maximum degree $Δ$ is r…