Coloring properties of categorical product of general Kneser hypergraphs

Roya Abyazi Sani, Meysam Alishahi, Ali Taherkhani

Abstract


More than 50 years ago Hedetniemi conjectured that the chromatic number of categorical product of two graphs is equal to the minimum of their chromatic numbers. This conjecture has received a considerable attention in recent years. Hedetniemi’s conjecture was generalized to hypergraphs by Zhu in 1992. Hajiabolhassan and Meunier, in 2016, introduced the first nontrivial lower bound for the chromatic number of categorical product of general Kneser hypergraphs and using this lower bound, they verified Zhu’s conjecture for some families of hypergraphs. In this paper, we shall present some colorful type results for the coloring of categorical product of general Kneser hypergraphs, which generalize the Hajiabolhassan-Meunier result. Also, we present a new lower bound for the chromatic number of categorical product of general Kneser hypergraphs which can be much better than the Hajiabolhassan-Meunier lower bound. Using this lower bound, we enrich the family of hypergraphs satisfying Zhu’s conjecture.


Keywords


Categorical product, chromatic number, Hedetniemi's conjecture, general Kneser hypergraph

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.1414.58b

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications