Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers
type: Item
instance of: scholarly article
title: Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers
zbMATH Open document ID: 1498.05107
author: Claude Tardif
published in: Graphs and Combinatorics
publication date: 2022-10-13T00:00:00Z
review text: 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)\)?
reviewed by: Stijn Cambie
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 7601300
zbMATH Keywords: direct product
zbMATH Keywords: graph colouring
zbMATH Keywords: fractional chromatic number
zbMATH Keywords: Hedetniemi's conjecture
Wikidata QID: Q122923369
describes a project that uses: GAP
describes a project that uses: GRAPE
MaRDI profile type: Publication
full work available at URL: s00373-022-02576-x
OpenAlex ID: W4304692595
cites work: Q4100121
cites work: The chromatic number of the product of two 4-chromatic graphs is 4
cites work: Star-extremal graphs and the lexicographic product
cites work: Counterexamples to Hedetniemi's conjecture
cites work: Local chromatic number, Ky Fan's theorem, and circular colorings
cites work: The chromatic number of the product of 14-chromatic graphs can be 13
cites work: Q3320408
cites work: The fractional version of Hedetniemi's conjecture is true
cites work: A note on the Poljak-Rödl function
cites work: Relatively small counterexamples to Hedetniemi's conjecture
DOI: 10.1007/S00373-022-02576-X
Recommended article: The chromatic number of the product of two 4-chromatic graphs is 4
Recommended article: Relatively small counterexamples to Hedetniemi's conjecture
Recommended article: Counterexamples to Hedetniemi's conjecture
Recommended article: Hedetniemi's conjecture is asymptotically false
Recommended article: A survey on Hedetniemi's conjecture
Recommended article: Hedetniemi's conjecture---a survey
Recommended article: The fractional chromatic number of the categorical product of graphs
Recommended article: An approach to hedetniemi's conjecture
Recommended article: The fractional version of Hedetniemi's conjecture is true
description: scientific article; zbMATH DE number 7601300