The mean chromatic number of paths and cycles (Q687131)

The mean chromatic number of a graph \(G\) on \(n\) vertices is defined to be \[ \overline\chi(G)= {1\over n!} \sum\chi(G,\sigma), \] where the sum is over all orderings of the vertex set of \(G\), and \(\chi(G,\sigma)\) is the number of colours used by the greedy algorithm to colour \(G\) with respect to the ordering \(\sigma\). Using generating function techniques, asymptotic expressions are obtained for the mean chromatic numbers of the paths and even cycles.