О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “$2$-дистанционная раскраска разреженных плоских графов”, Сиб. электрон. матем. изв., 2004, том 1,страницы 76

Эта публикация цитируется в 21 статьях

Статьи

$2$-дистанционная раскраска разреженных плоских графов

О. В. Бородин^a, А. О. Иванова^b, Т. К. Неустроева^b

^a Институт математики им. С. Л. Соболева СО РАН
^b Якутский государственный университет им. М. К. Аммосова, Институт математики и информатики

Аннотация: Clearly, the 2-distance chromatic number $\chi_2(G)$ of any graph $G$ with maximum degree $\Delta$ is at least $\Delta+1$. We prove that if $G$ is planar and its girth is large enough (w.r.t. a fixed $\Delta$), then $\chi_2(G)=\Delta+1$.

УДК: 519.172.2

MSC: 05С15

Поступила 29 октября 2004 г., опубликована 16 ноября 2004 г.