TOPICS
Search

Fractional Chromatic Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The fractional chromatic number chi^*(G) of a graph G is the minimum possible weight of a fractional coloring f, where the weight is the sum of the values of f. It is sometimes also denoted chi_f(G) (Pirnazar and Ullman 2002, Scheinerman and Ullman 2011) or chi_F(G) (Larsen et al. 1995), and sometimes also known as the set-chromatic number (Bollobás and Thomason 1979), ultimate chromatic number (Hell and Roberts 1982), or multicoloring number (Hilton et al. 1973). Every finite simple graph has a fractional chromatic number which is a rational number.

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 or bipartite graph with at least one graph edge 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 (Larsen 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 Chiu graph illustrated above (Chiu et al. 2021). Chiu et al. (2024) 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 4-regular planar graphs having these values.

For any finite graph G with at least one graph vertex,

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 the path graph P_4.

Dúcz and Varga (2026) constructed the snail graph and used it to prove the existence of a finite unit-distance graph G with alpha(G)/|G|<1/4. It follows that the fractional chromatic number of the plane satisfies chi_f(R^2)>4. ChatGPT and Codex assisted the computational search and software development. Independent peer review had not been reported as of Sep. 21, 2026.

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), n>=12+(1/n)
Kneser graph K(n,k) for 1<=k<=n/2n/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. The web graph row starts with a base cycle graph of length 3, followed by lengths 4, 5, ....

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 graph3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
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, Independence Ratio, Snail Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Bollobás, B. and Thomason, A. "Set Colourings of Graphs." Disc. Math. 25, 21-26, 1979. https://doi.org/10.1016/0012-365X(79)90148-1.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, pp. 84-91, 2021. https://doi.org/10.1007/978-3-030-83823-2_14.Chiu, M.-K.; Felsner, S.; Scheucher, M.; Schröder, F.; Steiner, R.; and Vogtenhuber, B. "Coloring Circle Arrangements: New 4-Chromatic Planar Graphs." European J. Combin. 121, 103839, 2024. https://doi.org/10.1016/j.ejc.2023.103839.Dúcz, A. and Varga, D. "A Unit-Distance Graph in the Plane with Independence Ratio Below 1/4." 26 Jun 2026. https://arxiv.org/abs/2606.28157.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-168, 1982. https://doi.org/10.1016/S0304-0208(08)73501-1.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 Resource. https://mathworld.wolfram.com/FractionalChromaticNumber.html

Subject classifications