A new lower bound for the chromatic number of general Kneser hypergraphs. (June 2018)
- Record Type:
- Journal Article
- Title:
- A new lower bound for the chromatic number of general Kneser hypergraphs. (June 2018)
- Main Title:
- A new lower bound for the chromatic number of general Kneser hypergraphs
- Authors:
- Abyazi Sani, Roya
Alishahi, Meysam - Abstract:
- Abstract: A general Kneser hypergraph KG r ( H ) is an r -uniform hypergraph that somehow encodes the edge intersections of a ground hypergraph H . The colorability defect of H is a combinatorial parameter providing a lower bound for the chromatic number of KG r ( H ), which is addressed in a series of works by Dol'nikov (1988), Kříž (1992) and Ziegler (2002). In this paper, we define a new combinatorial parameter, the equitable colorability defect of hypergraphs, which provides some common improvements upon these works. Roughly speaking, we propose a new lower bound for the chromatic number of general Kneser hypergraphs which substantially improves Ziegler's lower bound. It is always as good as Ziegler's lower bound and several families of hypergraphs for which the difference between these two lower bounds is arbitrary large are provided. This specializes to a substantial improvement of the Dol'nikov–Kříž lower bound for the chromatic number of general Kneser hypergraphs as well. Furthermore, we prove a result ensuring the existence of a colorful subhypergraph in any proper coloring of general Kneser hypergraphs that strengthens Meunier's result (Meunier, 2014).
- Is Part Of:
- European journal of combinatorics. Volume 71(2018)
- Journal:
- European journal of combinatorics
- Issue:
- Volume 71(2018)
- Issue Display:
- Volume 71, Issue 2018 (2018)
- Year:
- 2018
- Volume:
- 71
- Issue:
- 2018
- Issue Sort Value:
- 2018-0071-2018-0000
- Page Start:
- 229
- Page End:
- 245
- Publication Date:
- 2018-06
- Subjects:
- Combinatorial analysis -- Periodicals
Analyse combinatoire -- Périodiques
Combinatorial analysis
Periodicals
Electronic journals
511.6 - Journal URLs:
- http://www.sciencedirect.com/science/journal/01956698 ↗
http://www.elsevier.com/journals ↗
http://www.idealibrary.com ↗
http://firstsearch.oclc.org ↗
http://firstsearch.oclc.org/journal=0195-6698;screen=info;ECOIP ↗ - DOI:
- 10.1016/j.ejc.2018.03.007 ↗
- Languages:
- English
- ISSNs:
- 0195-6698
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3829.728200
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 6518.xml