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]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/08/2-degenerate_graph_2-core.svg/220px-2-degenerate_graph_2-core.svg.png)
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