Better Know A Theorem: An “Easy” Chromatic Number

12Oct07

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 theseUSA 4-colouring 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 Petersen Fractional Edge-Colouringexample, 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.

Advertisements


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

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: