ALCOMFT-TR-02-89

Maria Andreou and Paul Spirakis
The Square of Any Planar Graph is an Almost Perfect Graph
Patras. Work packages 2 and 4. May 2002.

Abstract: In this work we answer a conjecture posed by Wegner in 1977 [Wegner77] for the vertex colouring problem on the square of any planar graph, proving a stronger result for this problem. This problem is motivated by the Frequency Assignment Problem in radio networks.

Let G = (V, E) be a graph. A vertex colouring of G is a function c: V -> {1, 2, ..., k}, such that c(v) != c(u) if (v,u) \in E. The chromatic number, \chi(G), of G is the smallest integer k for which there exists a vertex colouring of G. The clique number, omega(G), of G is the size of its maximum clique. The square, G², of G is a graph defined on the same vertex set as G which has an edge between any pair of vertices of distance at most two in G.

In this work we define the class of almost perfect graphs. A graph G is almost perfect iff G and each of its induced subgraphs have the property that their chromatic number are bounded above by their clique number plus a constant, independent of the graph size.

In this work we prove the following for any planar graph G with maximum degree \Delta.

• The clique number of G² is at most \floor{ 3\Delta/2 } + 1, if \Delta >= 6. Otherwise, omega(G²) <= \Delta + 4.
• The chromatic number of G² is at most omega(G²) + 3, if omega(G²) <= 8. Otherwise \chi(G²) <= omega(G²) +1.
  # We also prove that G² is an almost perfect graph. A consequence of our main result is that:
• Any efficient approximation algorithm for the chromatic number of G² is also an efficient approximation algorithm for its clique number and vice-versa.

Postscript file: ALCOMFT-TR-02-89.ps.gz (277 kb).