On the phase transitions of graph coloring and independent sets

V. C. Barbosa, R. G. Ferreira

We study combinatorial indicators related to the characteristic phase transitions associated with coloring a graph optimally and finding a maximum independent set. In particular, w…