Definitions
A b-fold coloring of a graph G is an assignment of sets of size b to vertices of a graph such that adjacent vertices receive disjoint sets. An a:b-coloring is a b-fold coloring out of a available colors. The b-fold chromatic number χb(G) is the least a such that an a:b-coloring exists.
The fractional chromatic number χf(G) is defined to be
Note that the limit exists because χb(G) is subadditive, meaning χa+b(G) ≤ χa(G) + χb(G).
The fractional chromatic number can equivalently be defined in probabilistic terms. χf(G) is the smallest k for which there exists a probability distribution over the independent sets of G such that for each vertex v, given an independent set S drawn from the distribution,
- .
Some properties of χf(G):
and
- .
Here n(G) is the order of G, α(G) is the independence number, ω(G) is the clique number, and χ(G) is the chromatic number.
Read more about this topic: Fractional Coloring
Famous quotes containing the word definitions:
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)