Triangle-Cone Characterization of Graphs

Definitions and mathematical statement

For this draft, use the convention that $G=(V,E)$ is a finite simple undirected graph. The supplied statement does not explicitly specify these graph conventions, so their intended scope requires confirmation. Let \[ \mathcal T(G)=\{T\subseteq V: |T|=3,\ \tbinom{T}{2}\subseteq E\} \] be its set of triangles. For $T\in\mathcal T(G)$, define its edge incidence vector $\chi^T\in{\mathbb{R}}^E$ by \[ \chi^T_e=\begin{cases}1,&e\in\binom{T}{2},\\0,&e\notin\binom{T}{2}.\end{cases} \] The triangle cone is \[ C_\triangle(G)=\left\{\sum_{T\in\mathcal T(G)}\lambda_T\chi^T:\lambda_T\in{\mathbb{R}}_{\geq0}\text{ for every }T\in\mathcal T(G)\right\}. \] Write $\mathbf1_E\in{\mathbb{R}}^E$ for the vector whose every coordinate equals $1$.

Graph characterization problem. Characterize the graphs $G$ for which $\mathbf1_E\in C_\triangle(G)$. Explicitly, characterize when there exist nonnegative real triangle weights satisfying \[ \exists (\lambda_T)_{T\in\mathcal T(G)}\in{\mathbb{R}}_{\geq0}^{\mathcal T(G)}\quad\forall e\in E,\qquad \sum_{\substack{T\in\mathcal T(G)\\e\in\binom{T}{2}}}\lambda_T=1. \] Such weights are called a fractional triangle decomposition. Empty sums are zero; thus the displayed condition is vacuous when $E=\varnothing$, whereas an edge belonging to no triangle cannot satisfy its equation.

Related cone characterization problem. For each $G$, characterize linear inequalities defining $C_\triangle(G)$: give a graph-dependent description of a family $\mathcal A(G)\subseteq{\mathbb{R}}^E$ such that \[ C_\triangle(G)=\left\{x\in{\mathbb{R}}^E:\sum_{e\in E}a_ex_e\geq0\text{ for every }a\in\mathcal A(G)\right\}. \] The source calls these two characterization tasks equivalent. A description of the entire cone provides a criterion for membership of $\mathbf1_E$, but a characterization restricted to that vector does not, by itself, specify the entire cone. The intended sense of equivalence, and the desired form of the characterization, remain unresolved. The supplied record describes a broad research program, not a single proposed necessary-and-sufficient theorem.

Short English statement

Characterize graphs whose triangles can be assigned nonnegative real weights so that every edge receives total weight exactly $1$. The source also asks for defining inequalities for the full cone of triangle incidence vectors. The graph conventions and the asserted equivalence between these targets require review. The supplied open label is a dated curation assessment.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002727$, title Triangle-Cone Characterization of Graphs, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2014.
• Original OWR report: Combinatorial Optimization (2015), Oberwolfach Reports, pp. 2873--2932, DOI 10.4171/owr/2014/51. Supplied link: https://doi.org/10.4171/owr/2014/51. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2015 label is retained alongside the supplied 2014 proposed year and DOI.
• Supplied literature reference labeled "Dross, fractional triangle decompositions": https://doi.org/10.1137/15M1014310. No additional bibliographic details or precise theorem from this reference are supplied.
• Literature assessment dated exactly 2026-08-21: the supplied status is open. The supplied assessment describes a broad research program about packing, covering, and transversals rather than one resolved proposition, and describes the triangle-cone problem as remaining part of an active body of work. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. Time-sensitive status and cited claims require independent verification.
• The registry labels the statement corrected_verified and reports that it was checked against the official Oberwolfach report and preserves that report's hypotheses, notation, and open mathematical target. These are supplied verification claims; no independent source verification is asserted here.