Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-16T04:11:26.433Z Has data issue: false hasContentIssue false
  • English
  • Français

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
MICHELE MOSCA
Affiliation:
Mathematical Institute, University of Oxford, and Wolfson College, Oxford, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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
Combinatorics, Probability and Computing , Volume 7 , Issue 2 , June 1998 , pp. 211 - 216
Copyright
1998 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)