Gray code numbers for graphs
Kelly Choo, Gary MacGillivray · Ars Mathematica Contemporanea · 2011
A graph H has a Gray code of k -colourings if it is possible to list all of its k -colourings in such a way that consecutive elements in the list differ in the colour of exactly one vertex. We prove that for any graph H , there is a least integer k 0 ( H ) such that H has a Gray code of k -colourings whenever k ≥ k 0 ( H ). We then determine k 0 ( H ) whenever H is a complete graph, tree, or cycle.