TOPICS
Search

Fractional Chromatic Number


Let f be a fractional coloring of a graph G. Then the sum of values of f is called its weight, and the minimum possible weight of a fractional coloring is called the fractional chromatic number chi^*(G), sometimes also denoted chi_f(G) (Pirnazar and Ullman 2002, Scheinerman and Ullman 2011) or chi_F(G) (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

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

where omega(G) is the clique number, omega^*(G) is the fractional clique 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).

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, chi^*=3 but chi=4. Integer differences greater than one are also possible, for example, at least four of the non-Cayley vertex-transitive graphs on 28 vertices have chi-chi^*=2, and many Kneser graphs have larger integer differences.

FractionalColoringGimbelConjecture

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 J_(92) 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 G,

 chi^*(G)>=(|G|)/(alpha(G)),
(2)

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

 chi^*(G)=(|G|)/(alpha(G)),
(3)

(Scheinerman and Ullman 2011, p. 30). However, equality may also hold for graphs that are not vertex-transitive, including for the path graph P_3, claw graph K_(1,3), 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 M_n is discussed by Larsen et al. (1995), the cycle graphs C_(2n+1) by Scheinerman and Ullman (2011, p. 31), and the Kneser graph K(n,k) by Scheinerman and Ullman (2011, p. 32).

graphfractional chromatic number
cycle graph C_(2n+1)2+(1/n)
Kneser graph K(n,k) for k<n-1n/k
Mycielski graph M_na_2=2 and a_n=a_(n-1)+a_(n-1)^(-1)

Other special cases are given in the following table.

antiprism graph3, 4, 10/3, 3, 7/2, 16/5, 3, 10/3, 22/7, ...
barbell graphA0000273, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
cocktail party graph K_(n×2)A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
complete graph K_nA0000273, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
cycle graph C_nA141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
empty graph K^__nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
helm graph4, 3, 7/2, 3, 10/3, 3, 13/4, 3, ...
Mycielski graph M_nA073833/A0738342, 5/2, 29/10, 941/290, 969581/272890, ...
pan graphA141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
prism graph Y_nA141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
sun graphA0000273, 4, 5, 6, 7, 8, 9, 10, 11, ...
sunlet graph C_n circledot K_1A141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
web graph5/2, 2, 9/4, 2, 13/6, 2, 17/8, 2, 21/10, 2, 25/12, ...
wheel graph W_n4, 3, 7/2, 3, 10/3, 3, 13/4, 3, 16/5, 3, 19/6, 3, ...

See also

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

Explore with Wolfram|Alpha

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 (<5)-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

Subject classifications