Proof Let $f_0=\gcd (f_1,\ldots ,f_k)$ . We observe that if two vertices u and v are adjacent then $f_0$ divides $u-v$ . Now since $G_f(D)$ is connected, there is a path connecting $0$ and $1$ . This implies that $f_0$ divides $1-0=1$ . Hence, $\gcd (f_1,\ldots ,f_k)=1$ .

Proof Let $R= {\mathbb {F}}_q[x]/(f)$ . We need to show that $R= \langle S_{D} \rangle $ the abelian group generated by $S_{D}$ . Let $ a \in R.$ Because $\gcd (f_1, f_2, \ldots , f_k)=1$ , we can find $a_1, a_2, \ldots , a_k \in R$ such that

$$\begin{align*}a = \sum_{i=1}^k a_i f_i.\end{align*}$$

Since $G_{f}(\{1 \})$ is connected, for each $1 \leq i \leq k$ , we can find write

$$\begin{align*}a_i = \sum_{j=1}^{n_i} m_{ij} s_{ij}, \end{align*}$$

where $m_{ij} \in {\mathbb {Z}}$ and $s_{ij} \in R^{\times }.$ Consequently, we can write

$$\begin{align*}a = \sum_{i=1}^k \sum_{j=1}^{n_i} m_{ij} s_{ij} f_i. \end{align*}$$

Since $f_i\mid f$ , we see that $\gcd (s_{ij} f_i, f)= f_i \in D$ . This shows that $a \in \langle S_{D} \rangle $ . Since this is true for all a, we conclude that $R= \langle S_{D} \rangle $ .

Proof Let $m = \gcd (h,f).$ We need to show that $\gcd (h,g) = \gcd (m,g).$ We first claim that $\gcd (h,g) \mid \gcd (m,g).$ By definition, $\gcd (h,g) \mid g.$ We also have ${\gcd (h,g) \mid \gcd (h,f)=m}.$ Therefore, $\gcd (h,g) \mid \gcd (m,g).$

Conversely, we claim that $\gcd (m,g) \mid \gcd (h,g).$ This is clear since $m\mid h$ .

In summary, we have $\gcd (m,g) \mid \gcd (h,g)$ and $\gcd (h,g) \mid \gcd (m,g).$ This shows that $\gcd (m,g)=\gcd (h,g).$

Proof Suppose that $a \in S_{D}.$ Then, there exists i such that $\gcd (a,f)=f_i.$ By Lemma 3.5, we know that

$$\begin{align*}\gcd(a,g) = \gcd(\gcd(a,f), g) = \gcd(f_i,g).\end{align*}$$

This shows that $a \in S_{\overline {D}}.$ We conclude that $\Phi _{f,g}(S_{D}) \subseteq S_{\overline {D}}$ .

Proof Let $\bar {a},\bar {b}$ be two vertices in $G_{g}(\overline {D}).$ Since $\Phi _{f,g}$ is surjective, we can find ${a, b \in {\mathbb {F}}_q[x]/(f)}$ such that $\Phi _{f,g}(a)=\bar {a}, \Phi _{f,g}(b) = \bar {b}.$ Since $G_{f}(D)$ is connected, there is a path P from a to $b.$ By Proposition 3.6, $\Phi _{f,g}(P)$ is a path from $\bar {a}$ to $\bar {b}.$ This shows that $G_{g}(\overline {D})$ is connected as well.

Proof By Corollary 3.7, we know that if $G_{f}(D)$ is connected then $(1)$ and $(2)$ holds. Conversely, let us assume that $(1)$ and $(2)$ both hold. We will show that $G_{f}(D)$ is connected. This is equivalent to showing that $R: = {\mathbb {F}}_q[x]/(f) = \langle S_D \rangle .$

The key idea of this proof is similar to the proof for Theorem 3.2. The main difficulty is to deal with the fact that $G_{f}(\{1 \})$ is not connected in this case. We will do this step by step.

We first claim that if $g \in R$ such that $x(x+1) \mid g$ then $g = s_1 +s_2$ , where $s_1, s_2 \in R^{\times }.$ For an element $s \in R$ , s is a unit if and only $\Phi ^{\text {ss}}(s) \in (R^{\text {ss}})^{\times }$ where $R^{\text {ss}}= R/J(R)$ is the semisimplification of R (see [Reference Chudnovsky, Cizek, Crew, Mináč, Nguyen, Spirkl and Tân9, Proposition 4.30]). Therefore, for this statement, we can assume that $R = R^{\text {ss}}$ ; namely, f is a squarefree polynomial. If we write $f = x(x+1)h$ , where $\gcd (x(x+1),h)=1$ then we have the isomorphism

$$\begin{align*}R \cong {\mathbb{F}}_2[x]/(x(x+1)) \times {\mathbb{F}}_2[x]/(h). \end{align*}$$

Under this isomorphism, g is sent to $(0, g_1)$ , where $g_1 \in {\mathbb {F}}_2[x]/(h).$ Since $F_2[x]/(h)$ is a product of fields of order bigger than $2$ , every element in it can be written as the sum of two units; say $g_1 = t_1+t_2$ , where $t_1, t_2 \in ({\mathbb {F}}_2[x]/(f))^{\times }.$ We then see that $g =s_1+s_2$ where $s_1= (1,t_1)$ and $s_2 = (1, t_2)$ . By definition $s_1, s_2 \in R^{\times }.$

We now claim that if $g \in R$ such that $x(x+1) \mid g$ then $g \in \langle S_{D} \rangle .$ Since $\gcd (f_1,f_2,\ldots , f_k)=1$ , we can find $a_1, a_2, \ldots , a_k\in R$ such that

$$\begin{align*}a_1f_1+a_2f_2+\cdots+ a_kf_k=1.\end{align*}$$

Multiplying both sides with g, we get $g = \sum _{i=1}^k a_ig f_i.$ Since $x(x+1) \mid a_ig$ , we can write $a_i g = s_{1i}+s_{2i}$ , where $s_{1i}, s_{2i} \in R^{\times }.$ This shows that

(3.1) $$ \begin{align} g = \sum_{i=1}^k (s_{1i}f_i +s_{2i}f_i). \end{align} $$

Since $s_{1i}, s_{2i} \in R^{\times }$ , $s_{1i}f_i, s_{2i}f_i \in S_{D}.$ This shows that $g \in \langle S_{D} \rangle .$

Finally, let g now be an arbitrary element in R. We claim that $g \in \langle S_D \rangle .$ By our assumption, the graph $G_{x(x+1)}(S_{\bar {D}})$ is connected, $0$ and $\Phi _{f,x(x+1)}(g)$ are connected by a path. Consequently, we can write

$$\begin{align*}g \equiv \sum_{i} n_i \gcd(h_i, x(x+1))\quad \pmod{x(x+1)}, \end{align*}$$

where $n_i \in {\mathbb {Z}}$ and $\gcd (h_i, f) \in D$ . We can check that over ${\mathbb {F}}_2[x]$

$$\begin{align*}\gcd(h, x(x+1)) \equiv h\quad \pmod{x(x+1)},\end{align*}$$

for all $h \in {\mathbb {F}}_2[x].$ Therefore, we can write

$$\begin{align*}g \equiv \sum_{i} n_i h_i\quad \pmod{x(x+1)}. \end{align*}$$

By the previous case, we know that $g- \sum _{i=1}^k n_i h_i \in \langle S_D \rangle .$ This shows that $g \in \langle S_D \rangle $ as well. Since this is true for all g, we conclude that $R = \langle S_D \rangle .$

Proof (1) Let us consider the first part of this lemma. Because $G_{f}(D)$ is bipartite, we can write

$$\begin{align*}V(G_{f}(D)) = A \bigsqcup B \end{align*}$$

where $A,B$ are two independent sets in $G_{f}(D).$ Without loss of generality, we can assume that $0 \in A$ . We claim that $A=I$ . By the proof of [Reference Biswas5, Proposition 2.6], we know that A is a subgroup of $(R,+)$ of index $2.$ By definition, if $h_i \in S_D$ , then $(0,h_i) \in E(G_{f}(D))$ . Because A and B are disjoint independent set in $G_{f}(D)$ , $h_{i} \in B$ . Furthermore, since A is a subgroup of index $2$ in R, $h_i + h_j \in A$ for all $h_i,h_j \in S_D.$ Consequently, we must have $I \subseteq A.$

By our assumption that $G_{f}(D)$ is connected we know that $R = \langle S_D \rangle $ and hence ${I \sqcup I_1 = \langle S_D \rangle = R}.$ Clearly, if $a\in R\setminus I=I_1$ then $2a\in I$ . From this, we can see that I is a subgroup whose index is at most $2$ in R. Additionally, because $I \subseteq A$ and A has index $2$ in R, we must have that $I=A$ and $I_1 = B.$

(2) Suppose that $G_{f}(\{1\})$ is connected. We will show that I is an ideal in R as well. The idea is similar to the proof of Theorem 3.2 so we will be brief. Specifically, we note that for each $s \in R^{\times }$ , $sI = I.$ Since $\langle R^{\times } \rangle =R$ , this shows that $aI \subseteq I$ for all $a \in R.$ We conclude that I is an ideal in R.

(3) Finally, part $(3)$ follows from Eq. (3.1).

Proof If ${\mathbb {F}}_q \neq {\mathbb {F}}_2$ or $\gcd (x(x+1),f)=1$ , we know that $G_{f}(\{1\})$ is connected by Proposition 3.3. Furthermore, ${\mathbb {F}}_q[x]/(f)$ has no ideal of index $2.$ By Lemma 4.1, we conclude that $G_{f}(D)$ is not bipartite.

Proof Without loss of generality, we can assume that $x \mid f$ but $x+1 \nmid f.$ First, let us assume that $x \nmid f_i$ for all $1 \leq i \leq k$ . In this case, we can see that $A = xR$ and $B = 1+xR$ are independent subsets in $G_{f}(D)$ such that $V(G_{f}(D)) = A \bigsqcup B.$ This shows that $G_{f}(D)$ is bipartite.

Conversely, let us assume that $G_{f}(D)$ is bipartite. We claim that $x \nmid f_i$ for all ${1 \leq i \leq k}$ . Since $x(x+1) \nmid f$ , by Theorem 3.2 and Proposition 3.3, we know that $G_{f}(\{1\})$ is connected. Therefore, by Lemma 4.1, there exists an ideal I of index $2$ in R such that I is an independent set in $G_{f}(D).$ We remark that since the only ideal of index $2$ in R is $xR$ , $I=xR$ . Because $0 \in I$ and I is independent we must have

$$\begin{align*}xR \cap \{f_1, f_2, \ldots, f_k \} = \emptyset. \end{align*}$$

In other words, $x \nmid f_i$ for all $1 \leq i \leq k.$

Proof Suppose that $|\overline {D}| = 2$ . We claim that $G_{f}(D)$ is bipartite. Because $G_{f}(D)$ is connected, we know by Theorem 3.8 that $|\overline {D} \setminus \{x(x+1)\}| \geq 2.$ This shows that $\overline {D} \neq \{1, x(x+1) \}.$ We can check that $\overline {D}$ must be one of the following sets $\{1, x\}$ , $\{1, x+1 \}$ , $\{x, x+1 \}.$

First, we consider the case that $\overline {D} = \{1, x+1 \}$ . In this case, $V(G_{f}(D)) = xR \bigsqcup (1+xR)$ is a decomposition of $G_{f}(D)$ into a disjoint union of two independent sets. Similarly, if $\overline {D}=\{1, x\}$ then $V(G_{f}(D)) = (x+1)R \bigsqcup (1+(x+1)R)$ is a decomposition of $G_{f}(D)$ into a disjoint union of two independent sets. Now, suppose that $\overline {D} = \{x, x+1 \}.$ Let

$$\begin{align*}A = \{g \in R| g(0) = g(1)\}, \end{align*}$$

and

$$\begin{align*}B = \{g \in R : g(0) \neq g(1) \} = x + A.\end{align*}$$

We can check that if $a_1, a_2 \in A$ then $\gcd (a_1-a_2, x(x+1)) \in \{1, x(x+1) \}.$ By definition, $(a_1, a_2) \not \in E(G_{f}(D)).$ This shows that A is an independent set in $G_{f}(D)$ . Similarly, B is an independent set in $G_{f}(D)$ as well. We conclude that $G_{f}(D)$ is bipartite.

Conversely, suppose $G_{f}(D)$ is bipartite. We claim that $|\overline {D}| =2.$ By Lemma 4.1, the subgroup

$$\begin{align*}I = \left\{ \sum_{i} n_i h_i : n_i \in {\mathbb{Z}}, h_i \in S_D \text{ and} \quad \sum_{i=1} n_i \equiv 0\quad \pmod 2 \right\},\end{align*}$$

is an independent set in $G_{f}(D).$ Furthermore, by part $(3)$ of Corollary 3.7, we know that $x(x+1)R \subset I.$ Because $0$ is not connected to any node in I, we must have ${x(x+1)R \cap S_{D} = \emptyset }$ . Consequently, $x(x+1) \not \in \overline {D}.$ Suppose to the contrary that $|\overline {D}| \geq 3$ . We then have $\overline {D} = \{1, x, x+1 \}.$ This implies that $G_{x(x+1)}(\overline {D})$ is the complete graph $K_4.$ In $K_4$ , there is a path of length $2$ from $0$ to any other vertices. From this property, we conclude that for each $g \in R$ , we can write

$$\begin{align*}g \equiv \gcd(h_1, x(x+1)) + \gcd(h_2, x(x+1))\quad \pmod{x(x+1)}, \end{align*}$$

for some $h_1, h_2 \in S_D$ . We then conclude that $g-h_1-h_2 \in x(x+1)R \subset I$ . By the definition of I, $h_1+h_2 \in I$ , we conclude that $g \in I $ as well. This shows that $I=R$ , which is a contradiction.

Proof Since $a \in ({\mathbb {F}}_q[x]/(f))^{\times }$ , $m_a$ is an automorphism of $({\mathbb {F}}_q[x]/(f), +)$ . Furthermore, $m_a$ preserves $S_D$ ; i.e., $a S_{D} = S_D.$ As a result, $m_a$ is an automorphism of $G_{f}(D).$

Proof Clearly $(2)$ implies $(1)$ . Let us now prove $(1)$ implies $(2)$ . The proof that we discuss here is quite similar to the one that we gave for [Reference Chudnovsky, Cizek, Crew, Mináč, Nguyen, Spirkl and Tân9, Theorem 4.1] and Theorem 3.2. Because $G_f(D)$ is not prime, we can find a maximal homogenous set H containing $0$ . By [Reference Chudnovsky, Cizek, Crew, Mináč, Nguyen, Spirkl and Tân9, Theorem 3.4], we know that H is a subgroup of ${\mathbb {F}}_q[x]/(f)$ . We claim that it is an ideal as well. By Proposition 5.1, we conclude that $aH = H$ for all $a \in ({\mathbb {F}}_q[x]/(f))^{\times }.$ Furthermore, since $G_{f}(\{1\})$ is connected, $aH \subseteq H$ for all $a \in {\mathbb {F}}_q[x]/(f)$ as well. This shows that H is an ideal in ${\mathbb {F}}_q[x]/(f).$

Proof By replacing $a,b,c,f$ by $\frac {a}{m}, \frac {b}{m}, \frac {c}{m}, \frac {f}{m}$ , we can assume that $m=1.$ Because $\gcd (b,c)=1$ , we can find $t_1$ such that $c \mid a-bt_1.$ Let us write $a-bt_1 = a_1c.$ We will look for $t = t_1 +c t_2$ such that the condition $\gcd (a-bt, f)=c$ holds. By our choices of $t_1, t_2$ , this is equivalent to

$$\begin{align*}c= \gcd(a-b(t_1+ct_2),f) = \gcd(a_1c - b t_2 c, f) = c \gcd(a_1-b t_2, \frac{f}{c}). \end{align*}$$

We remark that the relation $a-bt_1 = a_1 c$ and the fact that $\gcd (a,b)=1$ imply that $\gcd (a_1, b)=1.$ By the Chinese remainder theorem, we can find $t_2$ such that ${\gcd (a_1 - b t_2, \frac {f}{c})=1}$ .

Proof Every element in $I_g$ can be written in the form $gm$ for a unique $m \in {\mathbb {F}}_q[x]/(f/g)$ . Therefore, we have a natural map $I_g \to {\mathbb {F}}_q[x]/(f/g)$ sending $gm \mapsto m.$ Furthermore, for two elements $ga, gb \in I_g$ , we have

$$\begin{align*}\gcd(ga-gb, f) = g \gcd(a-b, \tfrac{f}{g}). \end{align*}$$

Therefore, we see that $\gcd (ga-gb, f) \in D$ if and only $\gcd (a-b, \frac {f}{g}) \in D_g.$ From this, we conclude that the induced graph on $I_g$ is naturally isomorphic to $G_{f/g}(D_g)$ .

Proof First, let us show that $(2)$ implies $(1)$ . In other words, suppose that g satisfies the condition that $\Phi _{f,g}^{-1}(\overline {D_1}) \cap {\mathrm {Div}}(f)= D_1$ . We claim that the ideal I generated by g is a homogeneous set in $G_f(D).$ In fact, let $a \not \in I$ be an arbitrary element in ${\mathbb {F}}_q[x]/(f)$ and suppose that a is adjacent to an element in I. By a translation, we can assume that a is adjacent to $0$ in $G_f(D).$ We claim that a is adjacent to all elements in I as well. Let $gt$ be an element in I. We need to show that

$$\begin{align*}\gcd(a-gt, f) \in D.\end{align*}$$

Since $(a, 0) \in E(G_f(D))$ we know that $\gcd (a,f) \in D.$ Because $a \not \in I$ , we know further that $\gcd (a,f) \in D_1$ . Additionally, by Lemma 3.5, we must have ${\gcd (a,g) = \gcd (\gcd (a,f), g) \in \overline {D_1}}.$ Again, by Lemma 3.5, we have

$$\begin{align*}\gcd(\gcd(a-gt, f),g) = \gcd(a-gt, g) =\gcd(a, g) \in \overline{D_1} .\end{align*}$$

Because $D_1 = \Phi _{f,g}^{-1}(\overline {D_1}) \cap {\mathrm {Div}}(f)$ , this shows that $\gcd (a-gt, f) \in D_1$ and hence ${\gcd (a-gt, f) \in D} $ as required.

Conversely, we claim that $(1)$ implies $(2)$ . Suppose that I is a homogeneous set in $G_f(D).$ We need to show that $D_1 = \Phi _{f,g}^{-1}(\overline {D_1}) \cap {\mathrm {Div}}(f)$ . By Proposition 3.6, we always have $D_1 \subset \Phi _{f,g}^{-1}(D_1) \cap {\mathrm {Div}}(f)$ . Therefore, it is sufficient to show that $\Phi _{f,g}^{-1}(\overline {D_1}) \cap {\mathrm {Div}}(f) \subset D_1.$ Let $h \in \Phi _{f,g}^{-1}(\overline {D_1}) \cap {\mathrm {Div}}(f)$ . By definition, there exists $f_i \in D_1$ such that

$$\begin{align*}\gcd(h,g) = \gcd(f_i, g).\end{align*}$$

By Lemma 5.3, we can find $t \in {\mathbb {F}}_q[x]$ such that

$$\begin{align*}\gcd(h-gt, f) = f_i.\end{align*}$$

This shows that $(h, gt) \in E(G_f(D)).$ Since I is homogenous and $h \not \in I$ , we conclude that $(h,0) \in E(G_f(D))$ as well. By definition, $\gcd (h,f) \in D$ . Since $h \mid f$ , we conclude that $h \in D$ and hence $h \in D_1.$

Proof Let us first assume that I is homogenous. Let $g_i = \gcd (f_i,g).$ We claim that if $f_i \in D_1$ then $g_i =f_i$ and hence $f_i \mid g.$ In fact, we have $\gcd (g_i, g) = g_i = \gcd (f_i,g).$ This shows that $g_i \in \Phi _{f,g}^{-1}(\overline {D_1}) \cap {\mathrm {Div}}(f) = D_1$ (by Theorem 5.5). Since $f_i \nmid f_j$ for all $i \neq j$ , we must have $f_i = g_i$ and hence $f_i \mid g.$ By our assumption, $\gcd (f_1, f_2, \ldots , f_k)=1$ , and hence we must have $D_1 \neq \emptyset $ . If $D_2 \neq \emptyset $ then for each $f_1 \in D_1$ and $f_2 \in D_2$ , we have $f_1 \mid g \mid f_2$ which is a contradiction. Therefore, we must have $D_2 = \emptyset .$ In summary, we just prove that $f_i \mid g$ for all $1 \leq i \leq k.$ We now show that

$$\begin{align*}\mathrm{rad} \left(\frac{g}{f_i} \right) = \mathrm{rad} \left(\frac{f}{f_i} \right). \end{align*}$$

Suppose this is not the case. We can find a non-constant irreducible polynomial h of such that $\gcd (h,\frac {g}{f_i})=1$ and $h\mid \frac {f}{f_i}.$ We then see that $\gcd (hf_i, g)=f_i =\gcd (f_i,g).$ This implies that $hf_i \in D$ . Since $f_i \mid hf_i$ and $f_i \neq hf_i$ , this leads to a contradiction.

Let us now show the converse. By Theorem 5.5, we need to show that if ${h \in \Phi _{f,g}^{-1}(\overline {D_1}) \cap {\mathrm {Div}}(f)}$ then $h \in D_1.$ Since $h \in \Phi _{f,g}^{-1}(\overline {D_1})$ we can find $f_i \in D_1$ such that $\gcd (h,g) = \gcd (f_i,g)=f_i.$ Let us write $h=f_i h_1$ with $\gcd (h_1, \frac {g}{f_i})=1.$ By our assumption that $\mathrm {rad} \left (\frac {g}{f_i} \right ) = \mathrm {rad} \left (\frac {f}{f_i} \right )$ , we must have $\gcd (h_1, \frac {f}{f_i})=1$ as well. Since $h_1 \mid \frac {f}{f_i}$ , we must have $h_1=1$ and hence $h=f_i.$

Proof Suppose that $G_f(D)$ is not prime. By Proposition 5.2, there exists a proper divisor $g \mid f$ such that the ideal I generated by g is homogeneous. By Proposition 5.6, we must have $g=f$ which is a contradiction.

Proof If $k \geq 4$ then

$$\begin{align*}\omega(f/f_1) \geq \omega(f_2)+\omega(f_3)+\omega(f_4) \geq 3 .\end{align*}$$

By applying Proposition 7.3 for $g=f_1$ , we conclude that $G_{f}(D)$ is not perfect. Let us assume now that $k=3$ . By the same argument, it is enough to consider the case $\omega (f_1)=\omega (f_2) =\omega (f_3)=1.$ Furthermore, if $ f \neq f_1 f_2 f_3$ , then there exists an index $i \in \{1, 2, 3\}$ such that $\omega (f/f_i) \geq 3.$ As a result, $G_{f}(D)$ is not perfect by Proposition 7.3. Let us now consider the case $f=f_1f_2f_3$ . In this case

$$\begin{align*}{\mathbb{F}}_q[x]/(f) \cong {\mathbb{F}}_q[x]/(f_1 )\times {\mathbb{F}}_q[x]/(f_2) \times {\mathbb{F}}_q[x]/(f_3). \end{align*}$$

Under this isomorphism, we can identify $V(G_{f}(D))$ as the set of all triples $(a_1, a_2, a_3)$ , where $a_i \in {\mathbb {F}}_q[x]/(f_i)$ for $1 \leq i \leq 3.$ Furthermore, two vertices $(a_1,a_2,a_3)$ and $(b_1, b_2, b_3)$ are adjacent if and only if there exists an index $i \in \{1, 2, 3\}$ such that $a_i=b_i$ and ${(a_j-b_i) \in ({\mathbb {F}}_q[x]/(f_j))^{\times }}$ if $j \neq i$ . Using Sagemath, we can find the following induced $5$ -cycle in $G_{f}(D)$

$$\begin{align*}(0, 0, 0) \to (\alpha, \alpha, 0) \to (1, \alpha, 1) \to (1, 1, \alpha) \to (\alpha, 1, 0),\end{align*}$$

where $\alpha \in {\mathbb {F}}_q \setminus \{0, 1 \}.$ This show that $G_{f}(D)$ is not perfect.

Proof Let us assume to the contrary that $G_f(D)$ is perfect. Since $\gcd (f_1,f_2)=1$ , we have $f_1 f_2 \mid f$ and hence

$$\begin{align*}\omega(f) \geq \omega(f_1)+\omega(f_2).\end{align*}$$

If $\omega (f)> \omega (f_1)+\omega (f_2)$ then $\omega (f/f_2)> \omega (f_1) \geq 2.$ By Proposition 7.3, we know $G_f(D)$ is not perfect. Therefore, we must have $\omega (f)= \omega (f_1)+\omega (f_2).$

Let $g= f_1 f_2.$ By Proposition 5.6, the ideal generated by g is a homogeneous set in $G_f(D)$ and furthermore $G_f(D)$ is isomorphic to the wreath product ${G_{g}(\{f_1, f_2\}) * G_{f/g}(\emptyset )}.$ Since $G_f(D)$ is perfect, $G_{g}(\{f_1, f_2\})$ is perfect as well. Because $\omega (f_1) \geq 2$ , we can find $h_1, h_2 \in {\mathbb {F}}_q[x]$ such that $f_1 = h_1 h_2$ and $\gcd (h_1,h_2)=1.$ By the Chinese remainder theorem

$$\begin{align*}{\mathbb{F}}_q[x]/(g) \cong {\mathbb{F}}_q[x]/(h_1) \times {\mathbb{F}}_q[x]/(h_2) \times {\mathbb{F}}_q[x]/(f_2). \end{align*}$$

Under this isomorphism, we can identify ${\mathbb {F}}_q[x]/(g)$ with the set of tuples $(a_1, a_2, a_3)$ such that $a_1 \in {\mathbb {F}}_q[x]/(h_1), a_2 \in {\mathbb {F}}_q[x]/(h_2), a_3 \in {\mathbb {F}}_q[x]/(f_2).$ Furthermore, two vertices $(a_1,a_2,a_3)$ and $(b_1, b_2, b_3)$ are adjacent if and only if one of the following conditions happens:

1. (1) $a_1 = b_1, a_2 = b_2$ and $a_3 - b_3 \in ({\mathbb {F}}_q[x]/(f_2))^{\times }$ ;

2. (2) $a_3=b_3$ and $a_i-b_i \in ({\mathbb {F}}_q[x]/(h_i))^{\times }$ for $i \in \{1,2\}.$

Using Sagemath, we can find the following $7$ -cycle in $G_g(\{f_1, f_2 \})$ :

$$\begin{align*}(0, 0, 0) \to (1,1,0) \to (\alpha, 0, 0) \to (\alpha, 0, 1) \to (0, 1,1) \to (\alpha, \alpha, 1) \to (0, 0, 1),\end{align*}$$

where $\alpha \in {\mathbb {F}}_q \setminus \{0,1 \}.$ We conclude that $G_g(\{f_1, f_2\})$ is not a perfect graph, which is a contradiction.

Proof Let $f\colon G \to H$ be a graph morphism that makes G into an induced subgraph of $H.$ Let us index $V(G) =\{v_1, v_2, \ldots , v_{|G|} \}$ . Let $\hat {f}\colon G \to H \times K_{|G|}$ be the map defined by

$$\begin{align*}\hat{f}(v_i) = (f(v_i), i) .\end{align*}$$

We can see that $\hat {f}$ is a graph morphism which turns G into an induced subgraph of $H \times K_{|G|}.$

Proof By Erdős and Evans’s theorem [Reference Erdös and Evans12], there exists a squarefree integer $n \in {\mathbb {N}}$ such that G is an induced subgraph of the unitary graph $G_n$ on ${\mathbb {Z}}/n{\mathbb {Z}}.$ Let $r = \omega (n)$ ; i.e., $n=p_1p_2 \ldots p_r$ be the prime factorization of n. Then,

$$\begin{align*}G_n \cong \prod_{i=1}^r G_{p_i} \cong \prod_{i=1}^r K_{p_i}.\end{align*}$$

For each $i \in {\mathbb {N}}$ and $m_i \in {\mathbb {N}}$ , by Galois theory for finite fields, there exists a polynomial $h_i$ of degree $m_i$ such that $h_i$ is irreducible over ${\mathbb {F}}_q[x].$ We then see that $G_{h_i}(\{1\})$ is isomorphic to the complete graph $K_{q^{m_i}}.$ Let us choose $m_i$ so that $q^{m_i}>n$ for all i. For each $d \geq r$ , let $F_d = h_1 h_2 \ldots h_d.$ We then have

$$\begin{align*}G_{F_d}(\{1\}) \cong \prod_{i=1}^d G_{h_i}(\{1\}) \cong \prod_{i=1}^d K_{q^{m_i}}.\end{align*}$$

Since $q^{m_i}>n$ , we know that $G_n$ is an induced subgraph of $G_{F_r}(\{1\}).$ By Lemma 8.1, G is an induced subgraph of $G_{F_d}(\{1\})$ as well.

Proof Let $h_0$ be an arbitrary polynomial in ${\mathbb {F}}_q[x].$ By Proposition 8.2, there exists a positive integer $d \geq k$ and a polynomial h of the form $h = h_1 h_2 \ldots h_{d}$ such that G is an induced subgraph of $G_{h}(\{1\}).$ Let us choose $f = h_0 h$ and

$$\begin{align*}\{f_1, f_2, \ldots, f_k \} = \{h_1, h_2, \ldots, h_k \}. \end{align*}$$

Let I be the ideal generated by $h_0$ in ${\mathbb {F}}_q[x]/(f).$ By Lemma 5.4, the induced graph on I is naturally isomorphic to the unitary Cayley graph $G_{h}(\{1 \})$ . This shows that G is an induced subgraph of $G_{f}(D).$

Proof By Erdős and Evans’s theorem, there exists a squarefree number n such that G is an induced subgraph of the unitary Cayley graph $G_n.$ Suppose that $r = \omega (n)$ and $n=p_1 p_2 \ldots p_r$ be the prime factorization of $n.$ Then, as explained in the proof of Proposition 8.2, $G_n \cong \prod _{i=1}^r K_{p_i}.$ Our goal is to show that we can find ${\mathbb {F}}_{q^m}$ and f such that $G_n$ is an induced subgraph of $G_{f}(D)$ where we consider f as an element in ${\mathbb {F}}_{q^m}[x].$

Let m be a positive integer such that $q^m>n$ and $g = \mathrm {lcm}(f_1, f_2, \ldots , f_k) \in {\mathbb {F}}_q[x].$ By Galois theory, there exists a polynomial $h \in {\mathbb {F}}_q[x]$ with at least r distinct irreducible factors and $\gcd (h,g)=1.$ Let $f=hg$ . Let I be the ideal in ${\mathbb {F}}_{q^m}[x]/(f)$ generated by $f_1.$ Then, by Lemma 5.4, the induced subgraph on I is isomorphic to the unitary Cayley graph $G_{\bar {f}}(\{1\})$ , where $\bar {f} = f/f_1.$ Suppose that $\bar {f} = g_1^{a_1} g_2^{a_2} \ldots g_t^{a_t}$ be the factorization of $f/f_1$ over ${\mathbb {F}}_{q^m}[x].$ Then, by the choice of f, $t \geq r.$ By the Chinese remainder theorem, we know that ${\mathbb {F}}_{q^m}^t$ is a subring of ${\mathbb {F}}_{q^m}[x]/\bar {f}.$ Therefore, $G_{{\mathbb {F}}_{q^m}^t} = \prod _{i=1}^t K_{q^{m}}$ is an induced subgraph of $G_{\bar {f}}(\{1\})$ . Since $t \geq r$ and $q^m \geq n$ , by Lemma 8.1, $G_n$ is an induced subgraph of $G_{{\mathbb {F}}_{q^m}^t}$ . Consequently, $G_n$ is an induced subgraph of $G_{f}(D)$ as well.