RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2004, том 1, страницы 129–141 (Mi semr12)

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

Статьи

Достаточные условия $2$-дистанционной $\Delta+1$ раскрашиваемости плоских графов

О. В. Бородин, А. Н. Глебов, А. О. Иванова, Т. К. Неустроева, В. А. Ташкинов


Аннотация: A trivial lower bound for the $2$-distance chromatic number $\chi_2(G)$ of any graph $G$ with maximum degree $\Delta$ is $\Delta+1$. We prove that if $G$ is planar and its girth is at least $7$, then $\chi_2(G)=\Delta+1$ whenever $\Delta\ge 30$. On the other hand, we construct planar graphs with girth $5$ and $6$ that have arbitrarily large $\Delta$ and $\chi_2(G)>\Delta+1$.

УДК: 519.172.2

MSC: 05С15

Поступила 1 декабря 2004 г., опубликована 14 декабря 2004 г.



Реферативные базы данных:


© МИАН, 2024