Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T08:57:38.212Z Has data issue: false hasContentIssue false

Removing Edges Can Increase the Average Number of Colours in the Colourings of a Graph

Published online by Cambridge University Press:  01 June 1998

MICHELE MOSCA
Affiliation:
Mathematical Institute, University of Oxford, and Wolfson College, Oxford, UK (e-mail: mosca@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
1998 Cambridge University Press