Аннотация:
Тривиальная нижняя граница для 2-дистанционного хроматического числа χ2(G) любого графа G с максимальной степенью Δ равна Δ+1. Известно, что χ2=Δ+1, если обхват g не меньше 7, а Δ достаточно велико. Существуют примеры графов со сколь угодно большой Δ и обхватом g⩽6, для которых χ2(G)⩾Δ+2. В статье доказана 4-раскрашиваемость плоских субкубических графов с g⩾23, что усиливает аналогичный результат О. В. Бородина, А. О. Ивановой и Т. К. Неустроевой (2004) и Дворжака, Шкрековски и Танцера (2008) для g⩾24. Ил. 2, библиогр. 20.
Образец цитирования:
О. В. Бородин, А. О. Иванова, “2-дистанционная 4-раскраска плоских субкубических графов”, Дискретн. анализ и исслед. опер., 18:2 (2011), 18–28; J. Appl. Industr. Math., 5:4 (2011), 535–541