Advanced Graph Theory and Combinatorics

7Colorings

In this chapter, we will be interested in coloring vertices of a graph in such a way that adjacent vertices receive distinct colors. This kind of coloring is a special case of homomorphisms of graphs. Hence, the first section briefly describes the latter notion. We conclude this chapter with the introduction of Ramsey numbers related to colorings of the edges of a complete graph.

7.1. Homomorphisms of graphs

The idea of a homomorphism from a digraph G to a digraph H is to consider a map f from V(G) to V(G) such that the image (f(u), f(v)) of every edge (u, v) in G by f is an edge in H. Recall that in the unoriented case, an edge {u, v} corresponds to two directed edges (u, v) and (v, u).

DEFINITION 7.1.– Let G, H be two digraphs. A homomorphism from G to H is a map f : V(G) → V(H) such that, for all u, v ∈ V(G), if (u, v) ∈ E(G), then (f(u), f(v)) ∈ E(H). For the particular case of undirected graphs, f is a homomorphism when for all u, v ∈ V(G), if {u, v} ∈ E(G), then {f(u), f(v)} ∈ E(H).

Considering the homomorphism 1 ↦ a, 2 ↦ b, 3 ↦ c, 4 ↦ c for the digraphs with V(G) = {1, 2, 3, 4} and V(H) = {a, b, c, d} depicted in Figure 7.1, we see that a homomorphism is not necessarily onto (surjective). If needed, we can restrict ourselves to the subgraph induced by the range of f (in our example, there is also a homomorphism from the first digraph to the subgraph induced by {a, b, c}.)

Figure 7.1. A homomorphism 1 ↦ a, 2 ↦ b, 3 ↦ c, 4 ↦ c

We have mentioned in example ...