Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers (Q2084794)

Let \(G \times H\) be the direct product (also called categorical or tensor product) of the graphs \(G\) and \(H\), which is the graph with \(V( G \times H)=V(G) \times V(H)\) and adjacencies \((u,v) \sim (u^\prime,v^\prime)\) if \(u \sim u^\prime\) and \(v \sim v^\prime\). As a statement between Hedetniemi's conjecture \[ \chi(G \times H) \ge \min\{ \chi(G), \chi(H) \}, \] which was disproven by \textit{Y. Shitov} [Ann. Math. (2) 190, No. 2, 663--667 (2019; Zbl 1451.05087)], and its fractional version \[ \chi_f(G \times H) \ge \min\{ \chi_f(G), \chi_f(H) \}, \] which was proven by \textit{X. Zhu} [Eur. J. Comb. 32, No. 7, 1168--1175 (2011; Zbl 1229.05108)], the inequality \[ \chi(G \times H) \ge \min\{ \chi_f(G), \chi(H) \} \] is studied. A counterexample is constructed for which \(\chi(G \times H)=43\), which is smaller than for the previously known counterexamples (for which \(\chi(G \times H)\ge 125\) did hold). The counterexample uses the Cayley graph \(G_{166}=\mathrm{Cay}(\mathbb Z_{166}, \{ \pm 6, \pm 7, \pm46, \pm47\})\) and some of its properties. Let \(G\) be the lexicographic product (or graph composition) \( G_{166} \cdot K_{14} = G_{166}[K_{14}]\). Let \(H\) be the (exponential) graph \(K_{43}^{G_{166}[K_{14}]}\) which contains all (not necessarily proper) \(43\)-colourings of \(G_{166}[K_{14}]\). Then \(\chi_f(G)=43 \frac 1 {27}>43,\) \(\chi(H) \ge 44\) and \(\chi_f(G \times H)=43.\) In the end, the author poses the following problem: Let \(G\) be a graph with known independence number \(\alpha(G)\), and \(H\) a double cover of \(G\). How hard is it to determine whether \(\alpha(H) = 2 \alpha(G)\)?