Regarding equitable colorability defect of hypergraphs

Saeed Shaebani

Article Details

Regarding equitable colorability defect of hypergraphs

Authors:

Saeed Shaebani

Publisher:

Hacettepe University

Main Topics:

Mathematical Sciences

Journal:

Hacettepe Journal of Mathematics and Statistics Vol.53 Issue 1, pp.184-190

Document Type:

Article

Publication Date:

2/2024

Document Language:

English

Document ID (Org No.):

2001312255

pISSN:

2651-477X

Keywords:

Abstract:

 After Lovászs break-through in determining the chromatic number of Kneser graphs 1978, and after extending this result to the chromatic number of r-uniform Kneser hypergraphs by Alon, Frankl, and Lovászs 1986, some important parameters such as colorability defect and equitable colorability defect were introduced in order to provide sharp lower bounds for the chromatic number of general r-uniform Kneser hypergraphs. As a generalization of many earlier results in this area, Azarpendar and Jafari 2023 introduced the s-th equitable r-colorability defect rm ecdr mathcalF , s; a parameter which provides a lower bound for the chromatic number of generalized Kneser hypergraphs rm KG r mathcalF , s. They proved the following nice inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm ecdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , and noted that it is plausible that the above inequality remains true if one replaces leftlfloor fracs2 rightrfloor with s. In this paper, considering the relation rm ecdr left mathcalF , x right geq rm cdr left mathcalF , x right which always holds, we show that even in the weaker inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm cdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , no number x greater than leftlfloor fracs2 rightrfloor could be replaced by leftlfloor fracs2 rightrfloor.

 After Lovászs break-through in determining the chromatic number of Kneser graphs 1978, and after extending this result to the chromatic number of r-uniform Kneser hypergraphs by Alon, Frankl, and Lovászs 1986, some important parameters such as colorability defect and equitable colorability defect were introduced in order to provide sharp lower bounds for the chromatic number of general r-uniform Kneser hypergraphs. As a generalization of many earlier results in this area, Azarpendar and Jafari 2023 introduced the s-th equitable r-colorability defect rm ecdr mathcalF , s; a parameter which provides a lower bound for the chromatic number of generalized Kneser hypergraphs rm KG r mathcalF , s. They proved the following nice inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm ecdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , and noted that it is plausible that the above inequality remains true if one replaces leftlfloor fracs2 rightrfloor with s. In this paper, considering the relation rm ecdr left mathcalF , x right geq rm cdr left mathcalF , x right which always holds, we show that even in the weaker inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm cdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , no number x greater than leftlfloor fracs2 rightrfloor could be replaced by leftlfloor fracs2 rightrfloor.

 After Lovászs break-through in determining the chromatic number of Kneser graphs 1978, and after extending this result to the chromatic number of r-uniform Kneser hypergraphs by Alon, Frankl, and Lovászs 1986, some important parameters such as colorability defect and equitable colorability defect were introduced in order to provide sharp lower bounds for the chromatic number of general r-uniform Kneser hypergraphs. As a generalization of many earlier results in this area, Azarpendar and Jafari 2023 introduced the s-th equitable r-colorability defect rm ecdr mathcalF , s; a parameter which provides a lower bound for the chromatic number of generalized Kneser hypergraphs rm KG r mathcalF , s. They proved the following nice inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm ecdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , and noted that it is plausible that the above inequality remains true if one replaces leftlfloor fracs2 rightrfloor with s. In this paper, considering the relation rm ecdr left mathcalF , x right geq rm cdr left mathcalF , x right which always holds, we show that even in the weaker inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm cdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , no number x greater than leftlfloor fracs2 rightrfloor could be replaced by leftlfloor fracs2 rightrfloor.

 After Lovászs break-through in determining the chromatic number of Kneser graphs 1978, and after extending this result to the chromatic number of r-uniform Kneser hypergraphs by Alon, Frankl, and Lovászs 1986, some important parameters such as colorability defect and equitable colorability defect were introduced in order to provide sharp lower bounds for the chromatic number of general r-uniform Kneser hypergraphs. As a generalization of many earlier results in this area, Azarpendar and Jafari 2023 introduced the s-th equitable r-colorability defect rm ecdr mathcalF , s; a parameter which provides a lower bound for the chromatic number of generalized Kneser hypergraphs rm KG r mathcalF , s. They proved the following nice inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm ecdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , and noted that it is plausible that the above inequality remains true if one replaces leftlfloor fracs2 rightrfloor with s. In this paper, considering the relation rm ecdr left mathcalF , x right geq rm cdr left mathcalF , x right which always holds, we show that even in the weaker inequality chi left rm KG r mathcalF , s right geq leftlceil frac rm cdr left mathcalF , leftlfloor fracs2 rightrfloor right r-1 rightrceil , no number x greater than leftlfloor fracs2 rightrfloor could be replaced by leftlfloor fracs2 rightrfloor.

Article Details

Regarding equitable colorability defect of hypergraphs

Authors:

Saeed Shaebani

Publisher:

Hacettepe University

Main Topics:

Mathematical Sciences

Journal:

Hacettepe Journal of Mathematics and Statistics Vol.53 Issue 1, pp.184-190

Document Type:

Article

Publication Date:

2/2024

Document Language:

English

Document ID (Org No.):

2001312255

pISSN:

2651-477X

hypergraph

generalized Kneser hypergraph

chromatic number

colorability defect

equitable colorability defectHypergraph

Generalized Kneser Hypergraph

Chromatic Number

Colorability Defect

Equitable Colorability Defect

Hypergraph

Generalized Kneser Hypergraph

Chromatic Number

Colorability Defect

Equitable Colorability Defect

Issues

Article Details

Authors: Saeed Shaebani

Publisher: Hacettepe University

Main Topics: Mathematical Sciences

Journal: Hacettepe Journal of Mathematics and Statistics Vol.53 Issue 1, pp.184-190

Document Type: Article

Publication Date: 2/2024

Document Language: English

Document ID (Org No.): 2001312255

pISSN: 2651-477X

Issues

Authors:

Saeed Shaebani

Publisher:

Hacettepe University

Main Topics:

Mathematical Sciences

Journal:

Hacettepe Journal of Mathematics and Statistics Vol.53 Issue 1, pp.184-190

Document Type:

Article

Publication Date:

2/2024

Document Language:

English

Document ID (Org No.):

2001312255

pISSN:

2651-477X