Раскраска графа: различия между версиями

Раскраска графа (посмотреть исходный код)

1 байт убрано , 16 февраля 2015

м

4430

правок

Версия от 17:18, 16 февраля 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) ← Предыдущая правка		Версия от 17:19, 16 февраля 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) Следующая правка →
Строка 83:		Строка 83:


	~~<math>~~Теорема 4 ([3]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{3/14}) \; </math> цветов.~~</math>~~		'''Теорема 4 ([3]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{3/14}) \; </math> цветов.'''


	Теорема 5 ([13]). Если <math>\chi (G) = 4 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{7/9}) \; </math> цветов.		'''Теорема 5 ([13]). Если <math>\chi (G) = 4 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{7/9}) \; </math> цветов.'''