„Girth” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
Nincs szerkesztési összefoglaló |
||
15. sor:
A Mycielski konstrukció segítségével tetszőlegesen nagy kromatikus számú gráfokat konstruálhatunk úgy, hogy a girth-paramé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 egyel megnő.
Az általánosabb állítást miszerint tetszőleges ''a'' és ''b''-re létezik ''a'' girth-paraméterű és ''b'' kromatikus számú gráf Erdős Pál bizonyította először a valószínűségi módszer segítségével.
==Források==
| |||