Кп соответствует n - раскраске графа G, поскольку вершины графа Кп можно рассматривать как цвета и по определению гомоморфизма ни одна пара вершин графа G с одинаковым цветом не смежна. Любая раскраска, определенная полным гомоморфизмом, обладает тем свойством, что для любых двух цветов в графе G найдутся смежные вершины и и v, окрашенные в эти цвета. В данном случае мы получаем полную раскраску. На рис. 12.12 показан граф с полными раскрасками порядков 3 и 4; цвета указаны здесь положительными целыми числами.
