Maximum Clique in Proper Vertex-Minor-Closed Classes

Definitions and mathematical statement

Use the conventional setting of finite simple undirected graphs; this domain is not explicitly specified in the supplied record and requires confirmation against the original source. Let $\mathfrak G$ denote the class of such graphs. For $G\in\mathfrak G$ and $v\in V(G)$, local complementation at $v$ toggles adjacency between every pair of distinct neighbors of $v$, leaving all other adjacencies unchanged. A graph $H$ is a vertex-minor of $G$ if it is isomorphic to a graph obtained from $G$ by a finite sequence of local complementations and vertex deletions, allowing an empty sequence.

A graph class $\mathcal F\subseteq\mathfrak G$ is closed under isomorphism if every graph isomorphic to a member also belongs to $\mathcal F$. It is closed under vertex-minors if every vertex-minor of each member belongs to $\mathcal F$. Interpret proper as $\mathcal F\subsetneq\mathfrak G$. Define the clique number by \[ \omega(G)=\max\left\{|S|:S\subseteq V(G),\ \text{every two distinct vertices of }S\text{ are adjacent}\right\}. \] In particular, $\omega(G)=0$ for the graph with no vertices.

Question. For every proper graph class $\mathcal F$ closed under isomorphism and vertex-minors, does there exist an algorithm $A_{\mathcal F}$ and a polynomial $p_{\mathcal F}$ such that, for every input graph $G\in\mathcal F$, the algorithm outputs $\omega(G)$ within $p_{\mathcal F}(|V(G)|+1)$ steps, using a standard explicit graph encoding?

Here $\mathcal F$ is fixed before the algorithm is chosen, and both the algorithm and its polynomial bound may depend on $\mathcal F$. Membership in $\mathcal F$ is treated as an input promise; no recognition algorithm for $\mathcal F$ is requested. These complexity conventions make the usual reading explicit, but the supplied record does not expressly discuss uniformity, encoding, or behavior on inputs outside $\mathcal F$. The requested output is the size of a maximum clique. The supplied record labels the problem open; that label is not an independently verified mathematical conclusion.

Short English statement

For each fixed proper class of finite simple undirected graphs closed under vertex-minors and isomorphism, can the size of a maximum clique be computed in polynomial time on graphs promised to belong to the class? The graph domain and algorithmic conventions are standard interpretations requiring source confirmation.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004040$, title Maximum Clique in Proper Vertex-Minor-Closed Classes, exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the recorded proposed year is 2019.
• Supplied report citation: Graph Theory (2020), Oberwolfach Reports, DOI 10.4171/owr/2019/1, pp. 5--63. https://doi.org/10.4171/owr/2019/1. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2020 title date and the record's 2019 year information are retained without reconciliation.
• Supplied literature reference: McCarty, Local Structure for Vertex-Minors. https://dspacemainprd01.lib.uwaterloo.ca/server/api/core/bitstreams/a3790341-2224-4c60-b8a6-34dc44a88c07/content.
• Supplied literature reference: Vertex-minors survey. https://sangiloum.github.io/legacy/2024/03/2023vertexminors-survey-revised.pdf.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that the polynomial-time maximum-clique conjecture remains open beyond special classes such as circle graphs and bounded rank-width. This is supplied dated curation derived from the OWR material, not independently verified here. The background expressly requests independent verification of time-sensitive status and cited claims.
• The registry assigns the statement status corrected_verified, explaining that notation, typography, duplicate clauses, or omitted definitions were repaired while preserving mathematical content. This is a supplied editorial assertion, not independent mathematical or source verification of this draft.