0 KB250 KB24 KB200820252012Hass, Ruthštevilka:1letnik:5str. 149-157COBISSID:16272985ISSN:1855-3966URN:URN:NBN:SI:doc-E1NDPMMFenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneabarvanje grafovcanonical coloringgraph coloringgraph theorykanonično barvanjeteorija grafovThe canonical coloring graph of trees and cycles|For a graph ?$G$? and an ordering of the vertices ?$\pi$?, the set of canonical ?$k$?-colorings of ?$G$? under ?$\pi$? is the set of non-isomorphic proper ?$k$?-colorings of ?$G$? that are lexicographically least under ?$\pi$?. The canonical coloring graph Can?$_k^\pi(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 connectedTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije