Let G be a simple, connected and undirected graph. Let r; k be natural numbers. By a proper k-coloring of a graph G, we mean a map c : V (G) ! S, where jSj = k, such that any two adjacent vertices receive di erent colors. ...