4446
правок
Раскраска графа: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 66: | Строка 66: | ||
'''Теорема 1 ([15]) Если | '''Теорема 1 ([15]) Если <math>\overrightarrow{\chi} (G) = k \;</math> , то граф G может быть раскрашен за полиномиальное время при помощи <math>min \{ \tilde{O}(\Delta^{1-2/k}), \tilde{O}(n^{1-3/(k+1)}) \}</math> цветов.''' | ||
| Строка 74: | Строка 74: | ||
Теорема 2 ([20]). Если | '''Теорема 2 ([20]). Если <math>\chi (G) = k \;</math> , то граф G может быть раскрашен за полиномиальное время при помощи <math>O(k n^{1-1/(k-1)}) \; </math> цветов.''' | ||
Теорема 3 ([2]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи | '''Теорема 3 ([2]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{3/8}) \; </math> цветов. Если <math>\chi (G) \; = k \ge 4 </math>, то граф G может быть раскрашен за полиномиальное время при помощи не более чем <math>\tilde{O} (n^{1-1/(k-3/2)}) \; </math> цветов.''' | ||
