Una coloración de un grafo con colores es con respecto a un orden de los vértices si los vértices adyacentes se les asignan colores diferentes y, para , siempre que se asigne un color a un vértice , cada color menor que ha sido asignado a un vértice que precede en . El es el grafo con conjunto de vértices igual al conjunto de coloraciones canónicas de con respecto a , con dos de éstas siendo adyacentes si y solo si difieren en el color asignado a exactamente un vértice. Se estudia la conectividad y la Hamiltonicidad de los grafos de coloración canónica de grafos bipartitos y completos multipartitos. Se muestra que para grafos completos multipartitos y bipartitos existe un orden de vértices tal que es conectado para valores suficientemente grandes de . Se demuestra que un grafo de coloración canónica de un grafo completo multipartito generalmente no tiene un ciclo de Hamilton, y que existe un orden de vértices tal que tiene un camino de Hamilton para todos . El documento concluye con una consideración detallada de . Para cada y todos los órdenes de vértices , se demuestra que es o bien desconectado o isomorfo a un árbol en particular.