„Girth” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
FoBe (vitalap | szerkesztései) →Példák: enwikiből import példák |
Syp (vitalap | szerkesztései) |
||
20. sor:
== A girthparaméter és a [[kromatikus szám]] kapcsolata ==
Ha egy gráf girthparamétere nagyobb, mint 3, akkor a gráf [[háromszögmentes gráf|háromszögmentes]].
A [[Mycielski-konstrukció]] segítségével tetszőlegesen nagy kromatikus számú gráfokat konstruálhatunk úgy, hogy a girthparaméterük nagyobb marad, mint 3, mivel ha eredetileg egy háromszögmentes gráfból indulunk ki, akkor a Mycielski-konstrukció utáni gráfunk is háromszögmentes lesz, de a kromatikus száma eggyel megnő.
| |||