Дробно-хроматическое число: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Дробно-хроматическое число''' (''Fractional-chromatic number'') - Отображение <math>c</math> из ...)
(нет различий)

Версия от 14:29, 15 октября 2009

Дробно-хроматическое число (Fractional-chromatic number) - Отображение [math]\displaystyle{ c }[/math] из набора [math]\displaystyle{ {\cal C} }[/math] независимых множеств графа [math]\displaystyle{ G }[/math] в интервал [math]\displaystyle{ [0,1] }[/math] есть дробная раскраска, если для каждой вершины [math]\displaystyle{ x }[/math] из [math]\displaystyle{ G }[/math] справедливо соотношение

[math]\displaystyle{ \sum_{S \in {\cal C}\mbox{ таким, что } x \in S} c(S) = 1. }[/math]

Величина дробной раскраски [math]\displaystyle{ c }[/math] есть [math]\displaystyle{ \sum_{S \in {\cal C}} c(S) }[/math]. Дробно-хроматическим числом [math]\displaystyle{ \chi_{f}(G) }[/math] называется инфинум величин дробных раскрасок [math]\displaystyle{ G }[/math].

Литература

[Discrete Math.]