Hedetniemi's conjecture is asymptotically false

DOI10.1016/j.jctb.2020.03.003zbMath1457.05037arXiv1906.06783OpenAlexW3099860793MaRDI QIDQ2221935

Xiaoyu He, Yuval Wigderson

Publication date: 3 February 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.06783

zbMATH Keywords

graph coloringHedetniemi's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Related Items (6)

In praise of homomorphisms ⋮ The chromatic number of the product of 14-chromatic graphs can be 13 ⋮ Shannon capacity and the categorical product ⋮ Note on Hedetniemi's conjecture and the Poljak-Rödl function ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

Cites Work

• Unnamed Item
• Hedetniemi's conjecture for Kneser hypergraphs
• The fractional version of Hedetniemi's conjecture is true
• The chromatic number of the product of two 4-chromatic graphs is 4
• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• On the arc-chromatic number of a digraph
• A survey on Hedetniemi's conjecture
• Counterexamples to Hedetniemi's conjecture
• A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function
• Graph Theory and Probability
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting Families are Essentially Contained in Juntas
• Hedetniemi's conjecture---a survey

This page was built for publication: Hedetniemi's conjecture is asymptotically false