4446
правок
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 89: | Строка 89: | ||
Наилучший известный на данный момент результат для раскраски графа в три цвета приведен в [1]. Описанный в этой работе алгоритм использует релаксацию алгоритма строгой векторной раскраски (т.е. | Наилучший известный на данный момент результат для раскраски графа в три цвета приведен в [1]. Описанный в этой работе алгоритм использует релаксацию алгоритма строгой векторной раскраски (т.е. <math>\overrightarrow{\chi}_2 \; </math>), дополненную определенными ограничениями для нечетных циклов. | ||
Теорема 6 ([1]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи O( | '''Теорема 6 ([1]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>O(n^{0.2111}) \; </math> цветов.''' | ||