η-boundedness for two-star unions
Open problem on $\eta$-boundedness for disjoint union of two stars · arXiv:2302.04986
Status open high confidence
The open problem of whether $(S_a \cup S_b)$-free graphs are $\eta$-bounded for all $a,b \geq 1$ remains unresolved. No paper resolving this specific conjecture was found in the indexed literature. A related paper (arXiv:2403.19737) resolves a different conjecture from the same source paper, concerning graphs without large induced matchings, confirming activity in this area but leaving the disjoint-union-of-stars question open.
Reviewer notes. arXiv:2403.19737 ('Piercing independent sets in graphs without large induced matching') resolves a different conjecture from the same source paper (about $2K_2$-free or bounded induced matching graphs), not the disjoint-union-of-stars η-boundedness question. The source paper itself notes the analogy with the Gyárfás–Sumner conjecture: for χ-boundedness, H-free classes reduce to component-free classes, but the analogous reduction for η-boundedness (Conjecture 1.8) is unknown. No follow-up found in the indexed literature for the specific open problem.
Context
For the Gyárfás–Sumner conjecture, $\chi$-boundedness of an $H$-free class reduces to $\chi$-boundedness of the component-free classes. The authors do not know whether the analogous reduction holds for Conjecture 1.8, and in particular whether the disjoint union of two stars satisfies $\eta$-boundedness.
Notes. Stated as 'it remains open' in prose following Conjecture 1.13, without a labelled environment.
Source paper
Hitting all maximum stable sets in $P_5$-free graphs
Sepehr Hajebi, Yanjia Li, Sophie Spirkl · 2024-01-16
https://arxiv.org/abs/2302.04986