Perfectness of the power graph

The power graph of a group is the graph whose vertices are the group elements (sometimes the identity is excluded but it doesn’t matter here), in which x and y are joined if one is a power of the other.

A finite graph is perfect if every induced subgraph has clique number equal to chromatic number. This is a well-studied class of graphs.

Theorem The power graph of a finite group is perfect.

In fact, much more is true. The result holds in any power-associative magma, that is, set with a binary operation in which powers of any element satisfy the associative law, and in particular, in any semigroup. Moreover, finiteness is not necessary, if we adopt the convention that an infinite graph is perfect if every finite induced subgraph is perfect.

The proof is not hard, but contains a small subtlety, so I will give it in full here.

A binary relation → is a partial preorder if it is reflexive and transitive. One of the first pieces of mathematics you might do when looking at binary relations is the analysis of partial preorders. Define a relation ≡ by the rule that x ≡ y if x → y and y → x. Then ≡ is an equivalence relation. Now define a relation on the set of equivalence classes by the rule that [x] ≤ [y] if u → v for some (and hence every) u∈[x] and v∈[y]. Then ≤ is a partial order on the set of equivalence classes.

Conversely, given an equivalence relation and a partial order on the set of equivalence classes, we can reconstruct uniquely the partial preorder on the original set.

As a paranthetical remark, this can be expressed in the language of species by saying that partial preorders are obtained from partial orders by substituting sets.

The comparability graph of a partial preorder → is the undirected graph in which distinct points x and y are joined if either x → y or y → x.

Now let G be a group. (As before, a power-associative magma would suffice.) We define the directed power graph on G by the rule that x → y if y is a power of x. Since x¹ = x and (x^m)ⁿ = x^mn, this is a partial preorder whose comparability graph is the power graph of G.

So the general result from which all follows is:

Theorem The comparability graph of a partial preorder is perfect.

First we observe that the class of comparability graphs of partial preorders is closed under taking induced subgraphs, so it suffices to prove that such a graph has chromatic number equal to clique number.

Here is the proof. In the case of a partial order, this is the easy part of Dilworth’s Theorem, and is proved as follows. Take a finite partial order. Then a clique in the comparability graph is a chain in the order. Let k be the maximal size of a chain. We need to find a k-colouring of the graph. So take the set of minimal elements in the partial order. They are pairwise incomparable, so we can give them the first colour. Then remove these elements and proceed inductively. We only need k colours since the obstruction to this would be a chain of length greater than k.

To go from partial orders to partial preorders, it is convenient to use the weak perfect graph theorem, proved by Lovász:

Theorem The complement of a perfect graph is perfect.

So let Γ be the complement of the comparability graph of a partial preorder → on x. The equivalence classes of the relation ≡ are sets of vertices which pairwise have the same neighbours, and in particular are not joined in Γ. Factor out ≡; that is, shrink each equivalence class to a single vertex (there is no anbiguity about the adjacency relation in the reduced graph). This is the complement of the comparability graph of the partial order ≤, and so is perfect. Suppose that its clique number and chromatic number are equal to k.

I claim that we can blow up each vertex of the reduced graph to an equivalence class and reconstruct Γ without changing the clique number and chromatic number. Consider the process of “cloning” a single vertex v, creating a new vertex v* with the same neighbours as v. Since v and v* are nonadjacent, we do not create a larger clique; and since they have the same neighbours, we can give v* the same colour as v. A number of steps of this kind finish the proof.

The argument can be done without going via the complement, but is rather messier since the “blowing-up” process does not preserve clique and chromatic numbers in the original graph.

I will conclude with an open problem. There are two other graphs that are similarly defined on a group G (I will restrict to groups here, since I have no idea what is possible in more general cases):

• the enhanced power graph, in which x and y are joined if they are both powers of an element z;
• the commuting graph, in which x and y are joined if xy = yx.

The power graph is a spanning subgraph of the enhanced power graph, which is itself a spanning subgraph of the commuting graph.

Neither of these two graphs is perfect in general. For the commuting graph, take the symmetric group of degree 5, and consider the five transpositions (1,2), (3,4), (5,1), (2,3), (4,5). The induced subgraph is a 5-cycle, which has clique number 2 and chromatic number 3. For the enhanced power graph, replace transpositions by cycles of pairwise coprime length (in a larger symmetric group) with the same intersection pattern, noting that elements of coprime orders in a group commute if and only if they are both powers of a single element, their product.)

Problem For which groups is the enhanced power graph perfect? For which groups is the commuting graph perfect?

In my paper with Ghodratallah Aalipour, Saieed Akbari, Reza Nikandish and Farzad Shaveisi, we determined the groups in which either the enhanced power graph or the commuting graph is equal to the power graph; they obviously satisfy the condition. What other groups can occur?