- Hacettepe Journal of Mathematics and Statistics
- Cilt: 53 Sayı: 1
- Regarding equitable colorability defect of hypergraphs
Regarding equitable colorability defect of hypergraphs
Authors : Saeed Shaebani
Pages : 184-190
Doi:10.15672/hujms.1254664
View : 119 | Download : 207
Publication Date : 2024-02-29
Article Type : Research
Abstract :After Lovász’s 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ász’s (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 ecd}^r (\\mathcal{F} , s)$; a parameter which provides a lower bound for the chromatic number of generalized Kneser hypergraphs ${\\rm KG} ^r (\\mathcal{F} , s)$. They proved the following nice inequality $$\\chi \\left( {\\rm KG} ^r (\\mathcal{F} , s) \\right) \\geq \\left\\lceil \\frac{ {\\rm ecd}^r \\left( \\mathcal{F} , \\left\\lfloor \\frac{s}{2} \\right\\rfloor \\right) }{r-1} \\right\\rceil ,$$ and noted that it is plausible that the above inequality remains true if one replaces $\\left\\lfloor \\frac{s}{2} \\right\\rfloor$ with $s$. In this paper, considering the relation ${\\rm ecd}^r \\left( \\mathcal{F} , x \\right) \\geq {\\rm cd}^r \\left( \\mathcal{F} , x \\right)$ which always holds, we show that even in the weaker inequality $$\\chi \\left( {\\rm KG} ^r (\\mathcal{F} , s) \\right) \\geq \\left\\lceil \\frac{ {\\rm cd}^r \\left( \\mathcal{F} , \\left\\lfloor \\frac{s}{2} \\right\\rfloor \\right) }{r-1} \\right\\rceil ,$$ no number $x$ greater than $\\left\\lfloor \\frac{s}{2} \\right\\rfloor$ could be replaced by $\\left\\lfloor \\frac{s}{2} \\right\\rfloor$.Keywords : Hypergraph, Generalized Kneser Hypergraph, Chromatic Number, Colorability Defect, Equitable Colorability Defect, Hypergraph, Generalized Kneser Hypergraph, Chromatic Number, Colorability Defect, Equitable Colorability Defect