Реберная раскраска графов разных типов

1.

Реберная раскраска графов разных типов.
В задаче рёберной раскраски задаётся вопрос, можно ли раскрасить рёбра заданного графа
максимум в K различных цветов для заданного значения K или для минимального возможного
числа цветов. Как говорилось в [1], согласно теореме Визинга, χ'(G) = ∆(G) или x' (G) = ∆(G) +1 для
любого графа G.
Недавно Маттиоло, Маццуокколо и Табарелли доказали, что если есть граф с ∆(G) ≥ 2 и у него нет
охватывающего четного подграфа без изолированных вершин, то s(G) > δ(G), где δ(G) минимальная степень вершин в графе G.[2]
Степень вершины v ∈ V(G) может обозначаться через d(G(v)).[3]
Существуют различные алгоритмы раскраски для разных типов графов.
Например, нахождение полиномиального решения задачи о рёберной раскраске, порождаемых
запрещёнными 8-рёберными субкубическими лесами.[4] Также при составлении точного
расписания занятий, которые представляются в виде графов, мультиграфов, наборов графов.[5]
Или для получение исходного графа, чтобы получить решение для задачи 3-раскраски кубических
графов.[6]
Результат, полученный после раскраски ребер также может быть использован для решения других
задач, например в поиске минимальных реберных 1-расширений неориентированного цветного
графа.[7]
Также для раскрашенного графа существует задача расширения для звездных графов и
расширения 4-слойных графов и гиперкубов.[8][9]
Существуют приложения и в медицине. В работе [10] рассматривается объект исследования —
проектирование и реализация алгоритма нахождения линейных нейтрализующих мотивов в
молекулярных данных, для нахождения биомаркеров для выявления рака или вирусной
инфекции.

2.

Литература.
[1] Ghazaryan A. B., Petrosyan P. A. On the palette index of graphs having a spanning star //Proceedings
of the YSU A: Physical and Mathematical Sciences. – 2022. – Т. 56. – №. 3 (259). – С. 85-96.
[2] Mattiolo D., Mazzuoccolo G., Tabarelli G. Graphs with large palette index //Discrete Mathematics. –
2022. – Т. 345. – №. 5. – С. 112814.
[3] Sahakyan A. K., Kamalian R. R. Interval edge-colorings of trees with restrictions on the edges
//Proceedings of the YSU A: Physical and Mathematical Sciences. – 2021. – Т. 55. – №. 2 (255). – С. 113122.
[4] Малышев Д. С., Дугинов О. И. О случаях полиномиальной разрешимости задачи о рёберной
раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами //Дискретный
анализ и исследование операций. – 2022. – Т. 29. – №. 2. – С. 38-61.
[5] Масляев Д. А. СОВРЕМЕННОЕ СОСТОЯНИЕ ЗАДАЧИ АВТОМАТИЗАЦИИ СОСТАВЛЕНИЯ
ОПТИМАЛЬНОГО УЧЕБНОГО РАСПИСАНИЯ В ВУЗЕ //Вестник Сыктывкарского университета. Серия
1. Математика. Механика. Информатика. – 2022. – №. 1 (42). – С. 23-40.
[6] Pavlovic I. M. On proper graph colorings. – 2021.
[7] Razumovskii P. V. The search for minimal edge 1-extension of an undirected colored graph
//Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика.
– 2021. – Т. 21. – №. 3. – С. 400-407.
[8] Абросимов М. Б., Разумовский П. В. Минимальные расширения цветных звездных графов
//International Journal of Open Information Technologies. – 2022. – Т. 10. – №. 2. – С. 1-7.
[9] Лобов А. А., Абросимов М. Б. Вершинные расширения 4-слойных графов и гиперкубов
//Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика.
– 2022. – Т. 22. – №. 4. – С. 536-548.
[10] Муравейко Д. О. Алгоритмы нахождения линейных нейтрализующих мотивов в молекулярных
данных: магистерская диссертация : дис. – БГУ, ФПМИ, Кафедра дискретной математики и
алгоритмики, 2021.