4446
правок
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 101: | Строка 101: | ||
Теорема 7 ([10]) (i). Для всех константных значений | '''Теорема 7 ([10]) (i). Для всех константных значений <math>\varepsilon > 0 \; </math> и <math>k > 2 \; </math> существует бесконечное число графов G, таких, что <math>\overrightarrow{\chi} (G) = k \; </math> и <math>\alpha (G) \le n / \Delta^{1-2/k - \varepsilon}</math> (здесь <math>\Delta > n^{\delta} \; </math> для некоторой константы <math>\delta > 0 \; </math>). (ii) Существует бесконечное число графов G, таких, что <math>\overrightarrow{\chi} (G) = 3 \; </math> и <math>\alpha (G) \le n^{0.843} \; </math>. (iii) Для некоторого константного значения c существует бесконечное число графов G, таких, что <math>\overrightarrow{\chi} (G) = O(log \; n/log \; log \; n) \; </math> и <math>\alpha (G) \le log^c n \; </math>.''' | ||
Теорема 8 ([7]). Для некоторого константного значения c существует бесконечное число графов G, таких, что ~f2(G) < 2^°%" and <math>\chi (G) \; </math> > | '''Теорема 8 ([7]). Для некоторого константного значения c существует бесконечное число графов G, таких, что ~f2(G) < 2^°%" and <math>\chi (G) \; </math> >''' | ||