Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree

A packing of graphs $G_1$ and $G_2$, both on $n$ vertices, is a set $\{H_1,H_2\}$ such that $H_1\cong G_1$, $H_2\cong G_2$, and $H_1$ and $H_2$ are edge disjoint subgraphs of $K_n$. In 1978, Sauer and Spencer [J. Combin. Theory Ser. B, 25 (1978), pp. 295--...

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 0(n log n) steps assuming k k_0 for some absolute ...

We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints and apply this method in various scenarios. We establish a formula that generates a general upper bound for ...