Strong products of Kneser graphs (Q1336712)

For a (simple, undirected) graph \(G = (V(G), E(G))\), let \(\chi(G)\) and \(\omega(G)\) denote the chromatic number and the clique number, respectively. A subgraph \(H\) of \(G\) is a retract of \(G\) iff there is an edge-preserving map \(h : V(G) \to V(H)\) with \(h(x) = x\) for all \(x \in V(H)\). The strong product \(G \otimes H\) of graphs \(G\) and \(H\) has the vertex set \(V(G) \times V(H)\) and the edge set \[ \begin{multlined} \{\{(a,x),(b,y)\} : (a,x),(b,y) \in V(G) \times V(H) \wedge [(a = b \wedge \{x,y\} \in E(H)) \vee \\ \vee (x = y \wedge \{a,b\} \in E(G)) \vee (\{a,b\} \in E(G) \wedge \{x,y\} \in E(H))]\}. \end{multlined} \] It is proved that \(\chi(G \otimes H) \geq \chi(G \otimes K_ n) \geq \chi(G) + 2n - 2\) for any graphs \(G\), \(H\) with \(| E(G) | \geq 1\) and \(\omega(H) = n\) \((n = 1,2,\dots)\); this lower bound is sharp in the sense that for every \(n \geq 1\) and \(k \geq 0\) the Kneser graph \(KG_{n,k}\) satisfies \(\chi(KG_{n,k} \otimes K_ n) = 2n + k = \chi(KG_{n,k}) + 2n - 2.\) Regarding the problem of characterizing graphs \(G\), \(H\), \(G'\) and \(H'\) for which \(G' \otimes H'\) is a retract of \(G \otimes H\) where \(G'\) is not a retract of \(G\), by means of Kneser graphs for every \(n \geq 2\) there is constructed an infinite set of examples \(G\), \(G'\) such that \(G' \otimes K_ n\) is a retract of \(G \otimes K_ n\) while \(G'\) is not a retract of \(G\).