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

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength