Abstract
Let (Formula presented.) be a set of subsets of (Formula presented.) and (Formula presented.) be an integer. The (Formula presented.) -colorability defect (Formula presented.) of (Formula presented.) is the least number of elements of (Formula presented.) that need to be removed such that the remaining ground set can be (Formula presented.) -colored without inducing monochromatic sets in (Formula presented.). The set (Formula presented.) is a subset of (Formula presented.) containing all elements (Formula presented.) of (Formula presented.) such that any two members of (Formula presented.) are at least at distance (Formula presented.) apart on the (Formula presented.) -cycle. The main purpose of this note is to give a counterexample to a conjecture raised by Florian Frick, which says if (Formula presented.) is a set of subsets of (Formula presented.) and (Formula presented.), then the number of blocks needed to partition the elements of (Formula presented.) such that no (Formula presented.) pairwise disjoint sets lie in the same block is at least (Formula presented.).
Original language | English |
---|---|
Pages (from-to) | 762-766 |
Number of pages | 5 |
Journal | Journal of Graph Theory |
Volume | 103 |
Issue number | 4 |
DOIs | |
Publication status | Published - 26 Feb 2023 |
Keywords
- chromatic number
- colorability defect
- kneser hypergraphs
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics