|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Раскраска в три цвета псевдокубических графовстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 30 июня 2021 г.
- Авторы: Селезнева С.Н., Мельник М.В., Астахова А.В.
- Журнал: Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика
- Номер: 2
- Год издания: 2019
- Издательство: Изд-во Моск. ун-та
- Местоположение издательства: М.
- Первая страница: 39
- Последняя страница: 45
- Аннотация: Граф называется псевдокубическим, если степени всех его вершин, за исключением одной, не превосходят трех, а степень исключительной вершины не превосходит четырех. В работе доказано, что вершины каждого псевдокубического графа без порожденных подграфов, изоморфных K_4 или K_4^-, можно раскрасить в три цвета. Кроме того, показано, что задача 3-раскраски псевдокубических графов может быть решена полиномиальным алгоритмом.
- Добавил в систему: Селезнева Светлана Николаевна