We study a simple Markov chain, known as the Glauber dynamics, for generating a random k-coloring of a n-vertex graph with maximum degree Δ. We prove that the dynamics converges to a random coloring after O(n log n) steps assuming k ≥ k₀ for some absolute constant k₀, and either: ... more >>>

The Tutte-Gr\"othendieck polynomial $T(G;x,y)$ of a graph $G$ encodes numerous interesting combinatorial quantities associated with the graph. Its evaluation in various points in the $(x,y)$ plane give the number of spanning forests of the graph, the number of its strongly connected orientations, the number of its proper $k$-colorings, the (all ... more >>>