Counterexamples to Hedetniemi's conjecture

DOI10.4007/annals.2019.190.2.6zbMath1451.05087arXiv1905.02167OpenAlexW2969838569WikidataQ122932603 ScholiaQ122932603MaRDI QIDQ2274002

Yaroslav N. Shitov

Publication date: 19 September 2019

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberHedetniemi's conjecturetensor product of graphs

Mathematics Subject Classification ID

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

Related Items

Topology and Adjunction in Promise Constraint Satisfaction ⋮ In praise of homomorphisms ⋮ Distance formula for direct-co-direct product in the case of disconnected factors ⋮ Thinness of product graphs ⋮ On the \(r\)-dynamic coloring of the direct product of a path with either a path or a cycle ⋮ The fractional chromatic number of generalized cones over graphs ⋮ The chromatic number of the product of 14-chromatic graphs can be 13 ⋮ Shannon capacity and the categorical product ⋮ On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs ⋮ Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs ⋮ On multichromatic numbers of widely colorable graphs ⋮ Hedetniemi's conjecture from the topological viewpoint ⋮ On some metric properties of direct-co-direct product ⋮ Acyclic coloring of products of digraphs ⋮ On locally identifying coloring of graphs ⋮ On total coloring the direct product of cycles and bipartite direct product of graphs ⋮ Relatively small counterexamples to Hedetniemi's conjecture ⋮ Hedetniemi's conjecture is asymptotically false ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Minimal definable graphs of definable chromatic number at least three ⋮ A complexity problem for Borel graphs ⋮ Quantum multiplicative graph and a type of separate clique number ⋮ The diameter of strong orientations of strong products of graphs ⋮ A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function ⋮ Note on Hedetniemi's conjecture and the Poljak-Rödl function ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ A note on the Poljak-Rödl function ⋮ Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers ⋮ Chromatic numbers, Sabidussi's theorem and Hedetniemi's conjecture for non-commutative graphs ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

Cites Work

• Unnamed Item
• Hedetniemi's conjecture for uncountable graphs
• Hedetniemi's conjecture for Kneser hypergraphs
• The fractional version of Hedetniemi's conjecture is true
• Symmetric graphs and interpretations
• 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
• On multiplicative graphs and the product conjecture
• On the arc-chromatic number of a digraph
• A survey on Hedetniemi's conjecture
• Coloring graph products---a survey
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• Independence and coloring properties of direct products of some vertex-transitive graphs
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• Graph Theory and Probability
• On the chromatic number of the product of graphs
• Hedetniemi's conjecture---a survey