Gray code numbers for graphs - Choo, Kelly (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.
Keywords: barvanje grafov; ciklična Grayjeva koda; cyclic Gray code; graph colouring; graph theory; teorija grafov