Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Pro graf G definujeme mcc(t,G) jako nejmenší číslo m takové, že existuje obarvení vrcholů G pomocí t barev takové, že žádný souvislý jednobarevný podgraf nemá víc než m vrcholů. Pro různé třídy grafů se zkoumá maximum mcc(2,G) přes všechny n=vrcholové grafy z příslušné třídy.
Například se dokazuje, že pro rovinné grafy je toto maximum řádu n na 2/3.