What is ℕ⌄k for k in ℕ?
ℕ⌄k is the set {1, 2, …, k}, i.e., all natural numbers from 1 up to k inclusive.
What is a k-colouring of a graph G?
A function f: V(G) → ℕ⌄k is a k-colouring of G if and only if for all u, v in V(G), whenever {u, v} is an edge of G, we have f(u) ≠ f(v).
What does ℋ⌄k(G) represent for a graph G and k in ℕ?
ℋ⌄k(G) is the set of all k-colourings of G.
What is the relationship between ℋ⌄k(G) and Fun(V(G), ℕ⌄k)?
ℋ⌄k(G) is a subset of Fun(V(G), ℕ⌄k); that is, every k-colouring is a function V(G) → ℕ⌄k, but not every such function is a valid colouring.
When is a graph G called k-colourable?
G is k-colourable if and only if ℋ⌄k(G) ≠ ∅, meaning there exists at least one valid k-colouring of G.
How do you read the notation “f : V(G) → ℕ⌄n ; vᵢ ↦ i”?
It means f is a function from V(G) to ℕ⌄n, and the rule vᵢ ↦ i tells you how it acts: each vertex vᵢ is mapped to the number i (i.e., f(vᵢ) = i).
What is the chromatic number χ(G) of a graph G?
χ(G) is the smallest natural number k for which G is k-colourable. In other words, χ(G) = min { k in ℕ : ℋ⌄k(G) ≠ ∅ }.
