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.
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