Изменения

Перейти к: навигация, поиск

Верхние и нижние оценки хроматического числа

175 байт добавлено, 14:53, 15 ноября 2015
Источники информации
<tex>m \leqslant \frac{1}{2}n(n - 1) - \frac{1}{2}\sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1) \Rightarrow \frac{n^2}{n^2 - 2m} \leqslant \frac{n^2}{n^2 -n(n - 1) + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{n + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{\sum\limits^{\chi}_{i = 1}|V_i| + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{\sum\limits^{\chi}_{i = 1}|V_i|^2} = \frac{(\sum\limits^{\chi}_{i = 1}|V_i|)^2}{\sum\limits^{\chi}_{i = 1}|V_i|^2} \leqslant \chi</tex>.
}}
==Смотри так же==
*[[Хроматическое_число_планарного_графа|Хроматическое число планарного графа]]
 
== Источники информации ==
* [http://www.ucdenver.edu/academics/colleges/CLAS/Departments/math/students/alumni/Documents/Student%20Theses/Mitchell_MSThesis.pdf Множество разных оценок для хроматических чисел]

Навигация