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