The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic ...

Question

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

[Graph: A wheel-like graph with 8 outer vertices arranged in a ring, each adjacent to its two ring-neighbours; the ring alternates connections forming even cycles with no additional chords that force odd cycles.]

Accepted Answer

2 The chromatic number is the fewest colours needed so that no two adjacent vertices share a colour. If a graph contains no odd-length cycle, it is bipartite and needs exactly 2 colours (assuming it has at least one edge). We check whether the given graph has an odd cycle to determine whether 2 or more colours suffice.