Note on Hedetniemi's conjecture and the Poljak-Rödl function

DOI10.1007/978-3-030-62497-2_31zbMath1484.05079arXiv1911.12015OpenAlexW2992444327MaRDI QIDQ2058954

Xuding Zhu

Publication date: 10 December 2021

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

zbMATH Keywords

chromatic numberexponential graphsShitov's theorem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• The fractional version of Hedetniemi's conjecture is true
• Kneser's conjecture, chromatic number, and homotopy
• A note on the Poljak-Rödl function
• The chromatic number of the product of two 4-chromatic graphs is 4
• On multiplicative graphs and the product conjecture
• On the arc-chromatic number of a digraph
• n-tuple colorings and associated graphs
• A survey on Hedetniemi's conjecture
• Coloring graph products---a survey
• Relatively small counterexamples to Hedetniemi's conjecture
• Hedetniemi's conjecture is asymptotically false
• Counterexamples to Hedetniemi's conjecture
• A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• Graph Theory and Probability
• Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function
• Hedetniemi's conjecture---a survey