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

From VoWi
Jump to navigation Jump to search
Let G be an undirected simple graph and a subgraph of satisfying for some . What can be said about the relation between and ? Find a graph with which does not have a as a subgraph.

Solution[edit | edit source]

Since contains a sub-graph isomorph to the minimum number of colours needed to colour the whole graph is at least the number needed to colour . This means to colour we need at least colours:


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

TU Wien-Diskrete Mathematik für Informatik UE (Gittenberger)-Übungen WS13-Beispiel 37 - Exercise 37.png