TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 37

Let G be an undirected simple graph and $H$ a subgraph of $G$ satisfying $H\cong K_{n}$ for some $n$. What can be said about the relation between $\chi (G)$ and $\chi (H)$? Find a graph $G$ with $\chi (G)=3$ which does not have a $K_{3}$ as a subgraph.

Solution

Since $G$ contains a sub-graph $H$ isomorph to $K_{n}$ the minimum number of colours needed to colour the whole graph is at least the number needed to colour $H$. This means to colour $G$ we need at least $n$ colours:

   $\chi (G)\geq \chi (H)=n$

The figure below shows a three-colourable graph, which does not contain $K_{3}$.

Attachments

Add new attachment

E

• Exercise 37.png (details)