O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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, vV(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, vV(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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required