RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1992, том 4, выпуск 1, страницы 60–65 (Mi dm717)

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

Структурная теорема о плоских графах и ее приложение к раскраске

О. В. Бородин


Аннотация: Получен симметричный вариант теоремы Лебега 1940 г. об инциденции младших вершин и младших граней в плоских нормальных картах, имеющий неулучшаемый характер. В интересах приложения к раскраске графов этот результат переносится с привлечением дополнительной структурной информации на подходящее расширение класса нормальных карт. Как следствие, устанавливается справедливость (за исключением четырех частных случаев) гипотезы Кронка и Митчема 1973 г. о совместной раскраске вершин, ребер и граней плоских графов.

УДК: 519.1

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



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


© МИАН, 2024