Treffer: Aspects of the commuting graph

We discuss the computational problem of deciding whether a given graph is the commuting graph of a finite group; we give a quasipolynomial algorithm, and a polynomial algorithm for the case when the group is an extraspecial p-group for p< an odd prime. We give new results on the question of whether the commuting graph of a given group is a cograph or a chordal graph, two classes of graphs defined by forbidden subgraphs. The problems are not unrelated, since there are a number of cases where hard computational problems on graphs are easier when restricted to special classes of graphs; we conjecture that the recognition problem is polynomial for cographs and chordal graphs.