Degenerovaný graf

2-degenerovaný graf Degenerovaný graf nebo k-degenerovaný graf je v teorii grafů graf, jehož každý podgraf obsahuje alespoň jeden vrchol stupně nejvýše k.

Vlastnosti degenerovaného grafu

chromatické číslo k-degenerovaného grafu je nejvýše k + 1

Reference

Externí odkazy

Kategorie:Grafové pojmy