Fractional Graph Coloring

I’m sure you know about ordinary graph coloring, but just in case: a k-coloring of a graph assigns to each node one of k colors such that no two nodes that share an edge share a color. Most maps are shaded with a 4-coloring of their adjacency graphs, and a Sudoku puzzle is just a puzzle of finishing partial 9-coloring of the Sudoku graph.

Fractional graph coloring is a way to generalize graph coloring to fractional color amounts. For example, the pentagon graph is 5:2-colorable, and the 9-cycle is 9:4-colorable. An a:b-coloring of a graph assigns to each node b colors out of the available a such that no two nodes that share an edge share a color. Note that an n:1-coloring is just an n-coloring. Here is an example 6:2-coloring of an unnamed graph:

From any a:b-coloring, you can get a corresponding an:bn coloring by assigning each original color to n colors (as the Wikipedia article for fractional coloring shows in its image). Note that the reverse cannot be performed; the above graph that has been 6:2-colored cannot be 3-colored, and was in fact specifically chosen because of this.

I was trying to figure out the fractional chromatic number of the icosahedron graph for an earlier part of this article. First I assumed that it was 7/2, then I thought it was 18/5, then I tried 11/3. I still don’t know what it is. “Hang on,” you might be wondering, “Why are these actual fractions?” There is a way to generalize fractional graph coloring to actual fractional numbers of colors: an x-coloring (with x a real number) assigns each node of a graph to a set of real numbers with measure 1 that is a subset of the interval [0,x]¹, and no two adjacent nodes can share a color. Alternatively, you can consider the fractional chromatic number to be the minimum of the fractions you get if you interpret the coloring numbers as fractions.

An infinite graph can be constructed to have any irrational fractional chromatic number larger than 2: Find a series of fractions that converge to that number from below (If we were to do this for pi, the first three could be 3, 25/8, and 47/15), and take the disjoint union of the corresponding Kneser graph for each one.

An unproven conjecture: If some graph can be a:b-colored, and bc > ad, then it can also be c:d-colored. Equivalently: If bc > ad, then the Kneser graph KG_a,b can be c:d-colored.

1. It doesn’t actually matter if the interval is closed or open, because points have measure 0. I just think square brackets look better. ↩︎