\documentclass[ALCO, Unicode]{cedram}
\usepackage{amsmath, amssymb,epic,graphicx,mathrsfs}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{comment}
\usepackage{tikz}
\renewcommand{\thesection}{\arabic{section}}
\usepackage{url}
%\setlength{\parskip}{2mm}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{longtable}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{hhline}
%\numberwithin{equation}{section}
\newcommand{\leqs}{\leqslant}
\newcommand{\geqs}{\geqslant}
\DeclareMathOperator{\frat}{Frat}
%\DeclareMathOperator{\Syl}{Syl}
\DeclareMathOperator{\diam}{diam}
\newcommand{\nn}{\mathrel{\unlhd}}
\newcommand{\gen}[1]{\left\langle#1\right\rangle}
\DeclareMathOperator{\inn}{Inn} \DeclareMathOperator{\perm}{Sym}
\DeclareMathOperator{\Core}{Core} \DeclareMathOperator{\soc}{soc}
\DeclareMathOperator{\aut}{Aut} \DeclareMathOperator{\out}{Out}
\DeclareMathOperator{\Sz}{Sz} \DeclareMathOperator{\M}{M}
\DeclareMathOperator{\Th}{Th}\DeclareMathOperator{\B}{B}
\DeclareMathOperator{\J}{J} \DeclareMathOperator{\He}{He}
\DeclareMathOperator{\F}{F}\DeclareMathOperator{\Fix}{fix}
\DeclareMathOperator{\Suz}{Suz}\DeclareMathOperator{\odd}{odd}
\DeclareMathOperator{\HN}{HN}\DeclareMathOperator{\Ly}{Ly}
\DeclareMathOperator{\stab}{Stab}
\newcommand{\rw}{\mathrm{w}}
\DeclareMathOperator{\McL}{McL} \DeclareMathOperator{\Co}{Co}
\DeclareMathOperator{\ran}{rank} %\DeclareMathOperator{\frat}{Frat}
\DeclareMathOperator{\ssl}{SL} \DeclareMathOperator{\spp}{Sp}
\DeclareMathOperator{\PG}{PG}
\DeclareMathOperator{\oop}{O^+}
\DeclareMathOperator{\oom}{O^{--}} % \DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\maxd}{MaxDim}\DeclareMathOperator{\SU}{SU}
\DeclareMathOperator{\sym}{Sym}
\DeclareMathOperator{\pgl}{PGL}
\DeclareMathOperator{\ra}{rank} \DeclareMathOperator{\Ree}{R}
\DeclareMathOperator{\gl}{GL} \DeclareMathOperator{\psu}{PSU}
\DeclareMathOperator{\pg}{PG} \DeclareMathOperator{\gu}{GU}
\DeclareMathOperator{\pgu}{PGU}\DeclareMathOperator{\Ru}{Ru}
\DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\AGL}{AGL}
\newcommand{\Aa}{\text{A}}\newcommand{\Bb}{B}
\DeclareMathOperator{\mm}{M}\DeclareMathOperator{\core}{Core}
\DeclareMathOperator{\Ee}{E}\DeclareMathOperator{\Ff}{F}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\alt}{Alt}\DeclareMathOperator{\ON}{O'N}
\DeclareMathOperator{\End}{End} \DeclareMathOperator{\h}{{H^1}}
\DeclareMathOperator{\der}{Der} \DeclareMathOperator{\diag}{Diag}
\DeclareMathOperator{\fix}{fix}\DeclareMathOperator{\Syl}{Syl}
\DeclareMathOperator{\pgal}{P\Gamma L}\DeclareMathOperator{\fit}{Fit}
\newcommand{\abs}[1]{\left\vert#1\right\vert} \newcommand{\al}{\alpha}
\newcommand{\remm}{\mathrm{m}}
\newcommand{\g}{\gamma} \newcommand{\Al}{\Lambda}
\newcommand{\be}{\beta} \newcommand{\ol}{\overline}
\newcommand{\og}{\overline{G}}
\newcommand{\ox}{\overline{X}}
\newcommand{\pp}{p\prime}
\newcommand{\ovp}{\overline{\pi}}
\newcommand{\w}{\widetilde}
\newcommand{\OO}{\mathcal O}
\newcommand{\grs}{groups}
\newcommand{\sgr}{subgroup}
\newcommand{\op}{O^p}
%\newcommand{\C}{\mathbb C}
\newcommand{\FF}{\mathbb F}
\newcommand{\rg}{\Gamma}
\newcommand{\N}{\mathbb N}
\renewcommand{\AA}{\mathcal A}\newcommand{\PP}{\mathcal P}
\renewcommand{\SS}{\mathcal S}\renewcommand{\emptyset}{\varnothing}
\newcommand{\BB}{\mathcal B}
\newcommand{\MM}{\mathcal M}
\DeclareMathOperator{\menta}{MinInt}
\DeclareMathOperator{\manta}{MaxInt}
\DeclareMathOperator{\mindim}{MinDim}
\DeclareMathOperator{\maxdim}{MaxDim}
\DeclareMathOperator{\psl}{PSL}
\newcommand{\st}{such that }
\newcommand{\ifa}{if and only if } \newcommand{\f}{finite}
\newcommand{\au}{\alpha _1} \newcommand{\ad}{\alpha _2}
\newcommand{\ab}{abelian}
\newcommand{\subn}{subnormal} \newcommand{\nilp}{nilpotent}
\DeclareMathOperator{\prob}{Prob}\newcommand{\ov}[1]{\overline{#1}}
\newcommand{\zx}{\z^1_X}
\DeclareMathOperator{\z}{{Z}}
\title[Forbidden subgraphs in generating graphs of finite groups]{Forbidden subgraphs in generating graphs\\ of finite groups}
\author{\firstname{Andrea} \lastname{Lucchini}}
\address{Dipartimento di Matematica ``Tullio Levi-Civita''\\ Universit\`a degli Studi di Padova\\ 35121 Padova\\ Italy}
\email{lucchini@math.unipd.it}
\author{\firstname{Daniele} \lastname{Nemmi}}
\address{Dipartimento di Matematica ``Tullio Levi-Civita''\\ Universit\`a degli Studi di Padova\\ 35121 Padova\\ Italy}
\email{dnemmi@math.unipd.it}
\keywords{cographs, generating graph, perfect graphs}
\subjclass{20D60, 05C25}
\datereceived{2021-04-22}
\daterevised{2021-12-29}
\dateaccepted{2022-02-06}
\begin{document}
\begin{abstract} Let $G$ be a $2$-generated finite
group. The generating graph $\Gamma(G)$ is the graph whose vertices
are the elements of $G$ and where two vertices $g_1$ and $g_2$ are adjacent if $G = \langle g_1, g_2 \rangle.$ This graph
encodes the combinatorial structure of the distribution of generating pairs across $G.$ In this
paper we study
some graph theoretic properties of $\Gamma(G)$, with particular emphasis on those properties that can be formulated in terms of forbidden induced subgraphs. In particular we investigate when the generating graph $\Gamma(G)$ is a cograph (giving a complete description when $G$ is soluble) and when it is perfect (giving a complete description when $G$ is nilpotent and proving, among other things, that $\Gamma(S_n)$ and $\Gamma(A_n)$ are perfect if and only if $n\leq 4$). Finally we prove that for a finite group $G$, the properties that $\Gamma(G)$ is split, chordal or $C_4$-free are equivalent.
\end{abstract}
\maketitle
\section{Introduction}
If a finite group $G$ can be generated by $d$ elements, then the problem of determining the $d$-element generating sets for $G$
is non-trivial. The simplest interesting case is when $G$ is $2$-generated. One tool developed to study generators of a $2$-generated finite group $G$ is the generating graph $\Gamma(G)$ of $G.$ This is the graph which has the elements of $G$ as vertices and an edge between two elements $g_1$ and $g_2$ if $G$ is generated by $g_1$ and $g_2$. Some authors exclude the identity element in the set of vertices of $\Gamma(G);$ there is no substantial difference if $G$ is is
non-cyclic, but we choose to include the identity because we will also consider
cyclic groups.
Note that the generating graph may be defined for any group $G$, but it only has edges if $G$ is $2$-generated.
Several strong structural results about $\Gamma(G)$ are known in the case where $G$ is simple, and this reflects the rich group theoretic structure of these groups. For example, if $G$ is a non-abelian simple group, then the only isolated vertex of $\Gamma(G)$ is the identity \cite{gk} and the graph $\Delta(G)$ obtained by removing the isolated vertex is connected with diameter two \cite{bgk} and, if $|G|$ is sufficiently large, admits a Hamiltonian cycle \cite{bglm} (it is conjectured that the condition on $|G|$ can be removed). Moreover, in recent years there has been considerable interest in attempting to classify the groups $G$ for which $\Gamma(G)$ shares the strong properties of the generating graphs of simple groups. Recently, the following remarkable result
has been proved in \cite{bgh}:
the identity is the unique isolated vertex of $\Gamma(G)$ if and only if all proper quotients of $G$ are cyclic.
An open question is whether the subgraph $\Delta(G)$ of $\Gamma(G)$ induced by the non-isolated vertices is connected, for every finite group $G.$
The answer is positive if $G$ is soluble \cite{CL3} and in this case
the diameter of $\Delta(G)$ is at most three \cite{diam}. In \cite{hl} it is proved that when $G$ is nilpotent, then $\Delta(G)$ is maximally connected, i.e. the connectivity of the graph $\Delta(G)$ equals its minimum degree (recall that the connectivity of a finite graph $\Gamma$ is the least size of a
subset $X$ of the set $V(\Gamma)$ of the vertices such that the induced
subgraph on $V(\Gamma) \setminus X$ is disconnected).
The subgraph of a graph $\Gamma$ induced by a subset $X$ of the vertex set is the graph whose vertices are the elements of $X$ and where the edges are the edges of $\Gamma$ with both endpoints in $X.$
A number of important classes of graphs can be defined either structurally or
in terms of forbidden induced subgraphs, i.e. by specifying a family of graphs
that cannot appear as induced subgraphs.
The aim of this paper is to investigate some properties of the forbidden subgraphs of the generating graphs of finite groups.
A perfect graph is a graph in which the chromatic number of every induced
subgraph equals the order of the largest clique of that subgraph (clique number). A hole in a graph $\Gamma$ is an induced subgraph of $\Gamma$ isomorphic to a chordless cycle of length at least 4. An antihole is an induced subgraph $\Delta$ of $\Gamma$, such that $\overline{\Delta}$ is a hole of the complement graph $\overline{\Gamma}$. A hole
(resp. an antihole) is odd or even according to the number of its vertices. The strong perfect graph theorem is a forbidden graph characterization of perfect graphs as being exactly the graphs that have neither odd
holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas was announced in 2002 and published by them in 2006 \cite{crst}.
Motivated by the strong perfect graph theorem we analyze the existence of $m$-holes or $m$-antiholes in the generating graph of a finite group $G.$ The first result that can be proved with this approach is a complete characterization of the $2$-generated finite nilpotent groups with a perfect generating graph.
\begin{theorem}\label{nilperf}
Let $G$ be a finite $2$-generated nilpotent group. Then $\Gamma(G)$ is perfect if and only if the index of the Frattini subgroup is the product of at most four (not necessarily distinct) primes.
\end{theorem}
In general the condition on the number of prime divisors of the index of the Frattini subgroup is neither necessary nor sufficient to ensure that the generating graph is perfect, as it follows for example from the study of the generating graph of dihedral groups.
\begin{theorem}\label{diedrale}Let $D_n$ be the dihedral group of order $2n$. Then
$\rg(D_n)$ is perfect \ifa one of the following occurs:
\begin{enumerate}[label=(\arabic*)]
\item \label{12i} $n$ is even;
\item \label{12ii} $n$ is odd and divisible by at most two distinct primes. \end{enumerate}
\end{theorem}
An interesting and surprising consequence of Theorem \ref{diedrale} is that if $G$ is a $2$-generated finite group and $N$ is a normal subgroup of $G$, then the fact that $\Gamma(G)$ is perfect does not imply that
$\Gamma(G/N)$ is also perfect. For example let $m=p_1\cdot p_2 \cdot p_3$ be the product of three distinct odd primes and let $G=D_{2m}$ be the dihedral group of order $4m.$ By Theorem \ref{diedrale}, $\Gamma(G)$ is perfect. However, $G$ has a normal subgroup $N$ of order 2 such that $G/N \cong D_m$ and, again by Theorem \ref{diedrale}, $\Gamma(G/N)$ is not perfect.
We will prove (see Theorem \ref{mina5}) that the alternating group $A_5$ is the smallest $2$-generated finite group whose generating graph is not perfect. Moreover:
\begin{theorem}\label{altesim}
$\rg(A_n)$ and $\rg(S_n)$ are perfect \ifa $n < 5$.
\end{theorem}
The behaviour of the generating graph of the alternating groups suggests the following conjecture.
\begin{conjecture}\label{cong1}
If $G$ is a finite non-abelian simple group, then $\Gamma(G)$ is not perfect.
\end{conjecture}
Indeed, the proof of Theorem \ref{altesim} shows that if $n\geq 5$ then $\Gamma(A_n)$ and $\Gamma(S_n)$ contain a 5-hole, so we may also formulate a stronger conjecture.
\begin{conjecture}\label{cong2}
If $G$ is a finite non-abelian simple group, then there exists a subset $X$ of $G$ such that the subgraph of $\Gamma(G)$ induced by $X$ is a 5-hole.
\end{conjecture}
With the use of GAP \cite{GAP4}, we have checked the existence of a $5$-hole in $\rg(G)$ when $G$ is the Tits group or one of the sporadic simple groups with the exception of the Janko group $J_4$, the Thompson group, the Lyons group, the Baby Monster group and the Monster group.
Moreover Conjecture \ref{cong2} is true
when $G$ is a rank one group of Lie type, so we have:
\begin{thm}If $G$ is a simple group of Lie type of rank one,
then $\Gamma(G)$ is not perfect.
\end{thm}
A path graph is a graph whose vertices can be listed in the order $v_1, v_2, \dots, v_n$ such that the edges are $\{v_i, v_{i+1}\}$ where $i = 1, 2, \dots, n-1.$ A path graph with $n$-vertices is usually denoted by $P_n.$ A graph $\Gamma$ is called a cograph if $\Gamma$ has no induced subgraph isomorphic to the four-vertex path $P_4.$ Several alternative characterizations of cographs can be given:
\begin{enumerate}
\item
a cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex;
\item a cograph is a graph in which every non-trivial induced subgraph has at least two vertices with the same neighbourhoods;
\item a cograph is a graph in which every connected induced subgraph has a disconnected complement;
\item a cograph is a graph all of whose connected induced subgraphs have diameter at most 2.
\end{enumerate} We will prove
that if $N$ is a normal subgroup of a $2$-generated finite group $G$ and $\Gamma(G/N)$ contains an induced
subgraph isomorphic to $P_n$, then so does $\Gamma(G)$ (see Lemma \ref{quozienti}). Thus,
in contrast to perfectness, the property that $\Gamma(G)$ is a cograph is inherited by the epimorphic images of $G.$ This is a considerable advantage in the study of groups whose generating graph is a cograph and allows us to obtain some quite general results. For example we can completely characterize the $2$-generated finite soluble groups whose generating graph is a cograph.
\begin{theorem}\label{gencog}
Let $G$ be a $2$-generated finite soluble group. Then $\Gamma(G)$ is a cograph if and only if one of the following occurs.
\begin{enumerate}
\item $G$ is cyclic and $|G|$ is divisible by at most two distinct primes.
\item $G$ is a $p$-group.
\item $G/\frat(G) \cong V \rtimes \langle x \rangle$ where $x$ has prime
order
and $V$ is a faithful irreducible $\langle x \rangle$-module.
\end{enumerate}
\end{theorem}
Moreover we will prove the following theorems.
\begin{theorem}\label{unicoiso}
Let $G$ be a finite group and assume that the identity element is the unique isolated vertex of $\Gamma(G).$ If $\Gamma(G)$ is a cograph, then $G$ is soluble.
\end{theorem}
\begin{theorem}\label{perf}
Let $G$ be a $2$-generated finite group. If $\Gamma(G)$ is a cograph and $N$ is a maximal normal subgroup of $G,$ then $G/N$ is abelian.
\end{theorem}
\begin{coro}
Let $G$ be a non-trivial $2$-generated finite group. If $G$ is perfect, then $\Gamma(G)$ is not a cograph.
\end{coro}
The previous result suggests the following stronger conjecture.
\begin{conjecture}\label{cong4}
Let $G$ be a $2$-generated finite group. If $\Gamma(G)$ is a cograph, then $G$ is soluble.
\end{conjecture}
A graph is chordal if it contains no induced cycle of length greater then
3. A graph is called split if its vertex set is the disjoint union of two
subsets $A$ and $B$ so that $A$ induces a complete graph and $B$ induces
an empty graph. In the final part of the paper, we will prove the following result.
\begin{thm}\label{altrigrafi}Let $G$ be a $2$-generated finite group. Then the following conditions are equivalent.
\begin{enumerate}[label=(\arabic*)]
\item \label{1121} $\Gamma(G)$ is split.
\item \label{1122} $\Gamma(G)$ is chordal.
\item \label{1123} $\Gamma(G)$ is $C_4$-free, i.e. no induced subgraph of $\Gamma(G)$ is isomorphic to a cyclic graph with four vertices.
\item \label{1124} Either $G$ is a cyclic $p$-group or $|G|=2p$ for some prime $p.$
\end{enumerate}\end{thm}
\section{Cographs}
Our first result is that if $\Gamma(G)$ is a cograph, then $\Gamma(G/N)$ is also a cograph, for every normal subgroup $N$ of $G.$
In order to prove a more general statement which implies the previous sentence, we need to recall an auxiliary result, which generalizes an argument due to Gasch\"utz \cite{g2}. Given a subset $X$ of a finite group $G,$ we will denote by $d_X(G)$ the smallest cardinality
of a set of elements of $G$ generating $G$ together with the elements of $X.$ In the particular case when $X=\emptyset$, $d_\emptyset(G)=d(G)$
is the smallest cardinality of a generating set of $G.$
\begin{lemma}{\cite[Lemma 6]{CL3}}\label{modg} Let $X$ be a subset of $G$
and $N$ a normal subgroup of $G$ and suppose that
$\langle g_1,\dots,g_r, X, N\rangle=G.$
If $r\geq d_X(G),$ then we can find $n_1,\dots,n_r\in N$ so that $\langle g_1n_1,\dots,g_rn_r,X\rangle=G.$
\end{lemma}
\begin{lemma}\label{quozienti}
Let $G$ be a $2$-generated finite group and $N$ a normal subgroup of $G$ and let $t\in \mathbb N$ with $t\geq 2.$ If $\Gamma(G/N)$ contains an induced
subgraph isomorphic to $P_t$, then so does $\Gamma(G).$
\end{lemma}
\begin{proof}Assume that $(a_1N,a_2N,\dots,a_tN)$ is a $t$-vertex path in
$\Gamma(G/N).$ By Lemma \ref{modg} there exist $n_1, n_2 \in N$ such that
$\langle a_1n_1, a_2n_2 \rangle=G.$ In particular $d_{\{a_2n_2\}}(G)\leq 1,$ so, again by Lemma \ref{modg}, if $t\geq 3$ then there exists $n_3 \in N$ such that $\langle a_2n_2, a_3n_3 \rangle=G.$
By repeating this argument, we can find $n_1,\dots,n_t\in N$ such that
$\langle a_in_i, a_{i+1}n_{i+1}\rangle=G$ for $1\leq i\leq t-1.$ If $(r,s) \neq (i,i+1)$ for some $i\in \{1,\dots,t-1\}$, then $\langle a_r,a_s\rangle N \neq G,$ and consequently $\langle a_rn_r,a_sn_s\rangle\neq G.$
So $(a_1n_1,\dots,a_tn_t)$ is a $t$-vertex path in $\Gamma(G).$
\end{proof}
\begin{proof}[Proof of Theorem \ref{unicoiso}] %By Lemma \ref{quozienti}, it suffices to prove that if $G$ is a finite non-abelian simple group, then $\Gamma(G)$ is not a cograph.
This can be proved with the same argument used by Cameron in \cite[Theorem 8.8]{cam}. Let $\Delta(G)$ be the subgraph of $\Gamma(G)$ obtained by deleting the identity element. By \cite[Theorem 1]{bgh} the graph $\Delta(G)$ is connected. The join graph of $G$ is the graph whose vertices are the non-trivial proper subgroups of $G$ and in which two vertices $H$ and $K$ are adjacent if and only if $H\cap K\neq 1.$ By \cite{she} if $G$ is not soluble, then this graph is connected. It can be easily seen that this implies that the complement graph $\overline{\Delta(G)}$ is connected. Since the graph complement of a connected cograph is disconnected, it follows that $\Delta(G)$ (and consequently $\Gamma(G)$) is not a cograph when $G$ is not soluble.
\end{proof}
\begin{proof}[Proof of Theorem \ref{perf}] Let $N$ be a maximal normal subgroup of $G$. If $G/N$ is non-abelian, then it is isomorphic to a non-abelian simple group and by \cite{gk} the identity element is the unique isolated vertex of $\Gamma(G/N).$ So the conclusion follows immediately by combining Lemma \ref{quozienti} and Theorem \ref{unicoiso}.
\end{proof}
Let $\frat(G)$ be the Frattini subgroup of $G.$
\begin{lemma}\label{abelian}
Let $G$ be a $2$-generated finite nilpotent group. If $\Gamma(G)$ is a cograph, then $|G/\frat(G)|$ is the product of at most two primes.
\end{lemma}
\begin{proof}
Assume that $|G/\frat(G)|$ is divisible by $p_1p_2p_3$, with $p_1, p_2, p_3$ prime numbers. Since $d(G)\leq 2,$ we cannot have $p_1=p_2=p_3$ and so we may assume $p_3\notin \{p_1, p_2\}.$ Consider $X=\langle x_1 \rangle \times \langle x_2 \rangle \times
\langle x_3 \rangle$ with $|x_i|=p_i$ for $1\leq i \leq 3.$ It can be easily checked that $(x_1,1,1), (1, x_2,x_3),$ $(x_1,1,x_3),$ $(1,x_2,1)$ is
a four-vertex path in $\Gamma(X).$ Since $X$ is an epimorphic image of $G,$ Lemma \ref{quozienti} would imply that $\Gamma(G)$ is not a cograph.
\end{proof}
Before we state the following lemma, let us recall some definitions that will be used in the statement. A chief factor $X/Y$ of a finite group $H$ is said to be complemented in $H$ if $X/Y$ has a complement in $H/Y.$ If $V$ is a finite irreducible $H$-module, then a chief factor $X/Y$ of $H$ is $H$-isomorphic to $V$ if there exists a group isomorphism $\phi: X/Y \to V$ with the property that $\phi(x^h Y)=\phi(xY)^h,$ for any $x \in X$ and $h \in H.$
\begin{lemma}\label{semidiretto}
Let $H$ be a $2$-generated finite soluble group and $V$ a finite non-trivial irreducible $H$-module. Assume that there exist $a,b \in H$ such that
\begin{enumerate}
\item $H=\langle a, b \rangle$;
\item $H \neq \langle a\rangle, H \neq \langle b\rangle;$
\item $a \notin C_H(V), b \notin C_H(V).$
\end{enumerate}
Consider the semidirect product $G=V\rtimes H.$ If no complemented chief factor of $H$ is $H$-isomorphic to $V$, then $\Gamma(G)$ contains a subgraph isomorphic to the four-vertex path $P_4.$
\end{lemma}
\begin{proof}
Let $|V|=p^t,$ with $p$ a prime. Define
$$\Omega_a=\{v\in V\mid \langle a, bv\rangle=G\}, \quad \Omega_b=\{v\in V\mid \langle av, b\rangle=G\}.$$
Assume $v\notin \Omega_a.$ Then $\langle a, bv\rangle$ is a complement of
$V$ in $G$. The fact that no complemented chief factor of $H$ is $H$-isomorphic to $V$ ensures that all the complements of $V$ in $G$ form a single conjugacy class (see \cite[Satz 3]{g1}), so there exists $w\in V$ such that
$(a,bv)=(a^w,b^w).$ In particular $w\in C_V(a)$ and $v=[b,w].$ This implies $|V\setminus \Omega_a|\leq |[b,C_V(a)]|\leq |C_V(a)|.$ Since we are assuming $C_V(a)|V|^2,$ then $(\Omega_a \times \Omega_b) \cap \Omega \neq \emptyset,$ and $\Gamma(G)$ contains $P_4$. So we may assume
\begin{equation}\label{cru}|\Omega_a||\Omega_b|\leq |V^2| - |\Omega|=|V|.
\end{equation}
In particular it follows from (\ref{omega}), (\ref{omegb}) and (\ref{omeg}), that $(p^t-p^{t-1})^2\leq p^t,$ i.e.
\begin{equation}\label{s3}
p^t\leq \left(\frac{p}{p-1}\right)^2.
\end{equation}
This implies
$p=2$ and $t=2$, i.e. $V\cong C_2\times C_2$. We have two possibilities:
\begin{enumerate}
\item [a)] $H/C_H(V) \cong \gl(2,2) \cong S_3$.
In this case $G/C_H(V)\cong S_4.$ Since
$$((1,2), (2,3,4), (1,4), (1,2,3))$$ is a four-vertex path in $S_4,$ the conclusion follows from
Lemma \ref{quozienti}.
\item [b)] $H/C_H(V) \cong C_3.$ In this case $C_V(a)=C_V(b)=\{0\}$, but then, by (\ref{omega}) and (\ref{omegb}), $|\Omega_a|,|\Omega_b|\geq 3$, in contradiction with (\ref{cru}).\qedhere
\end{enumerate}
\end{proof}
\begin{lemma}\label{nonnil}
Let $G$ be a non-nilpotent $2$-generated finite soluble group. If $\Gamma(G)$ is a cograph, then $G/\frat(G) \cong N \rtimes H,$ where $N$ is a faithful irreducible $H$-module and $H$ is cyclic of prime order.
\end{lemma}
\begin{proof}
Assume that $\Gamma(G)$ is a cograph. Then also $\Gamma(G/\frat(G))$ is a cograph. Moreover $G/\frat(G)$ is not nilpotent (otherwise $G$ would be nilpotent) so it is not restrictive to assume $\frat(G)=1.$ Since $G$ is
not nilpotent, there exists a minimal normal subgroup of $G$, say $N$, which is not central in $G$. Set $H=G/C_G(N).$ Then $N$ is a faithful irreducible $H$-module and the semidirect product $N\rtimes H$ is an epimorphic image of $G.$ By Lemma \ref{quozienti}, $\Gamma(N \rtimes H)$ is a cograph, so it follows from Lemma \ref{semidiretto} that $H$ is a cyclic group and consequently $\dim_{\End_H(N)}N=1$.
Let $K$ be a complement of
$N$ in $G.$ Since $G$ is $2$-generated and $\dim_{\End_H(N)}N=1$, it follows from \cite[Satz 4]{g2} that no complemented chief factor of $K$ is $K$-isomorphic to $N$. Since $G/C_G(N)$ is cyclic, there exists $x \in K$
such that $K=\langle x, C_K(N)\rangle.$ Moreover, since $K$ is $2$-generated, by Lemma \ref{modg} there exist $c_1,c_2 \in C_K(N)$ such that
$\langle xc_1, xc_2\rangle=K$. If $K$ is not cyclic, then the two elements $a=xc_1$ and $b=xc_2$ satisfy the assumptions of Lemma
\ref{semidiretto}. But this would imply that $\Gamma(G)$ is not a cograph, a contradiction.
With a similar argument we can prove that $K/C_K(N)$ is a $p$-group. Indeed assume $|K/C_K(N)|=rs$ with $r,s \geq 2$ and $(r,s)=1.$ There exist $y_1, y_2 \in K$ such that $\langle y_1, y_2\rangle=K$, $|y_1C_K(N)|=r$ and $|y_2C_K(N)|=s.$ We take $y_1, y_2$ in the role of $a, b$ in Lemma \ref{semidiretto} and we deduce that $\Gamma(G)$ is not a cograph. %Since $\frat(K)\cap C_K(N)\leq \frat(G)=1,$ we deduce that the order of $C_K(N)$ is coprime with $p$. This implies that $K=\langle x_1x_2\rangle,$ where
%$|x_1|$ is a $p$-power and $(|x_2|,p)=1.$ Take
So we may assume $K=\langle xy \rangle$ where $|x|$ is a $p$-power,
$y \in C_K(N)$ and $(|y|,p)=1.$ If $y\neq 1,$ then, for any
$1\neq n \in N,$ $(n,xy,ny,x)$ is a four-vertex path in $\Gamma(G).$ So $y=1$ and $K$ is a cyclic $p$-group. In particular $C_K(N)\leq \frat(K).$ However $\frat(K)\cap C_K(N)\leq \frat(G)=1,$ so we deduce that $C_K(N)=1.$
We have now proved that $K=\langle x \rangle$ is cyclic of order $p^t$, for some $t \in \mathbb N$ and $N$ is a faithful irreducible $K$-module. In particular $K$ acts fixed-point-freely on $N$. Choose $1\neq n\in N.$ Then $K$ and $K^n$ are two maximal subgroups of $G$ with trivial
intersection. If $t>1,$ then
$(x^p,x^n,x,(x^n)^p)$ is a four-vertex path in $\Gamma(G)$. Since $\Gamma(G)$ is a cograph we conclude $t=1.$
\end{proof}
\begin{proof}[Proof of Theorem \ref{gencog}] Assume that $\Gamma(G)$ is a cograph. If $G$ is nilpotent then, by Lemma \ref{abelian}, $G/\frat(G)$ is either a $p$-group or a cyclic group of order $p_1p_2$, where $p_1$ and $p_2$ are two different primes. In the first case $G$ is a $p$-group, in the second $G$ is a cyclic group and $p_1, p_2$ are the only prime divisors of $|G|.$ If $G$ is not nilpotent, then, by Lemma \ref{nonnil},
$G/\frat(G) \cong V \rtimes \langle x \rangle$ where $x$ has prime order
and $V$ is a faithful irreducible $\langle x \rangle$-module.
Conversely we have to prove that if $G$ satisfies (1), (2) or (3), then $\Gamma(G)$ is a cograph. If $(g_1,g_2,g_3,g_4)$ is a four-vertex path in $\Gamma(G)$, then either $(g_1\frat(G),$ $g_2\frat(G), g_3\frat(G), g_4\frat(G))$ is a four-vertex path in $\Gamma(G/\frat(G))$ or there exist $1\leq i < j \leq 4$ with $g_i\frat(G)=g_j\frat(G).$ However if the second possibility occurs, then there exists $k \in \{1,2,3,4\} \setminus \{i,j\}$ such that
$g_k$ is adjacent to $g_j$ but not to $g_i.$ This implies $G=\langle g_k, g_j\rangle=\langle g_k, g_j, \frat(G) \rangle = \langle g_k, g_i, \frat(G) \rangle < G,$ a contradiction. Therefore, to complete the proof of the theorem we may
assume $\frat(G)=1.$
Assume by contradiction that $(g_1,g_2,g_3,g_4)$ is a four-vertex path in $\Gamma(G)$. There are four possibilities to consider.
\begin{enumerate}[label=\alph*)]
\item $G \cong C_p.$ There exists $i\in \{1,2,3,4\}$ such that
$|g_i|=p,$ but then $g_i$ is adjacent to $g_j$ for any $j\neq i,$ a contradiction.
\item $G \cong C_p \times C_p.$ In this case $|g_1|=|g_2|=|g_3|=|g_4|=p.$ Since $g_1$ and $g_3$ are not adjacent in $\Gamma(G),$ $\langle g_1 \rangle=\langle g_3 \rangle.$ Moreover, since $g_3$ and $g_4$ are adjacent $\Gamma(G),$ $\langle g_3 \rangle\neq \langle g_4 \rangle.$ But then $\langle g_1 \rangle \neq \langle g_4 \rangle$ and $g_1$ and $g_4$ are adjacent in $\Gamma(G),$ a contradiction.
\item $G \cong C_{p_1} \times C_{p_2},$ with $p_1\neq p_2.$
There is no $i\in \{1,2,3,4\}$ such that
$|g_i|=p_1p_2,$ since this would imply $g_i$ adjacent to $g_j$ for any $j\neq i.$ It is not restrictive to assume $|g_1|=p_1.$ This would imply $|g_2|=p_2, |g_3|=p_1, |g_4|=p_2$, and consequently that $g_1$ and $g_4$ are adjacent, a contradiction.
\item $G \cong V \rtimes \langle x \rangle$ where $x$ has
order $p$
and $V$ is a faithful irreducible $\langle x \rangle$-module.
There exists a prime $q\neq p$ such that $V$ is an elementary abelian $q$-group and every non-trivial element $g$ of $G$ has order $p$ or
$q.$ Assume that $|g_1|=p.$ Then $\langle g_1 \rangle$ is the unique maximal subgroup of $G$ containing $g_1.$ Since $g_3$ and $g_4$ are not adjacent to $g_1,$ we must have $g_3,g_4 \in \langle g_1 \rangle$, but then $g_3,g_4$ are not adjacent in $\Gamma(G).$ So $|g_1|=q.$ For the same reason $|g_4|=q$ and consequently $|g_2|=|g_3|=p.$ But this would imply that $g_2$ and $g_4$ are adjacent.
\end{enumerate}
\end{proof}
\section{Perfect graphs}
\subsection{Preliminary results}
The results of this section strongly depend on the strong perfect graph theorem, that has been already mentioned in the introduction and can be stated in the following way \cite{crst}.
\begin{thm}
A graph is perfect if and only if it admits neither odd holes nor antiholes as induced subgraph.
\end{thm}
In the following, we will use $Y$ to denote the following graph:
\begin{center}
\begin{tikzpicture}
[scale=.6,auto=left,every node/.style={circle,fill=black!20}]
\node (n1) at (5,3.5) {$x_2$};
\node (n2) at (5,6.5) {$x_1$};
\node (n3) at (7,5) {$x_3$};
\node (n5) at (9,5) {$x_4$};
\foreach \from/\to in {n1/n2,n1/n3,n2/n3,n5/n3}
\draw (\from) -- (\to);
\end{tikzpicture}
\end{center}
Recall that the tensor product $\Gamma_1 \wedge \Gamma_2$ of two graphs $\Gamma_1$ and $\Gamma_2$ is the graph whose vertex set coincides with the cartesian product
of the vertex sets of $\Gamma_1$ and $\Gamma_2$ and where $(x_1,y_1)$ and $(x_2,y_2)$ are adjacent if and only if $x_1, x_2$ are adjacent in $\Gamma_1$ and
$y_1, y_2$ are adjacent in $\Gamma_2.$ If $G_1$ and $G_2$ are $2$-generated finite groups, then $\Gamma(G_1\times G_2)$ is a subgraph of $\Gamma(G_1) \wedge \Gamma(G_2)$, and $\Gamma(G_1\times G_2) \cong \Gamma(G_1) \wedge \Gamma(G_2)$ if $|G_1|$ and $|G_2|$ are coprime (see \cite[Lemma 2.5]{hl}).
\begin{thm}[{\cite[Theorem 3.2]{rav}}]\label{rv}
The tensor product $\Gamma_1 \wedge \Gamma_2$ of two graphs $\Gamma_1$ and $\Gamma_2$ is perfect if and only if either
\begin{enumerate}
\item $\Gamma_1$ or $\Gamma_2$ is bipartite, or
\item neither $\Gamma_1$ nor $\Gamma_2$ contain $Y$ or an odd $n$-hole with
$n\geq 5,$ as an induced subgraph.
\end{enumerate}
\end{thm}
\begin{rema}\label{yk3}Let $\Gamma_1\cong Y$ be a graph with vertex-set $\{x_1,x_2,x_3,x_4\}$ and $\Gamma_2 \cong K_3$ be a complete graph with
vertex-set $\{y_1,y_2,y_3\}.$ Then $$((x_1,y_1), (x_2,y_3), (x_3,y_1), (x_4,y_2), (x_3,y_3))$$ is a 5-hole in the tensor product $\Gamma_1 \wedge \Gamma_2.$
\end{rema}
Another remark that will be used in some of the proofs is that a 5-hole in a graph $\Gamma$ is also a 5-antihole. Indeed if $\{x_1,x_2,x_3,x_4,x_5\}$ is a subset of the vertices of a graph $\Gamma$ inducing a 5-hole and $(x_1,x_2,x_3,x_4,x_5)$ is a 5-cycle in $\Gamma$, then $(x_1,x_3,x_5,x_2,x_4)$ is a 5-cycle in the complement graph.
In this and in the following sections we will use the notations $g_1 \sim g_2$ and $g_1\nsim g_2$ to denote that $g_1$ and $g_2$ are adjacent, or non-adjacent, in $\Gamma(G).$
\begin{lemma}\label{qfra}
$\Gamma(G)$ is perfect if and only if $\Gamma(G/\frat(G))$ is perfect.
\end{lemma}
\begin{proof}
By the strong perfect graph theorem, it suffices to prove that if $m\geq 5,$
then $\Gamma(G)$ contains an $m$-hole or an $m$-antihole if and only if $\Gamma(G/\frat(G))$ has the same property. Since $\langle g_1\frat(G), g_2\frat(G)\rangle=G/\frat(G)$ if and only if $\langle g_1, g_2 \rangle=G,$ if the subset $\{x_1\frat(G),\dots,x_m\frat(G)\}$ induces an $m$-hole or an $m$-antihole in $\Gamma(G/\frat(G))$, then so does
$\{x_1,\dots,x_m\}$ in $\Gamma(G).$ Conversely, assume that
$\{x_1,\dots,x_m\}$ induces an $m$-hole or an $m$-antihole in $\Gamma(G).$ If $1\leq i< j\leq m,$ then there exists $k\in \{1,\dots,m\}\setminus \{i,j\}$ such that $x_k$ is adjacent to $x_i$ but not to $x_j$. In particular $x_i\frat(G)\neq x_j \frat(G)$ and $\{x_1\frat(G),\dots,x_m\frat(G)\}$ induces an $m$-hole or an $m$-antihole in $\Gamma(G/\frat(G)).$
\end{proof}
Let $I_n=\{1,\dots,n\}$ and consider the graph $\Delta_n$ whose vertices are the subsets of $I_n$ and where $J_1$ and $J_2$ are adjacent if and only if $J_1\cup J_2=I_n.$
\begin{lemma}\label{deltan}
The graph $\Delta_n$ is perfect if and only if $n\leq 4.$
\end{lemma}
\begin{proof}
If $n\geq 5,$ then $
(\{1,2,4,6,\dots,n\}, \{1,3,5,6,\dots,n\},$ $\{2,4,5,6,\dots,n\},$\linebreak $\{1,3,4,6,\dots,n\},$ $\{2,3,5,6,\dots,n\})$ is a 5-hole in $\Delta_n$ so $\Delta_n$ is not perfect. We may assume $n\leq 4.$ Let $m\geq 5$ be an odd integer
and assume that $X$ is a subset of the vertex-set of $\Delta_n$ inducing an $m$-hole or an $m$-antihole. Clearly $I_n \notin X.$ As a consequence, $\emptyset\notin X.$ Moreover if $\{i\}$ is a singleton, then $I_n\setminus\{i\}$ is the unique proper subset of $I_n$ adjacent to $\{i\}$, so $\{i\}\notin X$. So we have at most $2^n-n-2$ possible choices for an element of $X$. This implies that $n=4$ and $X$ consists of sets of cardinality 2 or 3. Since $I_4$ contains only four subsets of cardinality 3, it is not restrictive to assume $\{1,2\} \subseteq X.$ Note that
a subset of cardinality 3 is adjacent to all the other subsets of cardinality 3. So if $X$ induces an $m$-hole, then $X$ contains at most 2 (adjacent) subsets of cardinality 3. This implies that $X$ contains at least 3 subsets of cardinality 2, inducing a 3-vertex path. But this is impossible since a subset of cardinality 2 is adjacent to only one subset of cardinality 2. If $X$ induces an $m$-antihole, then it contains at least one subset of cardinality 2,
say $Y$, and this must be adjacent to another $m-3$ elements of $X$. However
there is a unique subset of cardinality 2 and two subsets of cardinality 3 adjacent to $Y$, hence $m-3\leq 3.$
But this implies $m=5$ and we may exclude this possibility since a $5$-antihole is also a $5$-hole, as noted above.
\end{proof}
\begin{lemma}\label{unicomax}
Let $G$ be a finite group and let $g\in G$ be an element which is contained in a unique maximal subgroup of $G$. Then $g$ cannot be the vertex of an $m$-hole or $m$-antihole in $\rg(G)$ with $m\geq 5$.
\end{lemma}
\begin{proof}
Let $M\leq G$ be the unique maximal subgroup containing $g$ and let $m\geq 5.$
Let $(g,a_2,\dots,a_m)$ be an $m$-hole. We have $g\nsim a_3,a_4$, which implies $a_3,a_4\in M$, so they cannot be adjacent in $\Gamma(G),$ a contradiction.
Let $(g,a_2,\dots,a_m)$ be an $m$-antihole. We have $g\nsim a_2,a_m$, which implies $a_2,a_m\in M$, so they cannot be adjacent in $\Gamma(G),$ a contradiction.
\end{proof}
\begin{lemma}\label{aiaj}
Let $m\geq5$ and suppose $(a_1,\dots,a_m)$ is an $m$-hole or an $m$-antihole in $\rg(G)$. If $\gen{a_i}=\gen{a_j}$, then $i=j$.
\end{lemma}
\begin{proof}
Let $i\neq j$ and $\gen{a_i}=\gen{a_j}$. We can assume without loss of
generality that $i=1$ and $2\leq j\leq \frac{m+1}{2}$. If $(a_1,\dots,a_m)$ is an $m$-hole, then $a_m\sim a_1$, and this implies $a_m\sim a_j$ and consequently $j=m-1$. But then $m-1\leq\frac{m+1}{2}$, hence $m\leq3$, a contradiction. If $(a_1,\dots,a_m)$ is an $m$-antihole, then $a_m\nsim
a_1$, and so $a_m\nsim a_j$ and we argue as before.
\end{proof}
\subsection{Nilpotent groups}
The aim of this subsection is to prove Theorem \ref{nilperf}.
First we prove the statement in the special case where $G$ is cyclic.
\begin{lemma}\label{ciclo}
Let $G$ be a finite cyclic group. Then $\Gamma(G)$ is perfect if and only
if $|G|$ is divisible by at most four different primes.
\end{lemma}
\begin{proof}
By Lemma \ref{qfra}, we may assume $\frat(G)=1$, so $|G|=p_1\cdots p_t$ where $p_1,\dots,p_t$ are distinct primes. Assume that $(a_1,\dots,a_m)$ is an $m$-hole or an $m$-antihole in $\Gamma(G).$ Let $\pi=\{p_1,\dots,p_t\}$ and for any $i\in \{1,\dots,t\}$, let $\pi_i$ be the set of prime divisors of $|a_i|$. By Lemma \ref{aiaj}, if $i\neq j$, then $\pi_i \neq \pi_j$, moreover
$a_i$ and $a_j$ are adjacent in $\Gamma(G)$ if and only if $\pi_i \cup \pi_j=\pi.$ This implies that $\Gamma(G)$ is perfect if and only if $\Delta_t$ is perfect, and the conclusion follows from Lemma \ref{deltan}.
\end{proof}
The proof of the general case requires some preliminary lemmas and remarks.
\begin{rema}\label{y1}
Let $p$ and $q$ be two different primes. If $P=\langle a_1, a_2 \rangle$ is a finite, $2$-generated, non-cyclic $p$-group and $Q=\langle b_1, b_2 \rangle$ is a finite, $2$-generated, non-cyclic $q$-group, then $\Gamma(P\times Q)$ contains an induced subgraph isomorphic to $Y:$
\begin{center}
\begin{tikzpicture}
[scale=.6,auto=left]%every node/.style={circle,fill=black!20}]
\node (n1) at (5,3.5) {\tiny{$(a_1,b_1)$}};
\node (n2) at (5,6.5) {\tiny{$(a_2,b_2)$}};
\node (n3) at (7,5) {\tiny{$(a_1a_2,b_1b_2)$}};
\node (n5) at (10,5) {\tiny{$(a_1,b_2)$}};
\foreach \from/\to in {n1/n2,n1/n3,n2/n3,n5/n3}
\draw (\from) -- (\to);
\end{tikzpicture}
\end{center}
\end{rema}
\begin{rema}\label{y2}
If $P=\langle a_1, a_2 \rangle$ is a finite, $2$-generated, non-cyclic finite $p$-group and $C=\langle x \rangle$ is a non-trivial finite cyclic group whose order is not divisible by $p$, then $\Gamma(P\times C)$ contains an induced subgraph isomorphic to $Y:$
\begin{center}
\begin{tikzpicture}
[scale=.6,auto=left]%every node/.style={circle,fill=black!20}]
\node (n1) at (5,3.5) {\tiny{$(a_1,1)$}};
\node (n2) at (5,6.5) {\tiny{$(a_2,x)$}};
\node (n3) at (7,5) {\tiny{$(a_1a_2,x)$}};
\node (n5) at (10,5) {\tiny{$(a_2,1)$}};
\foreach \from/\to in {n1/n2,n1/n3,n2/n3,n5/n3}
\draw (\from) -- (\to);
\end{tikzpicture}
\end{center}
\end{rema}
\begin{rema}\label{k3}
If $G$ is a $2$-generated finite group of order at least 3, then $\Gamma(G)$ contains an induced subgraph isomorphic to $K_3.$ In particular $\Gamma(G)$ is not a bipartite graph.
\end{rema}
\begin{proof}
If $G=\langle a, b\rangle$ is not cyclic, then we can take the subgraph
of $\Gamma(G)$ induced by $\{a,b,ab\}.$ If $G=\langle x\rangle,$ we can
take the subgroup induced by $\{1,x,x^{-1}\}.$
\end{proof}
\begin{lemma}\label{necc}
Let $G$ be a $2$-generated finite nilpotent group. If $\Gamma(G)$ is perfect, then the order of $G/\frat(G)$ is the product of at most four (not necessarily distinct) primes.
\end{lemma}
\begin{proof}
By Lemma \ref{qfra} we may assume $\frat(G)=1.$ For any prime divisor $p$ of $|G|$, the Sylow $p$-subgroup of $G$ is either cyclic of order $p$ or elementary abelian of order $p^2.$ If all the Sylow subgroups of $G$ are cyclic, then $G$ is cyclic and the conclusion follows from Lemma \ref{ciclo}. So we may assume that $G$ contains a non-cyclic Sylow $p$-subgroup, say $P$, of order $p^2.$ Let $K$ be a complement of $P$ in $G.$ Assume, by contradiction, that
$|K|$ is the product of at least three primes. If $K$ is not cyclic, then $K=Q_1\times Q_2 \times H$ where $Q_1, Q_2$ are Sylow subgroups, $Q_1$ is non-cyclic and $Q_2\neq 1.$
By Remarks \ref{y2} and \ref{k3}, $\Gamma(P\times Q_2)$ and $\Gamma(Q_1\times H)$ contain an induced subgraph isomorphic, respectively,
to $Y$ and $K_3.$ But then we deduce from Remark \ref{yk3} that
$\Gamma(G) \cong \Gamma(P\times Q_2) \wedge \Gamma(Q_1\times H)$ is not perfect.
So we may assume that $K=\langle x \rangle$ and that $|x|$ is divisible by at least three different primes $q_1, q_2, q_3.$
Let $\Omega$ be the set of the vertices $y$ of $\Gamma(K)$ with the property that $\langle y \rangle \neq K$ and let $\Lambda$ be the subgraph of $\Gamma(K)$ induced by $\Omega.$ Notice that the subgraph of $\Gamma(G)$ induced by the subset $P \times \Omega$ is isomorphic to $\Gamma(P) \wedge \Lambda$ and that $\{ x^{q_1},x^{q_2},x^{q_3},x^{q_1q_2}\}$ induces a subgraph of $\Lambda$ isomorphic to $Y$. But then, again by Remark \ref{yk3},
$\Gamma(P) \wedge \Lambda$, and consequently $\Gamma(G)$, contains a 5-hole.
\end{proof}
\begin{lemma}\label{pp}
Let $G$ be a non-cyclic $2$-generated finite $p$-group. Then $\Gamma(G)$ is perfect and does not contain an induced subgraph isomorphic to $Y$.
\end{lemma}
\begin{proof} %By Lemma \ref{qfra}, we may assume $\frat(G)=1$, i.e. $G\cong C_p\times C_p.$
We have $G/\frat(G)\cong C_p\times C_p.$ If $g$ is a non-isolated vertex of $\Gamma(G)$, then $|g\frat(G)|=p$ and $\langle g \rangle$ is the unique maximal subgroup of $G$
containing $g.$ It follows from Lemma \ref{unicomax} that $\Gamma(G)$ contains no $m$-hole or $m$-antihole with $m\geq 5$, so it follows from the strong perfect graph theorem that $\Gamma(G)$ is perfect. Now assume by contradiction that $\{g_1,g_2,g_3,g_4\}$ induces a subgraph of $\Gamma(G)$
isomorphic to $Y.$ We may order these four vertices in such a way that $g_1$ and $g_2$ are adjacent, while $g_4$ is not adjacent to $g_1$ nor to $g_2.$ The latter condition implies $\langle g_4\frat(G) \rangle = \langle g_1\frat(G) \rangle
= \langle g_2\frat(G) \rangle,$ in contradiction with $\langle g_1, g_2\rangle=G.$
\end{proof}
\begin{proof}[Proof of Theorem \ref{nilperf}]
By Lemma \ref{qfra} we may assume that $\frat(G)=1.$ By Lemma \ref{necc}, the condition that $|G|$ is the product of at most 4 primes is necessary for $\Gamma(G)$ to be perfect. We have to prove that this condition is also sufficient. By Lemma \ref{ciclo}, we may assume that $G$ is not cyclic. This means that $G=P \times K,$
where $P \cong C_p\times C_p$ for a suitable prime $p$ and $K$ is a nilpotent group whose order is coprime with $p$ and is the product of at most
two primes. By Lemma \ref{pp}, we may assume $K\neq 1.$
If $K$ is not cyclic, then $K\cong C_q \times C_q,$ for a prime $q\neq p$ and $\Gamma(G)\cong \Gamma(P) \wedge \Gamma(Q)$ is perfect, as a consequence of Theorem \ref{rv} and Lemma \ref{pp}.
The previous argument does not work if $K=\langle g\rangle$ is cyclic.
Indeed, $\Gamma(G)$ and $\Gamma(P) \wedge \Gamma(K)$ are not isomorphic. For example, if $P=\langle a_1, a_2\rangle$, then
$(a_1,g)$ and $(a_2,g)$ are adjacent in $\Gamma(G)$ but not in $\Gamma(P) \wedge \Gamma(K)$. However we can argue in the following way. Assume that $X\subseteq G$ induces an $m$-hole or an $m$-antihole, with $m\geq 5.$ If $K=\langle g \rangle$ and $y \in P,$ then either $(y,g)$ is an isolated vertex of $\Gamma(G)$ (when $y=1$), or $\langle (y,g)\rangle$ is the unique maximal subgroup of $G$ containing $(y,g).$ In both the cases, since the vertices of an $m$-hole or an $m$-antihole are not isolated, Lemma \ref{unicomax}
implies that $(y,g) \notin X.$ In particular, this implies that $K$ has composite order (no element of $K$ could belong to $X$), so it remains to handle
the case where $K$ is cyclic of order $r\cdot s$ for distinct primes
$r$ and $s$. In this case, we consider the subgraph $\Delta$ of $\Gamma(K)$ induced by the elements of $K$ of prime order. From what we said above, it follows that $X$ induces an $m$-hole or $m$-antihole in $\Gamma(G)$ if and only if it induces an $m$-hole or $m$-antihole in $\Gamma(P) \wedge \Delta.$ This would imply that $\Gamma(P) \wedge \Delta$ is not perfect, and consequently, by
Theorem \ref{rv} and Lemma \ref{ciclo}, that $\Delta$ contains an induced subgraph isomorphic to $Y.$ So assume by contradiction that $\{g_1,g_2,g_3,g_4\}$ induces a subgraph of $\Delta$ isomorphic to $Y.$ We may order these four vertices in such a way that $g_1$ and $g_2$ are adjacent while $g_4$ is not adjacent to $g_1$ nor to $g_2.$ The latter condition implies $\langle g_4 \rangle = \langle g_1 \rangle
= \langle g_2 \rangle,$ in contradiction with $\langle g_1, g_2\rangle=K.$
\end{proof}
\subsection{The dihedral group}
In this subsection we determine when the dihedral group
\[
D_n=\gen{\rho,\iota\mid \rho^n=\iota^2=1, \rho^\iota=\rho^{-1}}
\]
has a perfect generating graph. We start with a preliminary lemma.
\begin{lemma}\label{c2c2}
Let $N$ be a normal subgroup of $G$ \st $G/N\cong C_2\times C_2$. Then $\rg(G)$ has no $m$-antihole with $m\geq7$.
\end{lemma}
\begin{proof}
Let $a,b,c\in G$ be \st $G/N\coloneqq \{N,aN,bN,cN\}$. Suppose $(a_1,\dots,a_m)$ is an $m$-antihole in $\Gamma(G).$ Since $a_1$ and $a_3$ are adjacent vertices of $\Gamma(G),$ we may assume without loss of generality that $a_1N=aN$ and $a_3N=bN$. Since $a_5,\dots,a_{m-1}$ are adjacent to both $a_1$ and $a_3$, it follows that $a_5N,\dots,a_{m-1}N$ are all equal to $cN$. In particular, if $m>7$, then $a_5N=a_7N$ implies $a_5\nsim a_7$, a contraction. So we may assume $m=7$. Since $a_4\sim a_1$, $a_4\sim a_6$, $a_1N=aN$
and $a_6N=cN$, we must have $a_4N=bN$. Analogously, from $a_2\sim a_4$ and $a_2\sim a_6$ it follows that $a_2N=aN$. But now consider $a_7N:$ $a_7N\neq aN$ since $a_7\sim a_2$, $a_7N\neq bN$
since $a_7\sim a_3$ and $a_7N\neq cN$ since $a_7\sim a_5$. This would imply $a_7\in N$, and consequently that $a_7$ is an isolated vertex of $\Gamma(G),$ a contradiction.
\end{proof}
\begin{proof}[Proof of Theorem \ref{diedrale}] Let $m\geq5$ be odd. We start with two general remarks.
\begin{enumerate}[label=(\alph*)]
\item \label{121} No rotation $\rho^i$ can appear in an $m$-hole or $m$-antihole. Indeed if $|\rho^i| 3$. Then $\Gamma(G)$ contains a 5-hole.
\end{prop}
\begin{proof} We may assume $q\notin \{4, 5,9\},$ since
$\psl_2(4)\cong\psl_2(5)\cong A_5$ and $\psl_2(9)\cong A_6$.
The group $G$ has a faithful 2-transitive action on the $q+1$ points of the 1-dimensional projective space $\pg(1,q)$
over the field $\mathbb{F}_q$ with $q$ elements.
Let $A,B,C,D$ be four distinct points of $\pg(1,q)$. The subgroups $H=\stab_G(A)\cap\stab_G(B)$ and $K=\stab_G(C)\cap\stab_G(D)$ are cyclic of order $u=(q-1)/(q-1,2)$. Notice that $\langle H, K\rangle$
connot be contained in the stabilizer of an element of $\pg(1,q),$ since the only element of $G$ which fixes three distinct points is the identity. The list of the maximal subgroups of $G$ is well-known (see for example \cite[Tables 8.1, 8.2]{max_simple}). In particular if $q \notin\{7,11\}$, then no maximal subgroup of $G$, except from a point stabilizer, contains two distinct cyclic subgroups of order $u$. This implies $G=\langle H,K \rangle$ and we can use Lemma \ref{stabilizer} to conclude.
Finally, if $q=7$, then $G\leq S_8$ and the following is a 5-hole in $\Gamma(G):$
$$((2,3,4)(5,8,7), (1,4,5)(3,7,6),
(2,7,8)(3,6,5), (1,2,4)(6,7,8),
(1,2,5,7)(3,8,6,4)).$$
%$$\begin{align*}
%(&(2,3,4)(5,8,7),\\
%&(1,4,5)(3,7,6),\\
%&(2,7,8)(3,6,5),\\
%&(1,2,4)(6,7,8),\\
%&(1,2,5,7)(3,8,6,4)).
%\end{align*}
%is a $5$-hole in $\rg(\psl_2(7))$.
Similarly, if $q=11,$ then $G\leq S_{12}$ and the following is
a 5-hole in $\Gamma(G):$
$$
((3,9,5,11,7)(4,10,6,12,8),
(1,6,3,4,12)(2,11,9,10,7),
(1,3,8,5,4)(6,7,9,12,10),$$
$$
(2,12,11,8,3)(4,7,9,10,6),
(1,9,6,7,5)(2,4,12,3,10)).
\qedhere$$
\end{proof}
\begin{prop}
Let $G=\psu_3(q),$ with $q> 2$. Then $\Gamma(G)$ contains a 5-hole.
\end{prop}
\begin{proof} Let $d=(q+1,3).$
The group $G$ is a 2-transitive group of permutations of the set $\Omega$ of the $q^3+1$ points of the corresponding polar space. If $A_1, A_2$ are two distinct points of $\Omega,$ then $\stab_G(A_1)\cap\stab_G(A_2)$ is a cyclic group of order $(q^2-1)/d$. Moreover $A_1$ and $A_2$ are the only points fixed by $\stab_G(A_1)\cap\stab_G(A_2)$ and $\stab_G(A_1)\cap\stab_G(A_2)$ acts on the remaining $q^3-1$ point with $q\cdot d$ orbits of size $(q^2-1)/d$ and one orbit of size $q-1$ (this information can be deduced for example from the description of the action of $G$ on $\Omega$ given in \cite[Section 7.7, pages 248-249]{dm}).
The statement can be directly proved using GAP if $q\leq 5,$ by searching elements in the intersections of stabilizers, in such a way to reproduce the situation of Lemma \ref{stabilizer}; so we may assume $q\geq 7.$
Let $A_1, A_2, A_3, A_4$ be four distinct points of $\Omega$ and consider $H=\stab_G(A_1)\cap\stab_G(A_2)$ and $K=\stab_G(A_3)\cap\stab_G(A_4)$. %Notice that $H\neq K$, since the only element of $G$ which fixes three distinct points is the identity.
The list of the maximal subgroups of $G$ is well-known (see for example \cite[Tables 8.5, 8.6]{max_simple}). In particular, since $q\geq 7,$ if $M$ is a maximal subgroup of $G$ containing an element of order $(q^2-1)/d,$ then either $M$ is a point-stabilizer or $M = X/Y$ with $X \cong \gu_2(q)$ and $Y$ cyclic of order $d.$ In the first case
$M$ cannot contain both $H$ and $K,$ since $H$ fixes only $A_1$ and $A_2$ and $K$ fixes only $A_3$ and $A_4.$ In the second case $Z(M)$ is cyclic of order $(q+1)/d$ and fixes precisely $q+1$ elements of $\Omega$ and any element of order $q^2-1$ contained in $M$ acts on the set of these $q+1$ elements with two fixed points and an orbit of cardinality $q-1.$ In particular, if we choose $A_3, A_4$ such that they don't belong to the orbit of size $q-1$ of $H$, then $G=\langle H, K \rangle$. With this choice of $A_3$ and $A_4,$ choose $A_5$ distinct from $A_1, A_2, A_3, A_4$ and not contained in the orbit of size $q-1$ of
$\stab_G(A_i)\cap\stab_G(A_j)$, for any $1\leq i < j\leq 4.$
We can use Lemma \ref{stabilizer} to conclude.
\end{proof}
\begin{prop}\label{suzuki}
Let $q=2^{2n+1}$ with $n\geq 1.$ If $G={^2B}_2(q)$ is a Suzuki group, then $\rg(G)$ contains a 5-hole.
\end{prop}
\begin{proof}
The group $G$ has a faithful 2-transitive action on an ovoid $\Omega$ in a 4-dimensional symplectic geometry over $\mathbb F_q.$ Up to conjugacy,
the maximal subgroups of $G$ are as follows (for example, see \cite[Table 8.16]{max_simple}):
\begin{enumerate}[label=(\arabic*)]
\item\label{3281} the stabilizer of $\omega \in \Omega$ (the Borel subgroup of order $q^2(q-1)$);
\item \label{3282} the dihedral group of order $2(q-1)$;
\item \label{3283} $C_{q+\sqrt{2q}+1}\rtimes C_4$;
\item \label{3284}$C_{q-\sqrt{2q}+1}\rtimes C_4$;
\item\label{3285} ${^2B}_2(q_0)$, where $q=q_0^r$, $r$ is prime and $q_0>2$.
\end{enumerate}
If $\omega_i$ and $\omega_j$ are distinct elements of $\Omega,$ then $\stab_G(\omega_i)\cap\stab_G(\omega_j)$ is cyclic of order $q-1$. Let $x$ be a generator of this cyclic group. Next choose $\omega_l$ and $\omega_k$ in $\Omega$ \st $\omega_i,\omega_j,\omega_k,\omega_l$ are all distinct, and let $y$ be a generator of $\stab_G(\omega_k)\cap\stab_G(\omega_l)$. Since the only element fixing three points is the identity, we have that $\gen{x}\neq \gen{y}$. Consider the subgroup $H\coloneqq \gen{x,y}$. If $H$ is a proper subgroup, it is contained in a maximal subgroup. However $H$ cannot be contained in subgroups of type \ref{3283}, \ref{3284} and \ref{3285}, since they do not contain elements of order $q-1$. Since $\gen{x}\neq\gen{y}$ we can also rule out the possibility that $H$ is contained in a subgroup of type \ref{3282}.
Finally, if $H\leq\stab_G(\omega)$, for some $\omega\in\Omega$,
then either $x$ or $y$ must fix three different points, which is impossible. Therefore $H=G$ and we can use Lemma \ref{stabilizer} to construct a $5$-hole.
\end{proof}
\begin{prop}\label{ree}
Let $q=3^{2n+1}$ with $n\geq 1.$ If $G\coloneqq {^2G_2}(q)$, then $\Gamma(G)$ contains a 5-hole.
\end{prop}
\begin{proof}
The group $G$ has a faithful 2-transitive action on an ovoid $\Omega$ in a 7-dimensional orthogonal geometry over $\mathbb F_q.$ The maximal subgroups of $G$ are as follows, up to conjugacy (see for example \cite[Table 8.43]{max_simple}):
\begin{enumerate}[label=(\arabic*)]
\item\label{3291} the stabilizer of $\omega \in \Omega$ (the Borel subgroup of order $q^3(q-1)$);
\item \label{3292} the centralizer of an involution, which is isomorphic to $C_2\times\psl_2(q)$;
\item \label{3293} the normalizer of a four-group, which is isomorphic to
$(2^2 \times D_{(q+1)/4})\rtimes3;$
\item\label{3294} $C_{q+\sqrt{3q}+1}\rtimes C_6$;
\item\label{3295} $C_{q-\sqrt{3q}+1}\rtimes C_6$;
\item\label{3296} ${^2G}_2(q_0)$, where $q=q_0^r$ and $r$ prime.
\end{enumerate}
The intersection of two different point-stabilizers is cyclic with order $q-1$. Moreover any involution $t$ in $G$ fixes precisely $q + 1$ points in $\Omega$, and the set of these $q+1$ elements is called the block of $t.$ Any two blocks can intersect in at most 1 point and any two points are pointwise fixed by a unique involution.
Choose $\omega_1,\dots,\omega_5\in\Omega$ all distinct in the
following way: $\omega_1$, $\omega_2$ and $\omega_3$ are chosen randomly and let $\Omega_{i,j}$ be the unique block which contains $\omega_i$ and $\omega_j$. Since $|\Omega|=q^3+1$ and a block has cardinality $q+1$, it is possible to choose $\omega_4\in\Omega\setminus\Omega_{2,3}$ and $\omega_5\in\Omega\setminus(\Omega_{3,4}\cup\Omega_{1,2})$. Since the block containing two elements is unique, we have that four of these five elements never belong to the same block.
Let $\omega_i,\omega_j,\omega_k,\omega_l$ be four of these five elements. Let $x$ be a generator of $\stab_G(\omega_i)\cap\stab_G(\omega_j)$ and $y$ a generator of $\stab_G(\omega_l)\cap\stab_G(\omega_k)$ and consider $H\coloneqq \gen{x,y}$. The subgroup $H$ cannot be contained in maximal subgroups of type~\ref{3293}, \ref{3294}, \ref{3295} and \ref{3296}, since these maximal subgroups do not contain elements of order $q-1$. There are no elements in $G$ of order $q-1$ which fix three distinct elements on $\Omega$, so $H$ is not contained in maximal subgroups of type \ref{3291}. Therefore, if $H