Том 11, серия 1, номер 1, 2004 г., Стр. 13-29
УДК 519.714
О. В. Бородин, А. Н. Глебов
Достаточное условие 3-раскрашиваемости плоских графов
Аннотация:
Две известные гипотезы о 3-раскрашиваемости плоских графов состоят в том, что любой плоский граф без циклов длины 4 и 5 является 3-раскрашиваемым, а также существует такое$d>3$ , что любой плоский граф с минимальным расстоянием не меньше$d$ между 3-циклами также 3-раскрашиваем. Ни одна из этих гипотез до сих пор не подтверждена и не опровергнута. В настоящей статье доказано, что если плоский граф не имеет 5-циклов и минимальное расстояние между 3-циклами не меньше 3, то такой граф 3-раскрашиваем.
Бородин О. В. 1
Глебов А. Н. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: brdnoleg@math.nsc.ru, angle@math.nsc.ru
Статья поступила 15 сентября 2003 г.
