Abstrakt
Injektivní barvení grafu je takové obarvení jeho vrcholů, že vrcholy ve vzdálenosti 2 mají různou barvu. V článku jsou ukázány výsledky o obarvování rovinných grafů pomocí malého počtu barev.
Ukazujeme, že rovinné grafy s maximálním stupněm \Delta a obvodem alespoň 19 jsou injektivně \Delta-obarvitelné. Podobně, obvod alespoň 10 implikuje (\Delta 1)-obarvitelnost, obvod alespoň 5 implikuje (\Delta 4)-obarvitelnost, pokud \Delta je dostatečně velké, a obvod alespoň 7 implikuje 5-obarvitelnost subkubických rovinných grafů.