Hamiltonicity of Highly Connected Induced-Star-Free Graphs

Definitions and mathematical statement

For a conventional interpretation, let graphs be finite, simple, and undirected, and let the parameter range over integers $k\geq 3$. These conventions are not explicitly specified in the supplied statement and require confirmation. For an integer $t\geq 1$, a graph $G$ is $t$-vertex-connected if $|V(G)|\geq t+1$ and deleting any set of fewer than $t$ vertices leaves a connected graph. The star $K_{1,k}$ has one centre adjacent to $k$ leaves and no edges between distinct leaves. A graph is induced-$K_{1,k}$-free if no subset of its vertices induces a graph isomorphic to $K_{1,k}$. A Hamiltonian cycle is a cycle of length at least three containing every vertex of the graph; a graph is Hamiltonian if it contains such a cycle.

Under these conventions, the question attributed to Alexey Pokrovskiy in the supplied report passage, labelled Conjecture 4, is whether \[ \exists f:\{3,4,5,\ldots\}\longrightarrow\mathbb Z_{\geq 1}\quad \forall k\geq 3\quad\forall G,\qquad \left(G\text{ is }f(k)\text{-vertex-connected and induced-}K_{1,k}\text{-free}\right) \Longrightarrow G\text{ is Hamiltonian}. \] The source does not explicitly give the domain or codomain of $f$, or the graph conventions; the displayed formulation is therefore a provisional conventional interpretation rather than a resolution of these omissions.

For context, a graph is claw-free if it is induced-$K_{1,3}$-free. The supplied passage states the Matthews--Sumner conjecture as: every $4$-vertex-connected claw-free graph is Hamiltonian. Its wording that this asks whether $f(3)\leq 4$ is understood as asking whether an admissible connectivity threshold at $k=3$ can be chosen at most $4$; no minimality of the function $f$ is specified. The passage further attributes to Ryjáček the assertion that an admissible threshold at $k=3$ exists and is at most $7$. These are retained as supplied contextual claims, without independent verification.

Short English statement

The question asks whether, for each intended star size $k$, sufficiently high vertex connectivity forces every graph with no induced $K_{1,k}$ to have a cycle through all its vertices. The displayed interpretation uses finite simple undirected graphs and $k\geq 3$, conventions requiring confirmation. The supplied record labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30006558$, title Hamiltonicity of Highly Connected Induced-Star-Free Graphs, exact source code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year $2026$. Its original passage names Alexey Pokrovskiy, although its structured proposer field is empty.
• Combinatorics (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/1, pp. 5--79: https://doi.org/10.4171/owr/2026/1. Also supplied under the literature-source label "Oberwolfach Report 1/2026." The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The extracted passage labels this question Conjecture 4.
• Carraher et al., Forbidden subgraphs and Hamiltonicity: https://doi.org/10.1016/j.disc.2021.112522. This is a supplied literature-review reference; the record provides no more detailed attribution of its results.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that the Matthews--Sumner conjecture remains unresolved, with known results only under stronger connectivity or extra structural hypotheses. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment; the record expressly calls for independent verification of time-sensitive status and cited claims.
• The registry marks the statement corrected_verified and reports that the official report was checked, the question isolated from surrounding exposition, and notation repaired. These are supplied verification claims, not checks performed for this draft. The passage's reference label [1] for the Matthews--Sumner conjecture is not accompanied by its bibliographic entry, and no separate bibliographic citation for the attributed Ryjáček result is supplied.