Lower bounds for the chromatic number of certain Kneser-type hypergraphs

DOI10.1016/J.EJC.2022.103664arXiv2009.05969MaRDI QIDQ6348985FDOQ6348985

Publication date: 13 September 2020

Abstract: Let

n g e 1

,

r g e 2

, and

s g e 0

be integers and

c a l P = P_{1}, d o t s, P_{l}

be a partition of

[n] = 1, d o t s, n

with

| P_{i} | l e r

for

i = 1, d o t s, l

. Also, let

c a l F

be a family of non-empty subsets of

[n]

. The

r

-uniform Kneser-type hypergraph

m b o x {K G}^{r} (c a l F, c a l P, s)

is the hypergraph with the vertex set of all

c a l P

-admissible elements

F i n c a l F

, that is

| F c a p P_{i} | l e 1

for

i = 1, d o t s, l

and the edge set of all

r

-subsets

F_{1}, d o t s, F_{r}

of the vertex set that

| F_{i} c a p F_{j} | l e s

for all

1 l e i < j l e r

. In this article, we extend the equitable

r

-colorability defect

m b o x {e c d}^{r} (c a l F)

of Abyazi Sani and Alishahi to the case when one allows intersection among the vertices of an edge. It will be denoted by

m b o x {e c d}^{r} (c a l F, s)

. We then, give (under certain assumptions) lower bounds for the chromatic number of

m b o x {K G}^{r} (c a l F, c a l P, s)

and some of its variants in terms of

m b o x {e c d}^{r} (c a l F, l f l o o r s / 2 f l o o r)

. This work generalizes many existing results in the literature of the Kneser hypergraphs. It generalizes the previous results of the current authors from the special family of all

k

-subsets of

[n]

to a general family

c a l F

of subsets.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

This page was built for publication: Lower bounds for the chromatic number of certain Kneser-type hypergraphs

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