Дробно-хроматическое число

Материал из WEGA

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

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

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

Литература

  • [Discrete Math.]