The canonical coloring graph of trees and cycles - Hass, Ruth (Ars mathematica contemporanea, 2012)
For a graph ?$G$? and an ordering of the vertices ?$π$?, the set of canonical ?$k$?-colorings of ?$G$? under ?$π$? is the set of non-isomorphic proper ?$k$?-colorings of ?$G$? that are lexicographically least under ?$π$?. The canonical coloring graph Can?$_k^π(G)$? is the graph with vertex set the canonical colorings of ?$G$? and two vertices are adjacent if the colorings differ in exactly one place. This is a natural variation of the color graph ?${\mathcal C}_k(G)$? where all colorings are considered. We show that every graph has a canonical coloring graph which is disconnected; that trees have canonical coloring graphs that are Hamiltonian; and cycles have canonical coloring graphs that are connected.
Keywords: barvanje grafov; canonical coloring; graph coloring; graph theory; kanonično barvanje; teorija grafov