RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2004, том 11, выпуск 1, страницы 13–29 (Mi da95)

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

Достаточное условие 3-раскрашиваемости плоских графов

О. В. Бородин, А. Н. Глебов

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Две известные гипотезы о 3-раскрашиваемости плоских графов состоят в том, что любой плоский граф без циклов длины 4 и 5 является 3-раскрашиваемым, а также существует такое $d>3$, что любой плоский граф с минимальным расстоянием не меньше $d$ между 3-циклами также 3-раскрашиваем. Ни одна из этих гипотез до сих пор не подтверждена и не опровергнута. В настоящей статье доказано, что если плоский граф не имеет 5-циклов и минимальное расстояние между 3-циклами не меньше 3, то такой граф 3-раскрашиваем.

УДК: 519.714

Статья поступила: 15.09.2003



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


© МИАН, 2024