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)\ge \chi (H)=n$

The figure below shows a three-colourable graph, which does not contain $K_3$.

Materialien

Neues Material hinzufügen

E

• Exercise 37.png (details)