Removing Edges Can Increase the Average Number of Colours in the Colourings of a Graph
Michele Mosca · Combinatorics Probability Computing · 1998
It was conjectured by Bartels and Welsh [1] that removing an edge from an n-vertex graph G will not increase the average number of colours in the proper colourings of G if k=n colours are available. This paper shows that for all n>3, and for each k∈{3, 4, …, [lfloor ](3n−6)/2[rfloor ]}, there is a graph on n vertices with an edge whose removal increases the average number of colours in the k-colourings, thus disproving the conjecture.