Graph Homomorphism - Connection To Coloring and Girth

Connection To Coloring and Girth

A graph coloring is an assignment of one of k colors to a graph G so that the endpoints of each edge have different colors, for some number k. Any coloring corresponds to a homomorphism from G to a complete graph K_k: the vertices of K_k correspond to the colors of G, and f maps each vertex of G with color c to the vertex of K_k that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of K_k, and every two distinct vertices of K_k are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in K_k. Conversely if f is a homomorphism from G to K_k, then one can color G by using the same color for two vertices in G whenever they are both mapped to the same vertex in K_k. Because K_k has no edges that connect a vertex to itself, it is not possible for two adjacent vertices in G to both be mapped to the same vertex in K_k, so this gives a valid coloring. That is, G has a k-coloring if and only if it has a homomorphism to K_k.

If there are two homomorphisms, then their composition is also a homomorphism. In other words, if a graph G can be colored with k colors, and there is a homomorphism, then H can also be k-colored. Therefore, whenever a homomorphism exists, the chromatic number of H is less than or equal to the chromatic number of G.

Homomorphisms can also be used very similarly to characterize the odd girth of a graph G, the length of its shortest odd-length cycle. The odd girth is, equivalently, the smallest odd number g for which there exists a homomorphism . For this reason, if, then the odd girth of G is greater than or equal to the corresponding invariant of H.