A counterexample to a conjecture on the chromatic number of r-stable Kneser hypergraphs

Research output: Journal PublicationArticlepeer-review

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 languageEnglish
Pages (from-to)762-766
Number of pages5
JournalJournal of Graph Theory
Volume103
Issue number4
DOIs
Publication statusPublished - 26 Feb 2023

Keywords

  • chromatic number
  • colorability defect
  • kneser hypergraphs

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A counterexample to a conjecture on the chromatic number of r-stable Kneser hypergraphs'. Together they form a unique fingerprint.

Cite this