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

Перейти к навигации Перейти к поиску
Строка 87: Строка 87:




'''Теорема 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/19}) \; </math> цветов.'''




Источник — http://pco.iis.nsk.su/wega/index.php/Раскраска_графа