Nondominating broom copy in χ-bounded graphs

Conjecture 2.3 · arXiv:2202.10412

arXiv Conjecture high confidence— first stated 2023-03-22

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Status open high confidence

Conjecture 2.3 from arXiv:2202.10412 would extend the self-isolating property (proved for paths as Corollary 2.4 of the same paper) to brooms, asserting that a graph of sufficiently large chromatic number relative to its clique number and containing no (ψ,q)-scattering must contain a σ-nondominating copy of any given broom H. The authors themselves described it as 'an appealing possible strengthening of 2.2 that we could not prove.' No subsequent paper resolving or substantially advancing this conjecture was found in the literature through May 2026.

Reviewer notes. No follow-up found. Sophie Spirkl's arXiv listing (arxiv.org/a/spirkl_s_1.html) and Paul Seymour's publication page show no paper specifically addressing sigma-nondominating broom copies or (psi,q)-scattering after 2023. The related 2025 preprint arXiv:2504.21127 (Nguyen, 'On Polynomially High-Chromatic Pure Pairs') extends broom-related poly-chi-bounding results but does not reference Conjecture 2.3 or the scattering/nondominating framework.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $\psi, \sigma : \mathbb{N} \to \mathbb{N}$ be non-decreasing polynomials, let $q \geq 0$ an integer, and let $H$ be a broom. Then there is a non-decreasing polynomial $\phi : \mathbb{N} \to \mathbb{N}$ such that if $G$ is a graph, and $\chi(G) > \phi(\omega(G))$, and $G$ contains no $(\psi, q)$-scattering, then $G$ [contains] a $\sigma$-nondominating copy of $H$.

Context

The authors remark that Conjecture 2.3 is 'an appealing possible strengthening of 2.2 that we could not prove.' Theorem 2.2 (which is proved) requires $H$ to be a broom and $J$ a path, finding both; Conjecture 2.3 would give a $\sigma$-nondominating copy of a broom alone without needing a path. This would extend the self-isolating property (proved for paths as Corollary 2.4) to brooms.

Notes. PDF extraction: the phrase 'then G a σ-nondominating copy of H' is missing the word 'contains'; reconstructed in brackets. Statement otherwise clear.

Source paper

Polynomial bounds for chromatic number VI. Adding a four-vertex path
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · 2023-03-22
https://arxiv.org/abs/2202.10412 PDF source