Hedetniemi's conjecture for Kneser hypergraphs

DOI10.1016/J.JCTA.2016.05.002zbMATH Open1342.05094arXiv1410.3021OpenAlexW1515028822WikidataQ123265806 ScholiaQ123265806MaRDI QIDQ530765FDOQ530765

Authors: Hossein Hajiabolhassan, Frédéric Meunier 

Publication date: 1 August 2016

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

Abstract: One of the most famous conjecture in graph theory is Hedetniemi's conjecture stating that the chromatic number of the categorical product of graphs is the minimum of their chromatic numbers. Using a suitable extension of the definition of the categorical product, Zhu proposed in 1992 a similar conjecture for hypergraphs. We prove that Zhu's conjecture is true for the usual Kneser hypergraphs of same rank. It provides to the best of our knowledge the first non-trivial and explicit family of hypergraphs with rank larger than two satisfying this conjecture (the rank two case being Hedetniemi's conjecture). We actually prove a more general result providing a lower bound on the chromatic number of the categorical product of any Kneser hypergraphs as soon as they all have same rank. We derive from it new families of graphs satisfying Hedetniemi's conjecture. The proof of the lower bound relies on the $Z_p$-Tucker lemma.

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

Recommendations

• Coloring properties of categorical product of general Kneser hypergraphs
• Hedetniemi's conjecture from the topological viewpoint
• An approach to hedetniemi's conjecture
• A survey on Hedetniemi's conjecture
• Counterexamples to Hedetniemi's conjecture

zbMATH Keywords

Kneser graphsKneser hypergraphs\(Z_p\)-Tucker lemmacategorical productHedetniemi conjecture

Mathematics Subject Classification ID

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

Cites Work

• On the diameter of Kneser graphs
• Kneser's conjecture, chromatic number, and homotopy
• A survey on Hedetniemi's conjecture
• Independence and coloring properties of direct products of some vertex-transitive graphs
• The Chromatic Number of Kneser Hypergraphs
• Hom complexes and homotopy theory in the category of graphs
• Colorful subgraphs in Kneser-like graphs
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Title not available (Why is that?)
• n-tuple colorings and associated graphs
• Generalized Kneser coloring theorems with combinatorial proofs
• A combinatorical proof of Kneser's conjecture
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Topological lower bounds for the chromatic number: a hierarchy
• Title not available (Why is that?)
• Title not available (Why is that?)
• On topological relaxations of chromatic conjectures
• Colorful subhypergraphs in Kneser hypergraphs
• On the chromatic number of general Kneser hypergraphs
• The chromatic number of almost stable Kneser hypergraphs
• On the b-chromatic number of Kneser graphs
• A certain combinatorial inequality
• Stable Kneser hypergraphs and ideals in $\mathbb {N}$ with the Nikodým property
• Chromatic number via Turán number
• A category-theoretical approach to hypergraphs
• On generalized Kneser hypergraph colorings

Cited In (8)

• Counterexamples to Hedetniemi's conjecture
• Coloring properties of categorical product of general Kneser hypergraphs
• Hedetniemi's conjecture is asymptotically false
• Chromatic number of random Kneser hypergraphs
• Strengthening topological colorful results for graphs
• Hedetniemi's conjecture and dense Boolean lattices
• A new lower bound for the chromatic number of general Kneser hypergraphs
• Hedetniemi's conjecture from the topological viewpoint

This page was built for publication: Hedetniemi's conjecture for Kneser hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q530765)