Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Problém barvení druhé mocniny grafu přirozeně vzniká v souvislosti se vzdálenostními obarveními. Uvažujeme tento problém pro řídké subkubické grafy.
Ukážeme, že vybíravost $\chi_\ell(G^2)$ druhé mocniny subkubického grafu $G$ maximálního průměrného stupně $d$ je nejvýš 4 pokud $d [.lt.] 24/11$ a $G$ neobsahuje 5-cyklus, nejvýš 5 pokud $d [.lt.] 7/3$ a nejvýš 6 pokud $d [.lt.] 5/2$. Wegnerova hypotéza říká, že barevnost druhé mocniny subkubického rovinného grafu je nejvýš 7.
Nechť $G$ je rovinný graf obvodu $g$. Náš výsledek implikuje, že $\chi_\ell(G^2)$ je nejvýš 4 pokud $g\ge 24$, nejvýš 5, pokud $g\ge 14$, a nejvýš 6, pokud $g\ge 10$.
Pro dolní odhad najdeme rovinný subkubický graf $G_2$ obvodu 5 takový, že $\chi(G_2^2)=6$.