The prime graph on class sizes of a finite group has a bipartite complement (Q2333341)

In this paper the authors prove the statement of the title. Let \(G\) be a finite group. Write \(\mathrm{cs}(G)\) for the set of the conjugacy class sizes of \(G\). The prime graph for this set is the simple undirected graph \(\Delta(G)\) whose vertex set consists of the prime divisors of the elements in \(\mathrm{cs}(G)\), and two distinct vertices \(p\) and \(q\) are connected by an edge if and only if \(pq\) divides some element in \(\mathrm{cs}(G)\). By earlier work of the first author [J. Algebra 303, No. 1, 216--224 (2006; Zbl 1105.20017)] it is known that for any three distinct vertices of \(\Delta(G)\) there is at least one edge between two of them. Another way to state this result is to say that the complement of \(\Delta(G)\) does not contain a triangle, i.e., a cycle of length 3. In the paper under review, the authors generalize this result by showing that the complement of \(\Delta(G)\) does not contain any cycle of odd length, which implies that it is a bipartite graph. The proof of this result introduces and uses an orientation on a suitable subgraph of the complement graph. As a consequence of their main result, the authors derive that \(\Delta(G)\) cannot contain any pentagon, and the vertex set of \(\Delta(G)\) can be partitioned into two subsets whose induced subgraphs are cliques.