The star chromatic numbers of graph products (Q2717070)

All graphs \(G=(V,E)\) treated in the present paper are simple ones, and the author considers the following two kinds of graph products, namely the categorical product \(G\otimes H\) of graphs \(G\) and \(H\): this is a graph such that \(V(G\otimes H)=\{(g,h):g\in V(G),h\in V(H)\}\) and \(E(G\otimes H)=\{((g,h),(g',h')):(g,g')\in E(G),(h,h')\in E(H)\}\) and the wreath product \(G([ H])\) of graphs \(G\) and \(H\): this is a graph such that \(V(G[H])=\{(g,h):g\in V(G),h\in V(H)\}\) and \(E(G[H])=\{((g,h),(g',h'))\): either \((g,g')\in E(G)\), or \(g=g'\) and \((h,h')\in E(H)\}\). The star-chromatic numbers \(\chi^*\) of these graphs are discussed in some special cases, where \(\chi^*\) is defined in the following way: if \(k\) and \(b\) are such that \(k\geq 2d\), then a \((k,d)\)-coloring of a graph \(G\) is a mapping \(c:V\rightarrow Z_k\), such that for each edge \((u,v)\in E, |c(u)-c(v)|_k\geq d\), where \(|x|_k=\min\{|x|,k-|x|\}\), and \(Z_k=\{0,1,\dots,k-1\}\). Then \(\chi^*=\inf\{k/d:G\) has a \((k,d)\)-coloring\(\}\). It is known that for every \(G\) we have \(\chi(G)-1<\chi^*(G)\leq \chi(G),\chi^*(G)=\min\{k/d:G\) has a \((k,d)\)-coloring, \(k\leq |V(G)|\}\), where \(\chi\) is the chromatic number of a graph. Furthermore, \(\chi\) and \(\chi^*\) of the above defined products possess the following properties: For any graphs \(G, H\) one has: \(\chi(G\otimes H)\leq \min\{\chi(G),\chi(H)\}\) and \(\chi^*(G\otimes H)\leq \min\{\chi^*(G),\chi^*(H)\}\) (Property 1.1), \(\chi^*(G[H])\leq \chi^*(G)\cdot\chi^*(H)\) (Property 2.1). NEWLINENEWLINENEWLINEThe main result of this paper is a sufficient condition for these inequalities to become equalities. For this aim the author needs the term \(i(G)=\biggl|{V(G)\over \alpha(G)}\biggr|\), where \(\alpha(G)\) denotes a maximal independent set of \(G\). Then he gets the following results: If \(G\) is a graph with \(\chi^*(G)=k/d\), then for any natural number \(m\geq k/d\), we have \(\chi(G\otimes K_m)=\chi(G)\) and \(\chi^*(G\otimes K_m)=\chi^*(G)\) (Theorem 2.1). If graphs \(G\) and \(H\) satisfy \(i(G)=\chi^*\geq 2\), then \(\chi^*(G[H])=\chi^*(G)\cdot\chi^*(H)\) (Theorem 2.4).