Fractional-coloring

Материал из WEGA
Перейти к навигации Перейти к поиску

Fractional-coloring --- дробная раскраска.

A fractional-coloring is a mapping [math]\displaystyle{ c }[/math] from the collection [math]\displaystyle{ {\mathcal S} }[/math] of independent sets of a graph [math]\displaystyle{ G }[/math] to the interval [math]\displaystyle{ [0,1] }[/math], if for every vertex [math]\displaystyle{ x }[/math] of [math]\displaystyle{ G }[/math] we have

[math]\displaystyle{ \sum \{c(S) : S \in {\mathcal S} \mbox{ such that } x \in S \} = 1. }[/math]

The value of a fractional-coloring [math]\displaystyle{ c }[/math] is

[math]\displaystyle{ \sum_{S \in {\mathcal S}}c(S). }[/math]

The fractional-chromatic number [math]\displaystyle{ \chi_{f}(G) }[/math] of [math]\displaystyle{ G }[/math] is the infimum of the values of fractional-colorings of [math]\displaystyle{ G }[/math].