Section 5: Graph colouring

Question 1

We are interested in assigning colours to the vertices of a graph, so that no two adjacent vertices can receive the same colour. A colouring of the vertices of a graph G that satisfies this rule is called
a

Answer 1

proper colouring of G

Question 2

If there exists a proper
k-colouring of G, we say that G is

Answer 2

k-colourable

Question 3

The _______ of G is the smallest natural number k such that G is k-colourable

Answer 3

chromatic number

Question 4

If H is a subgraph of G, and H has chromatic number at least k, then G ________.

Answer 4

also has chromatic number at least k

Question 5

The complete graph on n vertices, Kn, has chromatic number _________.

Answer 5

n (every vertex must receive a different colour)

Question 6

the _______ _______ of G is the largest natural number t such that K_t
is a subgraph of G

Answer 6

clique number

Question 7

t the chromatic number of a graph G is at least the _______ _______ of G

Answer 7

clique number

Question 8

In general, if C_t
is a cycle on t vertices, where t is odd, we need ____ colours to properly colour C_t

Answer 8

three

Question 9

If we have a proper
colouring of a graph G, and all the vertices of U ⊆ G receive the same colour, then there cannot be an edge between any two vertices of U.
A set like this, which does not induce any edges in G, is called an _____ ____

Answer 9

independent set

Question 10

the number of vertices in the largest independent
set in G is called the ______ ______ of G

Answer 10

independence number

Question 11

The number of vertices that receives any one colour in a proper colouring of G is at most the ____ _____ of G

Answer 11

independence number

Question 12

independence number of G × chromatic number of G ≥ _____.

Answer 12

|G|

Question 13

Theorem 5.1. Let G be a graph with n vertices and independence number α. Then the chromatic number of G is at least ____.

Answer 13

n/α

Question 14

a _____ _______ is one which makes the best short-term decision, without considering the long-term consequences of this decision

Answer 14

greedy algorithm

Question 15

The greedy
algorithm for colouring a graph is as follows:
a) ______
b) Colour the vertices in this order, each time choosing the
first colour that has not already been used on a neighbour of the vertex being considered.

Answer 15

List the vertices of G in some order.

Question 16

The greedy
algorithm for colouring a graph is as follows:
a) List the vertices of G in some order.
b) __________

Answer 16

Colour the vertices in this order, each time choosing the first colour that has not already been used on a neighbour of the vertex being considered.

Question 17

Lemma 5.2. Let G be a graph with maximum degree d. Then the chromatic number of G is at most _____

Answer 17

d + 1