### Better Know A Theorem: An “Easy” Chromatic Number

One well-known problem in mathematics is to determine the minimum number of colours that map-makers can use to draw a map such that *adjacent countries are always coloured differently*. Let’s assume that countries always consist of a single connected region — this disallows islands and would exclude some real-life regions like Palestine. Also, let us take “adjacent” to mean “sharing a border of nonzero length and not just a corner” or else it is easy to see that an *n*-slice pizza map takes *n* colours. Under these assumptions, the celebrated 4-colour theorem tells us that 4 colours is always enough. For example, at the right is an image showing a map of the US meeting these conditions using only 4 colours: red, green, blue and brown. (The map is due to Robin Thomas.)

A *graph* is a mathematical object that can generalize this type of map. The graph consists of several **vertices **and some **edges** that connect pairs of vertices. In the map-maker analogy above, suppose we 1) place a vertex in each country and 2) for each border between two countries, create an edge connecting those two countries’ vertices. Then the requirement on the map-maker’s colouring is to *assign a colour to each vertex so that for each edge, its endpoints have different colours.*

We define the **chromatic number** to be the minimum total number of colours needed to obtain a colouring of the type described above. Many generalizations of this notion exist. First, the **edge-chromatic number** is the minimum total number of colours needed to *colour the edges such that for every vertex, all edges touching that vertex are coloured differently.* Second, the **fractional chromatic number** is the minimum value of the ratio *C*/*K*, where there exists an assignment of *K* distinct colours to each vertex, using *C* colours overall, so that no colour is assigned to both endpoints of any edge. Finally, combining both of these notions gives us the **fractional edge-chromatic number**.

Consider a fixed graph. Let *D* be the maximum number of edges that meet at any single vertex (the “maximum degree”). Let *v* be such a vertex. It is easy to see that the fractional edge-chromatic number is at least *D*: namely, if *K* colours are assigned to each vertex, then all *DK* colours assigned to edges meeting *v* must be distinct, so *C ≥ DK* and consequently the ratio *C/K* is at least *D*. Next, it is also easy to see that the fractional edge-chromatic number is at *most* the edge-chromatic number (take *K*=1). Vizing’s theorem tells us that the (fractional) edge-chromatic number is between *D* and *D*+1. As an example, the Petersen graph has *D*=3 and edge-chromatic number 4, but its fractional edge-chromatic number is 3, since a colouring exists wih *K*=2 and *C*=6 (see picture).

But in general, many of these numbers can be hard to find exactly. Finding the chromatic number, edge-chromatic number, or fractional chromatic number of a graph is NP-complete (i.e., hard in some explicit sense). However, finding the fractional edge-chromatic number of a graph can be done efficiently!

The efficient algorithm to find the fractional edge-chromatic number relies on a min-max relation, LP duality (see earlier post), the Tutte-Berge formula and the “matching polytope”. There is a well-written proof of the result in the cleverly-titled Fractional Graph Theory: A Rational Approach to the Theory of Graphs. I won’t get into the whole details here, but the min-max relation is the following: the fractional edge-chromatic number is max(*D, Λ*) where *Λ* is the maximum value of {2E(H)/(V(H)-1)} where H ranges over all induced subgraphs having V(H) odd.

Filed under: b.k.a.t., combinatorial optimization | Leave a Comment

## No Responses Yet to “Better Know A Theorem: An “Easy” Chromatic Number”