Gray code numbers for graphs

Authors

  • Kelly Choo University of Victoria, Canada
  • Gary MacGillivray University of Victoria, Canada

DOI:

https://doi.org/10.26493/1855-3974.196.0df

Keywords:

graph colouring, cyclic Gray code

Abstract

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 k0(H) such that H has a Gray code of k-colourings whenever k ≥ k0(H). We then determine k0(H) whenever H is a complete graph, tree, or cycle.

Downloads

Published

2023-03-27

Issue

Vol. 4 No. 1 (2011)

Section

Articles

License

Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/