С.Н. Селезнева
Московский государственный университет имени М.В. Ломоносова, г. Москва, 119991, Россия
Полный текст PDF
DOI: 10.26907/2541-7746.2020.4.387-395
Для цитирования: Селезнева С.Н. О хроматическом числе графов с некоторым ограничением степеней вершин // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 4. – С. 387–395. – doi: 10.26907/2541-7746.2020.4.387-395.
For citation: Selezneva S.N. On the chromatic number of graphs with some restriction of vertex degrees. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 4, pp. 387–395. doi: 10.26907/2541-7746.2020.4.387-395. (In Russian)
Аннотация
Рассмотрены графы, в которых степень одной вершины равна (d + 1), а степени всех других вершин не превосходят d , d ≥ 3 . Установлены свойства, при которых вершины таких графов могут быть раскрашены в d цветов.
Ключевые слова: граф, раскраска, вершинная раскраска, хроматическое число, степень вершины графа
Благодарности. Работа поддержана МЦФПМ-МГУ, проект «Оценки сложностных характеристик булевых функций и графов» (2020 г.).
Литература
Поступила в редакцию
23.10.2020
Селезнева Светлана Николаевна, доктор физико-математических наук, профессор факультета вычислительной математики и кибернетики
Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия
E-mail: selezn@cs.msu.ru
Контент доступен под лицензией Creative Commons Attribution 4.0 License.