Publikace na Matematicko-fyzikální fakulta |
2005
Abstrakt
Studujeme zobecnění problému barvení cest minimálním počtem barev: pro daný graf a množinu dvojic vrcholů chceme spojit každou dvojici k disjunktními cestami téže barvy; úkolem je minimalizovat počet použitých barev za podmínky, že cesty stejné barvy jsou hranově disjunktní. Základním problémem je hledání disjunktních cest mezi jednou dvojicí, problém úzce spjatý s Mengerovou větou.
Mengerova věta neříká nic o délce těchto cest; článek dává odhady na délku těchto cest.