Graph/Färbung/Einfache Eigenschaften/Fakt

Für die chromatische Zahl ${}\chi (G)$ eines Graphen ${}G=(V,E)$ gelten die folgenden Aussagen.

Ein Graph ist genau dann nicht leer, wenn seine chromatische Zahl ${}\geq 1$ ist.

Ein nichtleerer Graph besitzt genau dann die chromatische Zahl ${}1$ , wenn er keine Kanten besitzt.

Ein Graph ist genau dann bipartit, wenn seine chromatische Zahl ${}\leq 2$ ist.

Es ist
${}\chi (G)\leq {\#\left(V\right)}\,.$

Der vollständige Graph ${}K_{n}$ besitzt die chromatische Zahl ${}n$ .

Einen Beweis erstellen

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.