О хроматическом числе графов с некоторым ограничением степеней вершин

С.Н. Селезнева

Московский государственный университет имени М.В. Ломоносова, г. Москва, 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 г.).

Литература

  1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Либроком, 2009. – 383 с.
  2. Bondy J.A., Murty U.S.R. Graph Theory. – Springer, 2008. – 655 p.
  3. Stockmeyer L.J. Planar 3 -colorability is NP -complete // SIGACT News. – 1973. – V. 5, No 3. – P. 19–25.
  4. Garey M.R., Johnson D.S., Stockmeyer L. Some simplified NP -complete graph problems // Theor. Comput. Sci. – 1976. – V. 1, No 3 – P. 237–267. – doi: 10.1016/0304-3975(76)90059-1.
  5. Малышев Д.С. Полная классификация сложности задачи о вершинной 3 -раскраске для четверок порожденных 5 -вершинных запретов // Журн. Средневолж. матем. о-ва. – 2020. – Т. 22, Вып. 1. – С. 38–47. – doi: 10.15507/2079-6900.22.202001.38-47.
  6. Селезнева С.Н., Мельник М.В., Астахова А.В. Раскраска в три цвета псевдокубических графов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. – 2019. – Вып. 2. – С. 39–45.
  7. Визинг В.Г. Раскраска вершин графа в предписанные цвета // Методы дискретного анализа в теории кодов и схем: Сб. науч. тр. – Новосибирск: Ин-т математики СО АН СССР, 1976. – Вып. 29. – С. 3–10.

Поступила в редакцию

23.10.2020

 

Селезнева Светлана Николаевна, доктор физико-математических наук, профессор факультета вычислительной математики и кибернетики

Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия

E-mail: selezn@cs.msu.ru

 

Контент доступен под лицензией Creative Commons Attribution 4.0 License.