TOPICS

# Fractional Edge Chromatic Number

The fractional edge chromatic number of a graph is the fractional analog of the edge chromatic number, denoted by Scheinerman and Ullman (2011). It can be defined as

 (1)

where is the fractional chromatic number of and is the line graph of .

There exists a polynomial-time algorithm for computing the fractional edge chromatic number (Scheinerman and Ullman 2011, pp. 86-87).

If the edge chromatic number of a graph equals its maximum vertex degree (i.e., if a graph is class 1), then the fractional edge chromatic number also equals . This follows from the general principle for fractional objects that

 (2)

and the fact that

 (3)

(Scheinerman and Ullman 2011, p. 80), so combining gives

 (4)

Therefore, if , .

Since any vertex-transitive graph has either a perfect matching (for even vertex degree) or a near-perfect matching (for odd vertex-degree; Godsil and Royle 2001, p. 43) and every vertex-transitive graph has its fractional chromatic number given by the vertex count divided by its independence number, applying the above to the line graph means that a symmetric graph (i.e., one that is both vertex- and edge-transitive) has fractional edge chromatic number given by

 (5)

where is the vertex count and the edge count of (S. Wagon, pers. comm., Jun. 6, 2012).

The flower snark is an example of a graph for which the edge chromatic number and fractional edge chromatic number are both integers, but (Scheinerman and Ullman 2001, p. 96).

Edge Chromatic Number, Fractional Chromatic Number

## Explore with Wolfram|Alpha

More things to try:

## References

Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Scheinerman, E. R. and Ullman, D. H. "Fractional Edge Coloring." Ch. 4 in Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, pp. 77-98, 2011.

## Cite this as:

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