Том 9, серия 1, номер 1, 2002 г., Стр. 3-26
УДК 519.172
В. А. Аксенов, О. В. Бородин, А. Н. Глебов
О продолжении 3-раскраски с двух вершин в плоском графе без 3-циклов
Аннотация:
Раскраска вершин графа в$k$ цветов называется правильной$k$ -раскраской, если любые две смежные вершины окрашены в разные цвета. Доказано, что любая правильная раскраска, заданная на двух вершинах плоского графа$G$ без 3-циклов, может быть продолжена до правильной 3-раскраски графа$G$ .
Ил. 17, библиогр. 6.
Аксенов В. А. 2
Бородин О. В. 1
Глебов А. Н. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: borodin@math.nsc.ru, angle@math.nsc.ru
Статья поступила 21 ноября 2001 г.
