Fractional Clique Number

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

The fractional clique number satisfies

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

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength