4430
правок
Раскраска графа: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 80: | Строка 80: | ||
Сочетание техник, описанных в [15] и [2], дает следующие результаты для графов с <math>\chi (G) \; </math> | Сочетание техник, описанных в [15] и [2], дает следующие результаты для графов с <math>\chi (G) = 3, 4 \; </math> (эти результаты также были расширены для более высоких значений <math>\chi (G) \; </math>). | ||
Теорема 4 ([3]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи | <math>Теорема 4 ([3]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{3/14}) \; </math> цветов.</math> | ||
Теорема 5 ([13]). Если <math>\chi (G) \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи | Теорема 5 ([13]). Если <math>\chi (G) = 4 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{7/9}) \; </math> цветов. | ||
