Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Uvažuje se d-dimenzionální mříška s diagonálami, což je graf, jehož vrcholy jsou všechny d-tice se složkami z množiny {1,2,...,n} a dvě d-tice jsou spojené hranou, pokud se liší v každé složce nejvýš o 1. Dokazuje se, že pro každé obarvení vrcholů 2 barvami existuje souvislý jednobarevný podgraf s minimálně n^(d-1)-O(n^(d-2)) vrcholy, což je téměř nejlepší možný výsledek.
Podobný problém se řeší také pro grafy triangulovaných mřížek.