Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Nechť $G$ je graf a nechť $c: V(G)\to\binom{[5]}{2}$ je přiřazení dvouprvkových podmnožin množiny $[5]$ vrcholům $G$ tak, že pro každou hranu $vw$ jsou množiny $c(v)$ a $c(w)$ disjunktní. Takové přiřazení nazveme {\em (5,2)-obarvení}.
Graf je $(5,2)$-obarvitelný, právě když má homomorfismus do Petersenova grafu. {\em Lichý obvod} grafu $G$ je délka nejkratšího lichého cyklu (nebo $\infty$ když $G$ je bipartitní). Ukážeme, že každý rovinný graf lichého obvodu aspoň 9 je (5,2)-obarvitelný, a tudíž má homomorfismus do Petersenova grafu.
Z toho také plyne, že takové grafy mají zlomkovou barevnost nejvýš $5/2$. Speciálně se tento výsledek vztahuje na rovinné grafy s obvodem aspoň 8.