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.^[1]

Vlastnosti degenerovaného grafu editovat

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

Reference editovat

↑ HLINĚNÝ, Petr. Barevnost a další těžké problémy [online]. Brno: [cit. 2016-10-27]. S. 6. Dostupné v archivu pořízeném dne 2016-10-27.
↑ Shuji Isobe; Xiao Zhou; Takao Nishizeki. Total Colorings of degenerate graphs [online]. [cit. 2016-10-27]. Kapitola Introduction, s. 6. Dostupné v archivu pořízeném dne 2016-10-27.

Externí odkazy editovat

Obrázky, zvuky či videa k tématu Degenerovaný graf na Wikimedia Commons

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

[1] HLINĚNÝ, Petr. Barevnost a další těžké problémy [online]. Brno: [cit. 2016-10-27]. S. 6. Dostupné v archivu pořízeném dne 2016-10-27.

[2] Shuji Isobe; Xiao Zhou; Takao Nishizeki. Total Colorings of degenerate graphs [online]. [cit. 2016-10-27]. Kapitola Introduction, s. 6. Dostupné v archivu pořízeném dne 2016-10-27.

[1]

[2]