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

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

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

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

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

Литература

  • [Discrete Math.]