Article contents
Removing Edges Can Increase the Average Number of Colours in the Colourings of a Graph
Published online by Cambridge University Press: 01 June 1998
Abstract
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.
- Type
- Research Article
- Information
- Copyright
- 1998 Cambridge University Press
- 3
- Cited by