Coloring fiber product of graphs (Q2508412)

The cross product \(G_1\times G_2 = (V,E)\) of two graphs \(G_i=(V_i, E_i)\), \(i=1,2\), consists of \(V=V_1\times V_2\) and \(E=\{(u_1, u_2)(v_1, v_2) \mid u_1v_1\in E_1\) and \(u_2v_2\in E_2\}\). A homomorphism \(f: G\rightarrow H\) of two graphs \(G\) and \(H\) is a mapping from the vertex set of \(G\) into the vertex set of \(H\) such that \(f(u)\) and \(f(v)\) are adjacent in \(H\) whenever \(u\) and \(v\) are adjacent in \(G\). Given \(H, G_1, G_2\) and homomorphisms \(f_i: G_i\rightarrow H\), \(i=1,2\), the fiber product (over \(f_1\) and \(f_2\)) \(G_1\times_H G_2 =(V, E)\) consists of \(V=\{(u_1, u_2)\in V_1\times V_2 \mid f_1(u_1) = f_2(u_2)\}\) and \(E=\{(u_1,u_2)(v_1,v_2) \mid u_1v_1\in E_1\) and \(u_2v_2\in E_2\}\). Thus, \(G_1\times_H G_2\) is an induced subgraph of \(G_1\times G_2\). Hedetniemi conjectured that \(\chi(G_1\times G_2) > n\) whenever \(\chi(G_i) > n\), \(i=1,2\). A stronger conjecture by Khelladi reads as follows: For any homomorphisms \(f_i:G_i\rightarrow K_n\), \(\chi(G_1\times_{K_n} G_2)\leq n\). The authors prove the latter for \(n\leq 3\). They also prove that the following conjectures are equivalent: Conjecture A: For any graphs \(G_i\) with \(\chi(G_i) > n\), \(i=1,2\), and \(p\geq\max\{\chi(G_1),\chi(G_2)\}\), there exist homomorphisms \(f_i: G_i\rightarrow K_p\) such that \(\chi(G_1\times_{K_p} G_2) > n\). Conjecture B: If \(\chi(G)>n\), then for every homomorphism \(f: G\rightarrow K_p\) with \(\chi(G)=p\), \(\chi(C_n(G,f))=n\), where \(C_n(G, f)\) is the graph with vertex set \[ A_1\cup\cdots\cup A_p,\quad A_i =\{\varphi \mid \varphi:f^{-1}(i)\rightarrow K_n\},\quad 1\leq i\leq p, \] and edge set \[ \{\varphi\varphi' \mid \varphi\in A_i, \varphi'\in A_j, \text{ and for all }(u,v)\in f^{-1}(i)\times f^{-1}(j),\;uv\in E(G)\text{ implies }\varphi(u)\not=\varphi'(v)\}. \] Note that Conjecture A implies Hedetniemi's conjecture (and hence so does Conjecture B).