---
OA_place: repository
OA_type: green
_id: '22156'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: He X, Wigderson Y. Hedetniemi’s conjecture is asymptotically false. <i>Journal
    of Combinatorial Theory, Series B</i>. 2021;146:485-494. doi:<a href="https://doi.org/10.1016/j.jctb.2020.03.003">10.1016/j.jctb.2020.03.003</a>
  apa: He, X., &#38; Wigderson, Y. (2021). Hedetniemi’s conjecture is asymptotically
    false. <i>Journal of Combinatorial Theory, Series B</i>. Elsevier. <a href="https://doi.org/10.1016/j.jctb.2020.03.003">https://doi.org/10.1016/j.jctb.2020.03.003</a>
  chicago: He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically
    False.” <i>Journal of Combinatorial Theory, Series B</i>. Elsevier, 2021. <a href="https://doi.org/10.1016/j.jctb.2020.03.003">https://doi.org/10.1016/j.jctb.2020.03.003</a>.
  ieee: X. He and Y. Wigderson, “Hedetniemi’s conjecture is asymptotically false,”
    <i>Journal of Combinatorial Theory, Series B</i>, vol. 146. Elsevier, pp. 485–494,
    2021.
  ista: He X, Wigderson Y. 2021. Hedetniemi’s conjecture is asymptotically false.
    Journal of Combinatorial Theory, Series B. 146, 485–494.
  mla: He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically
    False.” <i>Journal of Combinatorial Theory, Series B</i>, vol. 146, Elsevier,
    2021, pp. 485–94, doi:<a href="https://doi.org/10.1016/j.jctb.2020.03.003">10.1016/j.jctb.2020.03.003</a>.
  short: X. He, Y. Wigderson, Journal of Combinatorial Theory, Series B 146 (2021)
    485–494.
date_created: 2026-06-29T10:50:09Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2026-07-08T07:43:57Z
day: '01'
doi: 10.1016/j.jctb.2020.03.003
extern: '1'
external_id:
  arxiv:
  - '1906.06783'
intvolume: '       146'
keyword:
- Graph coloring
- Hedetniemi's conjecture
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1906.06783
month: '01'
oa: 1
oa_version: Preprint
page: 485-494
publication: Journal of Combinatorial Theory, Series B
publication_identifier:
  issn:
  - 0095-8956
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hedetniemi's conjecture is asymptotically false
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2021'
...