The fractional chromatic number of a graph
is the minimum possible weight of a fractional
coloring
, where the weight is the sum
of the values of
.
It is sometimes also denoted
(Pirnazar and Ullman 2002, Scheinerman and Ullman 2011)
or
(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
|
(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 (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,
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 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 with at least one graph vertex,
|
(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 the path graph .
Dúcz and Varga (2026) constructed the snail graph and used it to prove the existence of a finite unit-distance
graph
with
. It follows that the fractional chromatic
number of the plane satisfies
. 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 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 | |
| Mycielski
graph |
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 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 | 3, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ... | |
| wheel
graph | 4, 3, 7/2, 3, 10/3, 3, 13/4, 3, 16/5, 3, 19/6, 3, ... |
For an integer ,
let
be the maximum reduced denominator of the fractional
chromatic number among
-vertex graphs. Xu and Zhu (2026)
prove
|
(4)
|
They also improve the general determinant upper bound: for all sufficiently large ,
|
(5)
|
The lower bound is a limit-superior assertion, rather than a lower bound for every order.