Hedetniemi's conjecture is asymptotically false
He X, Wigderson Y. 2021. Hedetniemi’s conjecture is asymptotically false. Journal of Combinatorial Theory, Series B. 146, 485–494.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
He, Xiaoyu;
Wigderson, YuvalISTA
Abstract
Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. More precisely, we prove that there exists an absolute constant δ>0 such that for all c sufficiently large, there exist graphs G and H with chromatic number at least (1+δ)c for which χ(G×H)≤c.
Keywords
Publishing Year
Date Published
2021-01-01
Journal Title
Journal of Combinatorial Theory, Series B
Publisher
Elsevier
Volume
146
Page
485-494
ISSN
IST-REx-ID
Cite this
He X, Wigderson Y. Hedetniemi’s conjecture is asymptotically false. Journal of Combinatorial Theory, Series B. 2021;146:485-494. doi:10.1016/j.jctb.2020.03.003
He, X., & Wigderson, Y. (2021). Hedetniemi’s conjecture is asymptotically false. Journal of Combinatorial Theory, Series B. Elsevier. https://doi.org/10.1016/j.jctb.2020.03.003
He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically False.” Journal of Combinatorial Theory, Series B. Elsevier, 2021. https://doi.org/10.1016/j.jctb.2020.03.003.
X. He and Y. Wigderson, “Hedetniemi’s conjecture is asymptotically false,” Journal of Combinatorial Theory, Series B, vol. 146. Elsevier, pp. 485–494, 2021.
He X, Wigderson Y. 2021. Hedetniemi’s conjecture is asymptotically false. Journal of Combinatorial Theory, Series B. 146, 485–494.
He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically False.” Journal of Combinatorial Theory, Series B, vol. 146, Elsevier, 2021, pp. 485–94, doi:10.1016/j.jctb.2020.03.003.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
arXiv 
Google Scholar