CDAM Research Report, LSE-CDAM-2007-31
Finding Paths Between 3-Colourings
Luis Cereceda, Jan van den Heuvel, and Matthew JohnsonGiven a 3-colourable graph G and two proper vertex 3-colourings α and β of G, consider the following question: is it possible to transform α into β by recolouring vertices of G one at a time, making sure that all intermediate colourings are proper 3-colourings?
A PDF file (227 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-31, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
|Introduction to the CDAM Research Report Series.|