QA484 : Some results in Kneser hypergraphs coloring
Thesis > Central Library of Shahrood University > Mathematical Sciences > PhD > 2018
Authors:
Abstarct: Lovász proved the long-standing Kneser conjecture in 1978. This proof gave birth to an area of combinatorics called toplogical combinatorics which concentrates on coloring properties of Kneser graphs and hypergraphs. The general Kneser hypergraph KG^r (H) is an r-uniform hypergraph that somehow encodes the edge intersections of a ground hypergraph H.
We here define a new combinatorial parameter called equitable colorability defect of hypergraphs, which provides a new lower bound for the chromatic number of general Kneser hypergraphs. We prove that our proposed sharp lower bound outperforms most of the best known existing lower bounds for chromatic number of hypergraph KG^r (H). In addition, we demonstrate that the difference between our proposed lower bound and some of the best known lower bounds such as the Dol'nikov-Kří ž lower bound (1992), the Ziegler lower bound (2002), and the Alishahi-Hajiabolhassan lower bound (2015) can be arbitrary large. By use of the aforementioned lower bound, the chromatic number of some family of grahs is determined, as well.
Furthermore, we prove a result ensuring the existence of a colorful subhypergraph in any proper coloring of general Kneser hypergraphs that strengthens prior results in the literature.
We extend these results to categorical product of general Kneser hypergraphs. To be more specific, we present some colorful type results for the coloring of categorical product of general Kneser hypergraphs, which generalize the Hajiabolhassan-Meunier result (2016). 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 (a generalization of Hedetniemi's conjecture to hypergraphs).
Keywords:
#Kneser hypergraphs; chromatic number; colorability defect; colorful subhypergraph; categorical product; Hedetniemi's conjecture
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: