Fractional Chromatic Number

 

Let  be a fractional coloring of a graph . Then the sum of values of  is called its weight, and the minimum possible weight of a fractional coloring is called the fractional chromatic number , sometimes also denoted  (Pirnazar and Ullman 2002, Scheinerman and Ullman 2011) or  (Larson et al. 1995), and sometimes also known as the set-chromatic number (Bollobás and Thomassen 1979), ultimate chromatic number (Hell and Roberts 1982), or multicoloring number (Hilton et al. 1973). Every simple graph has a fractional chromatic number which is a rational number or integer.

The fractional chromatic number of a graph can be obtained using linear programming, although the computation is NP-hard.

The fractional chromatic number of any tree and any bipartite graph is 2 (Pirnazar and Ullman 2002).

The fractional chromatic number satisfies

(1)

where  is the clique number,  is the fractional clique 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).

The fractional chromatic number of a graph may be an integer that is less than the chromatic number. For example, for the Chvátal graph,  but . Integer differences greater than one are also possible, for example, at least four of the non-Cayley vertex-transitive graphs on 28 vertices have , and many Kneser graphs have larger integer differences.

For any graph ,

(2)

where  is the vertex count and  is the independence number of . Equality always holds for a vertex-transitive , in which case

(3)

(Scheinerman and Ullman 2011, p. 30). However, equality may also hold for graphs that are not vertex-transitive, including for the path graph , claw graph , diamond graph, etc.

Closed forms for the fractional chromatic number of special classes of graphs are given in the following table, where the Mycielski graph  is discussed by Larsen et al. (1995), the cycle graphs  by Scheinerman and Ullman (2011, p. 31), and the Kneser graph  by Scheinerman and Ullman (2011, p. 32).

graph	fractional chromatic number
cycle graph
Kneser graph  for
Mycielski graph	and

Other special cases are given in the following table.

antiprism graph		3, 4, 10/3, 3, 7/2, 16/5, 3, 10/3, 22/7, ...
barbell graph	A000027	3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
cocktail party graph	A000027	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
complete graph	A000027	3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
cycle graph	A141310/A057979	3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
empty graph	A000012	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
helm graph		4, 3, 7/2, 3, 10/3, 3, 13/4, 3, ...
Mycielski graph	A073833/A073834	2, 5/2, 29/10, 941/290, 969581/272890, ...
pan graph	A141310/A057979	3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
prism graph	A141310/A057979	3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
sun graph	A000027	3, 4, 5, 6, 7, 8, 9, 10, 11, ...
sunlet graph	A141310/A057979	3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
web graph		5/2, 2, 9/4, 2, 13/6, 2, 17/8, 2, 21/10, 2, 25/12, ...
wheel graph		4, 3, 7/2, 3, 10/3, 3, 13/4, 3, 16/5, 3, 19/6, 3, ...

---

REFERENCES

Bollobás, B. and Thomassen, A. "Set Colorourings of Graphs." Disc. Math. 25, 27-31, 1979.

Godsil, C. and Royle, G. "Fractional Chromatic Number." §7.3 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 137-138, 2001.

Hell, P. and Roberts, F. "Analogues of the Shannon Capacity of a Graph." Ann. Disc. Math. 12, 155-162, 1982.

Hilton, A. J. W.; Rado. R.; and Scott, S. H. "A -Colour Theorem for Planar Graphs." Bull. London Math. Soc. 5, 302-306, 1973.

Larsen, M.; Propp, J.; and Ullman, D. "The Fractional Chromatic Number of Mycielski's Graphs." J. Graph Th. 19, 411-416, 1995.

Lovász, L. "Semidefinite Programs and Combinatorial Optimization." In Recent Advances in Algorithms and Combinatorics (Ed. B. A. Reed and C. L. Sales). New York: Springer, pp .137-194, 2003,

Pirnazar, A. and Ullman, D. H. "Girth and Fractional Chromatic Number of Planar Graphs." J. Graph Th. 39, 201-217, 2002.

Scheinerman, E. R. and Ullman, D. H. Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, 2011.

Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A057979, A073833, A073834, and A141310 in "The On-Line Encyclopedia of Integer Sequences."

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

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