Hedetniemi's conjecture for Kneser hypergraphs

DOI10.1016/J.JCTA.2016.05.002MaRDI QIDQ530765zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(10)

• 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
• Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs
• A new lower bound for the chromatic number of general Kneser hypergraphs
• Hedetniemi's conjecture from the topological viewpoint
• Altermatic number of categorical product of graphs

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)