WikiSort.ru - Не сортированное

Раскраска

Раскраску квадрата графа можно использовать для назначения частот участникам беспроволочной сети таким образом, чтобы никакие два участника не мешали бы друг другу и любому другому из общих соседей^[4], а также для поиска графического представления графов с большим угловым разрешением^[en][5].

Как хроматическое число, так и вырождение^[en] k-ой степени планарного графа с максимальной степенью вершины Δ равны ${\displaystyle O(\Delta ^{\lfloor k/2\rfloor })}$ , где граница вырождения показывает, что можно использовать алгоритм жадной раскраски для раскраски графа таким числом цветов^[4]. Для случая квадрата планарного графа Вегнер в 1977 году высказал гипотезу, что хроматическое число такого графа не превышает ${\displaystyle \max \left(d+5,{\frac {3d}{2}}+1\right)}$ , и на текущий момент известно, что хроматическое число не превышает ${\displaystyle {\frac {5d}{3}}+O(1)}$ ^[6][7]. Более обще, для любого графа с вырождением d и максимальной степенью Δ вырождение квадрата графа равно O(dΔ), так что многие виды разреженных графов, отличные от планарных графов, также имеют пропорциональное Δ хроматическое число квадрата.

Хотя хроматическое число квадрата непланарного графа с максимальной степенью Δ может быть в худшем случае пропорционально Δ², оно меньше для графов с большим обхватом и для этого случая ограничено числом O(Δ²/log Δ)^[8].

Задача определения минимального числа цветов для раскраски квадратного графа NP-трудна даже для планарного случая^[9]

Гамильтоновость

Куб любого связного графа обязательно содержит гамильтонов цикл^[10]. Квадрат связного графа не обязательно будет содержать гамильтонов цикл и задача определения, что такой цикл содержится в квадрате, NP-полна^[11]. Тем не менее, согласно теореме Фляйшнера, квадрат вершинно 2-связного графа всегда гамильтонов^[12].