Том 6, серия 1, номер 4, 1999 г., Стр. 20-35
УДК 519.1
О. В. Бородин, А. В. Косточка, А. Распо, Э. Сопена
Ациклическая раскраска 1-планарных графов
Аннотация:
Граф называется 1-планарным, если его можно нарисовать на плоскости так, чтобы каждое ребро пересекалось не более чем с одним другим ребром. Доказано, что ациклическое хроматическое число любого 1-плоского графа не превосходит 20.
Ил. 7, библиогр. 15.
Бородин О. В. 2
Косточка А. В. 1
Распо А. 3
Сопена Э. 3
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
3. Университет Бордо I, Лаборатория информатики,
33405 Талане Седекс, Франция
Статья поступила 16 февраля 1999 г.
