Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers
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)\)?
- The chromatic number of the product of two 4-chromatic graphs is 4
- Relatively small counterexamples to Hedetniemi's conjecture
- Counterexamples to Hedetniemi's conjecture
- Hedetniemi's conjecture is asymptotically false
- A survey on Hedetniemi's conjecture
- Hedetniemi's conjecture---a survey
- The fractional chromatic number of the categorical product of graphs
- An approach to hedetniemi's conjecture
- The fractional version of Hedetniemi's conjecture is true
- A note on the Poljak-Rödl function
- Counterexamples to Hedetniemi's conjecture
- scientific article; zbMATH DE number 3851123 (Why is no real title available?)
- scientific article; zbMATH DE number 3520447 (Why is no real title available?)
- Local chromatic number, Ky Fan's theorem, and circular colorings
- Relatively small counterexamples to Hedetniemi's conjecture
- Star-extremal graphs and the lexicographic product
- The chromatic number of the product of 14-chromatic graphs can be 13
- The chromatic number of the product of two 4-chromatic graphs is 4
- The fractional version of Hedetniemi's conjecture is true
- Note on Hedetniemi's conjecture and the Poljak-Rödl function
- The chromatic number of the product of 14-chromatic graphs can be 13
- Relatively small counterexamples to Hedetniemi's conjecture
- Counterexamples to Hedetniemi's conjecture
- The fractional chromatic number of the categorical product of graphs
- Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs
- The fractional chromatic number of the direct product of graphs
- scientific article; zbMATH DE number 2119454 (Why is no real title available?)
- The chromatic number of the product of 5-chromatic graphs can be 4
- More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
- On the chromatic number and independence number of hypergraph products
This page was built for publication: Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084794)
