Uniquely-covered induced path in triangle-free graphs

AX_large_chromatic_induced_path_uniquely_covered

Source: arXiv:1702.01094 — Induced subgraphs of graphs with large chromatic number. IX. Rainbow paths

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

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

Status ai-disproved high confidence

For every s at least 3, there are triangle-free graphs of arbitrarily large chromatic number with a stable-set cover for which no s-vertex induced path has the required private-cover property.

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.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

AI-generated write-up ai-disproved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

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