Question

4. The following graph is called the Hajós graph. What is its chromatic number?

Discrete mathematics and cryptography: specifically graph theory.

Please show working

Answer 1

N The Chromatic number of a graph is the minimum number of cDlors needed to produce a proper coloring of the grapho red Iblue blue a blue e green Let us name the verliess of the graph as shown above. Now, we find the chromatic number of the graph as follow- • Assign red colour to the vertex a. Now, assign blue color to the adjacent vertices of a i.C., b and g. Note that b and g must not be adjacent. • Now, again assign red colour to c and f and C and f are not adjacent and also C¢f are not adiacent to ao • Now, assign blue color to d as it is not adjacent to any vertex of blue color. • Now, assign green color to e. since, we used three colors to color the graph. so, chromatic number of graph is 3. ar