Maximum induced forests of product graphs (Q2683145)

The forest number \(f(G)\) for a graph \(G\) is the maximum number of vertices in an induced forest of \(G\). A product \(G\ast H\) of graphs \(G\) and \(H\) is a graph on the vertex set \(V(G)\times V(H)\). Based on the definition of an edge set, several products are known. In particular, two vertices \((g,h),(g\prime,h\prime)\in V(G)\times V(H)\) are adjacent in \begin{itemize} \item the Cartesian product \(G\Box H\) if \(g=g\prime\) and \(hh\prime\in E(H)\) or \(gg\prime\in E(G)\) and \(h=h\prime\); \item the direct product \(G\times H\) if \(gg\prime\in E(G)\) and \(hh^\prime\in E(H)\); \item the lexicographic product \(G\circ H\) if \(gg\prime\in E(G)\) or \(g=g\prime\) and \(hh\prime\in E(H)\). \end{itemize} In this paper, the forest number of Cartesian, direct and lexicographic products is studied. Some bounds are given and some conditions on the factors are presented that yield some exact values for the forest number of the mentioned products. The topic remains open for further investigation.