Stable Label Patterns on Graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a graph in the intended class of graphs, which is not specified in the supplied record. A vertex labeling is a map \[ \ell:V\longrightarrow\{+,-,0\}, \] where the three labels are treated as symbols. The record refers to a graph-based pattern system and to stability but supplies neither the system nor a definition of stability. Consequently, the set \[ \mathcal S(G)\subseteq\{+,-,0\}^{V} \] of stable patterns cannot be determined from the supplied information. Here $\mathcal S(G)$ is only a placeholder for the stable patterns of the intended system, including any admissibility conditions that system imposes.

The record also invokes trivial symmetries without identifying them or their action on labelings. Write $\ell_1\sim_G\ell_2$ provisionally for equivalence under those intended symmetries; this notation does not specify an equivalence relation from the available data.

Subject to supplying these missing definitions, the two requested questions have the following schematic form:

1. Characterize all graphs $G$ in the intended graph class for which \[ \mathcal S(G)\ne\varnothing. \]
2. Determine whether there exist a graph $G$ in that class and two patterns $\ell_1,\ell_2\in\mathcal S(G)$ such that \[ \ell_1\not\sim_G\ell_2. \]

No restriction to finite, simple, directed, undirected, connected, or weighted graphs is supplied. No dynamical equations, parameter ranges, boundary conditions, stability criterion, or rule excluding a trivial labeling is supplied. These omissions prevent a fully specified mathematical statement; the displayed questions preserve the supplied targets without choosing the missing hypotheses.

Short English statement

The problem asks which graphs admit stable vertex patterns with labels $+, -, 0$, and whether one graph can admit two such patterns unrelated by the intended trivial symmetries. The governing system, stability criterion, graph class, and symmetries must be recovered before either question is mathematically precise.

Sources

• Local UnsolvedMath registry record, permanent ID $30002254$, title Stable Label Patterns on Graphs, source problem code catalogue entry; supplied as part of the Oberwolfach Reports Open Problems collection. Project registry locations are data/unsolvedmath/problems.json and catalog/problems.json; their contents have not been independently inspected for this draft.
• Supplied source citation: Dynamics of Patterns (2013), Oberwolfach Reports, pp. 3549--3633, DOI 10.4171/owr/2012/60. Supplied source and literature link: https://doi.org/10.4171/owr/2012/60. The literature-source label is Dynamics of Patterns, Oberwolfach Report 60/2012. The record gives proposed year 2012 and does not name a proposer.
• Supplied literature assessment, checked on 2026-08-21: the record labels the problem open, states that the report gives examples such as stars while leaving graph classification and multiplicity open, and reports that no later general solution was located. This is supplied dated curation, not an independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified, with the supplied verification claim that the official report explicitly poses both the existence/classification and nontrivial-multiplicity questions. This claim is recorded as source metadata and has not been independently verified here.