Аннотация:Хроматическое число графа, то есть минимальное количество красок, которые необходимы для правильной вершинной раскраски графа, издавна является предметом изучения. Хорошо известна проблема четырёх красок. Задача раскраски графов сложна и имеет практическое применение в проектировании интегральных схем, а также в теории кодирования и других областях.
В работе Санжара Адилова изучается связь хроматического числа графов с их толщиной (минимальным числом планарных графов, объединение которых даёт исходный граф) и обхватом (длиной минимального цикла).
Связь обхвата и хроматического числа произвольного графа была изучена венгерским математиком Палом Эрдёшем, который доказал, что для любого положительного k существует граф с обхватом g ≥ k и хроматическим числом χ(G) ≥ k. Другими словами, существуют графы со сколь угодно большими обхватом и хроматическим числом. Однако выяснилось, что при наложении ограничений на толщину графа, удаётся доказать оценку сверху на хроматическое число. Например, широко известно, что планарные графы (толщина 1) допускают правильную раскраску в 4 цвета, а для бипланарных графов (толщины не более 2) без треугольников выпускник кафедры МаТИС Роман Ищенко доказал, что их хроматическое число не превосходит 8.
В своей выпускной работе Санжар обобщил результаты для бипланарных графов на случай произвольного обхвата, показал, что, начиная с обхвата 10, все бипланарные графы 5-раскрашиваемы. Далее Адилов С. Ш. с помощью этой же техники получил оценку хроматического числа графов произвольной заданной толщины k и обхвата g.