Uniquely-covered induced path in triangle-free graphs

Question (uniquely-covered vertices in an induced path) · arXiv:1702.01094

arXiv Question medium confidence— first stated 2017-07-03

Status open high confidence

The Question asks whether every triangle-free graph with very large chromatic number admits, for any stable-set cover of its vertices, an induced path whose vertices are each uniquely covered by some member of the cover. This strictly generalizes the paper's main rainbow-path theorem (proper colorings are a special case) and remains open. The closely related proper-coloring variant (the Aravind conjecture on induced rainbow paths of length k) has seen partial progress: a 2026 preprint improves the lower bound on the rainbow path length from (log log log k)^{1/3-o(1)} to (log k)^{1/2-o(1)}, but neither this nor any other identified work addresses the uniquely-covered formulation with arbitrary stable-set covers.

Cited literature (1)

partial Towards a conjecture on long induced rainbow paths in triangle-free graphs (2026)

Julien Duron, Jean-Florent Raymond · arXiv preprint · arXiv:2601.00602

Improves the lower bound on induced rainbow path length in triangle-free graphs from (log log log k)^{1/3-o(1)} to (log k)^{1/2-o(1)}, and shows the path can see at least k/2 colors, advancing the proper-coloring special case of the question but not the general stable-set-cover formulation.

Reviewer notes. The Question in 1702.01094 is a strict generalization of the paper's own main theorem: a proper k-coloring is a partition into stable sets where each path vertex is trivially uniquely covered by its color class, so any resolution of the Question implies the rainbow-path conjecture. No paper found after 2017 addresses this general uniquely-covered formulation directly; progress in the literature (arXiv:2601.00602) targets only the proper-coloring variant.

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

Question. Let $G$ be a triangle-free graph with very large chromatic number, and let $\mathcal{A}$ be a set of stable subsets (not necessarily pairwise disjoint) of $V(G)$ with union $V(G)$. Does there necessarily exist an $s$-vertex induced path $P$ of $G$ such that for each $v\in V(P)$, some $X\in\mathcal{A}$ satisfies $X\cap V(P)=\{v\}$?

Context

The authors pose this as an additional open question in the Conclusion, asking whether a large chromatic number forces an induced path whose vertices are each 'uniquely covered' by some member of an arbitrary stable-set cover.

Notes. Stated as prose in the Conclusion with 'another question to which we do not know the answer'.

Source paper

Induced subgraphs of graphs with large chromatic number. IX. Rainbow paths
Alex Scott, Paul Seymour · 2017-07-03
https://arxiv.org/abs/1702.01094 PDF source