The canonical coloring graph of trees and cycles
Haas, Ruth
ARS MATHEMATICA CONTEMPORANEA, Tome 4 (2011), / Harvested from ARS MATHEMATICA CONTEMPORANEA
link
link
link

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 Ck(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.

Publié le : 2011-01-01
DOI : https://doi.org/10.26493/1855-3974.168.464 
@article{168,
     title = {The canonical coloring graph of  trees and cycles},
     journal = {ARS MATHEMATICA CONTEMPORANEA},
     volume = {4},
     year = {2011},
     doi = {10.26493/1855-3974.168.464},
     language = {EN},
     url = {http://dml.mathdoc.fr/item/168}
}

Haas, Ruth. The canonical coloring graph of  trees and cycles. ARS MATHEMATICA CONTEMPORANEA, Tome 4 (2011) . doi : 10.26493/1855-3974.168.464. http://gdmltest.u-ga.fr/item/168/