TOPICS

# 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.

Gimbel et al. (2019) conjectured that every 4-chromatic planar graph has fractional chromatic number strictly greater than 3. Counterexamples are provided by the 18-node Johnson skeleton graph as well as the 18-node example given by Chiu et al. (2021) illustrated above. Chiu et al. (2021) further demonstrated that there are exactly 17 4-regular 18-vertex planar graphs with chromatic number 4 and fractional chromatic number 3, and that there are no smaller graphs having these values.

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, ...

Chromatic Number, Fractional Clique Number, Fractional Coloring, Fractional Edge Chromatic Number

## Explore with Wolfram|Alpha

More things to try:

## References

Bollobás, B. and Thomassen, A. "Set Colorourings of Graphs." Disc. Math. 25, 27-31, 1979.Chiu, M. K.; Felsner, S.; Scheucher, M.; Schröder, F.; Steiner, R.; and Vogtenhuber, B. "Coloring Circle Arrangements: New 4-Chromatic Planar Graphs." In Extended Abstracts EuroComb 2021 (Ed. J. Nešetril, G. Perarnau, J. Rué, and O. Serra). Cham, Switzerland: Birkhäuser, Cham., pp. 84-91, 2021.Gimbel, J.; Kündgen, A.; Li, B.; and Thomassen, C. "Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces." SIAM J. Disc. Math. 33, 1415-1430, 2019.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."

## Referenced on Wolfram|Alpha

Fractional Chromatic Number

## Cite this as:

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