Perfectness of commuting graphs

A finite graph is perfect if the clique number and chromatic number of any induced subgraph are equal. The main facts about perfect graphs are:

• (The Strong Perfect Graph Theorem) A graph is perfect if and only if it has no induced subgraph which is an odd cycle of length at least 5 or the complement of one.
• (The Weak Perfect Graph Theorem) If a graph is perfect then so is its complement.

In recent postings I defined the power graph and the commuting graph of a finite group. In the case of the commuting graph, central elements of the group were excluded; here it won’t matter if they are excluded or not. If we include them, then the power graph is a spanning subgraph of the commuting graph. (This is just a fancy way of saying that if one element is a power of another then the two elements commute.)

The power graph of a finite group is perfect. So a natural question is:

For which finite groups G is the commuting graph perfect?

For example, for the alternating group A5, the commuting graph consists of a bunch of complete graphs with one vertex from each complete graph identified; it is clearly perfect. However, the commuting graph of S5 is not perfect, since the five transpositions (1,2), (2,3), (3,4), (4,5), and (5,1) induce a cyclic subgraph.

I did wonder if perhaps the commuting graph of a soluble group might be perfect; but this is false. The group with presentation

a0,…,a4 | ai2=(aiai+1)2=(aiai+2)4=1 (i=0,…,4)⟩

(indices mod 5) is presumably infinite, but it has finite quotients in which the orders of elements are precisely as specified: for example, its largest nilpotent quotient of class 2 has order 1024. The five images of the generators in this quotient induce a 5-cycle.

This can be generalised. Given a graph X, the graph group FX is the group generated by elements av for vertices v of X, with relations asserting that generators corresponding to adjacent vertices commute. Let us say that a homomorphic image of a graph group is large if the images of the generators are all distinct and not the identity, and the images of generators corresponding to non-adjacent vertices do not commute. Then any finite large quotient of a graph group FX, where X is an odd cycle of length at least 5 or the complement of one, has imperfect commuting graph. Conversely, by the Strong Perfect Graph Theorem, the commuting graph of a group G is imperfect if and only if G contains a subgroup which is a large quotient of such a graph group.

This characterisation is not very helpful – but at least it suggests that progress on this problem depends on describing large finite quotients of these specific graph groups.

I count all the things that need to be counted.
This entry was posted in exposition, open problems. Bookmark the permalink.

One Response to Perfectness of commuting graphs

1. Nick Gill says:

Peter, I came across this post after asking (and answering) the following related question on mathoverflow: http://mathoverflow.net/questions/110404/when-does-a-distinguished-matching-exist

With regard to the perfectness of commuting graphs, I believe Brown has written two papers concerned with the symmetric groups that prove that the chromatic and clique numbers of the NON-commuting graph do not coincide for n>=15. Which implies that these non-commuting graphs are not perfect and hence, by the WPGT, that the corresponding commuting graphs are not perfect either.

Azad, Britnell and I have some (currently unpublished) results for simple groups of Lie type and for GL_n(q) which may (eventually) yield an answer to which of these groups have perfect commuting graph.

Best wishes, Nick Gill