TOPICS
Search

Fractional Clique Number


The maximum possible weight of a fractional clique of a graph G is called the fractional clique number of G, denoted omega^*(G) (Godsil and Royle 2001, pp. 136-137) or omega_F (Larson et al. 1995). Every simple graph has a fractional clique number which is a rational number or integer.

The fractional clique number satisfies

 omega(G)<=omega^*(G)=chi^*(G)<=chi(G),

where omega(G) is the clique number, chi^*(G) is the fractional chromatic number, and chi(G) is the chromatic number (Godsil and Royle 2001, pp. 141 and 145), where the result omega^*(G)=chi^*(G) follows from the strong duality theorem for linear programming (Larson et al. 1995; Godsil and Royle 2001, p. 141).


See also

Clique Number, Fractional Clique, Fractional Coloring

Explore with Wolfram|Alpha

References

Godsil, C. and Royle, G. "Fractional Clique Number." §7.2 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 136-137, 2001.Larsen, M.; Propp, J.; and Ullman, D. "The Fractional Chromatic Number of Mycielski's Graphs." J. Graph Th. 19, 411-416, 1995.

Referenced on Wolfram|Alpha

Fractional Clique Number

Cite this as:

Weisstein, Eric W. "Fractional Clique Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FractionalCliqueNumber.html

Subject classifications