Hitting Maximum Independent Sets in Bounded-Chromatic Graphs

Definitions and mathematical statement

Under the conventional interpretation that the graphs are finite, simple, and undirected, let $G=(V,E)$ be a nonempty graph and put $n=|V|$. These graph conventions are not explicitly specified in the supplied record. An independent set is a subset of $V$ containing no adjacent pair of vertices. Define \[ \alpha(G)=\max\{|I|:I\subseteq V\text{ is independent}\}, \qquad \mathcal M(G)=\{I\subseteq V:I\text{ is independent and }|I|=\alpha(G)\}. \] Let $\chi(G)$ be the least number of colors in a proper vertex coloring, and define \[ h(G)=\min\left\{|S|:S\subseteq V,\ S\cap I\ne\varnothing\text{ for every }I\in\mathcal M(G)\right\}. \] Thus the sets to be met are maximum independent sets, not merely inclusion-maximal independent sets.

The requested bounded-chromatic-number conjecture asks whether \[ \forall k\in{\mathbb{Z}}_{\ge1}\ \forall\varepsilon>0\ \exists N\in{\mathbb{Z}}_{\ge1}\ \forall G, \qquad \left(|V(G)|\ge N\ \text{and}\ \chi(G)\le k\right) \Longrightarrow h(G)\le\varepsilon |V(G)|. \] Here $G$ ranges over graphs with the conventions stated above, and $N$ may depend on $k$ and $\varepsilon$. Equivalently, for every sequence $(G_j)_{j\ge1}$ with $|V(G_j)|\to\infty$ and a uniform bound on $\chi(G_j)$, must \[ \frac{h(G_j)}{|V(G_j)|}\longrightarrow0? \] The growth condition on the orders makes explicit the asymptotic interpretation of the supplied statement. The original statement labels the problem open even when $\chi(G)=3$; the supplied dated assessment describes the case of $3$-colorable graphs as still open.

For context, the source attributes to Bollobás, Erdős, and Tuza (1991) the stronger conjecture that, for every sequence of graphs of orders $n_j\to\infty$, if there is a constant $c>0$ such that $\alpha(G_j)\ge c n_j$ for all sufficiently large $j$, then $h(G_j)/n_j\to0$.

The following additional remarks are preserved as supplied source claims, not as independently verified results. The source attributes to Hajnal (1965) the assertion that $\alpha(G)>n/2$ implies $h(G)=1$. It also describes graphs $G=G_n$ with \[ \alpha(G)>n/4,\qquad \chi(G)\le8,\qquad h(G)>n/2, \] and graphs with \[ \alpha(G)=\left(1/2-o(1)\right)n, \qquad h(G)>(\log n)^{0.999}. \] The source says that these constructions settle questions of Friedgut, Kalai, and Kindler, and of Dong and Wu, without supplying the precise questions. Finally, it states that regular graphs with $\alpha(G)>0.250001n$ satisfy the bound transcribed as $h(G)\le O(n\log n)$, and says that this applies in particular to regular $3$-colorable graphs.

These contextual bounds have unresolved transcription problems: a detached square-root sign occurs before the first construction, and another occurs before the regular-graph remark. Their intended placements and radicands cannot be recovered from the supplied text. Taken literally for unbounded graph orders, the displayed construction with $\chi(G)\le8$ and $h(G)>n/2$ would contradict the requested conjecture. No correction to either bound is assumed here; these remarks require source review before they can be used mathematically.

Short English statement

For each fixed bound on the chromatic number, must every sufficiently large graph have a set of vertices meeting every maximum independent set whose size is an arbitrarily small fraction of the graph's order? The supplied record presents this as a conjecture and labels the overall status partially solved. Corrupted square-root notation in the contextual claims prevents those claims from being interpreted reliably.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004982$, source problem code catalogue entry, title: "Hitting Maximum Independent Sets in Bounded-Chromatic Graphs." Project registry: data/unsolvedmath/problems.json; additional-record registry: catalog/problems.json. This draft uses the supplied complete record and does not claim an independent inspection of either registry file.
• Supplied report citation: Graph Theory (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/1, pp. 5--78. https://doi.org/10.4171/owr/2022/1. The record also calls this "Oberwolfach Report 1/2022" and gives proposed year 2022; the year discrepancy remains unresolved.
• Supplied literature source: "Bai, Chang, and Yan, hitting maximum independent sets." https://arxiv.org/abs/2608.18963. No further bibliographic details are supplied.
• Supplied literature source: "Oberwolfach Report 1/2022." https://doi.org/10.4171/owr/2022/1.
• Literature assessment dated exactly 2026-08-22: the record labels the status "partially solved" and states that the constant-chromatic-number relaxation remains open even for $3$-colorable graphs, while recent work establishes only restricted dense, regular, or highly connected cases. This is supplied dated curation, not an independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• Supplied historical attributions: Bollobás, Erdős, and Tuza (1991) for the stronger conjecture; Hajnal (1965) for the assertion concerning $\alpha(G)>n/2$; Friedgut, Kalai, and Kindler, and Dong and Wu for questions reportedly settled by the contextual constructions. Separate authoritative citations for these historical claims are not supplied. No proposer is identified for the relaxation.
• The registry labels the statement corrected_verified and reports that it was checked against the official Oberwolfach report. This is a supplied verification claim, not verification performed for this draft.