Semidefinite Bounds Beyond Fractional Chromatic Number

Definitions and mathematical statement

For the purpose of defining the standard parameters, consider a finite simple undirected graph $G=(V,E)$. This is a conventional interpretation: the supplied record does not explicitly specify the graph class or whether additional restrictions are intended. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number $\chi(G)$ is the minimum number of colors in such a coloring. Let $\mathcal I(G)$ denote the family of independent vertex sets of $G$. The fractional chromatic number is \[ \chi_f(G)=\min\left\{\sum_{I\in\mathcal I(G)}w_I:\ w_I\geq0\text{ for every }I\in\mathcal I(G),\quad \sum_{\substack{I\in\mathcal I(G)\\v\in I}}w_I\geq1\text{ for every }v\in V\right\}. \] In particular, $\chi_f(G)\leq\chi(G)$.

Requested construction. Obtain efficiently computable bounds for $\chi(G)$ that improve on $\chi_f(G)$, preferably expressible as compact semidefinite programs suitable for practical computation. A semidefinite program optimizes a linear function subject to affine constraints and positive semidefiniteness constraints on symmetric matrices.

One possible precise interpretation of the requested improvement is to construct a graph parameter $b$ satisfying \[ \chi_f(G)\leq b(G)\leq\chi(G) \] for every graph in the intended class, with strict inequality $\chi_f(G)<b(G)$ on a specified nonempty family, and with $b(G)$ obtainable from a compact semidefinite program. This interpretation is conditional, not an additional hypothesis supplied by the source. The record does not specify whether universal domination of $\chi_f$ is required, which graphs must exhibit strict improvement, or whether improvement must exceed the integer rounding of a lower bound.

The terms "efficiently computable," "compact," and "suitable for practical computation" have no quantitative definitions in the record. In particular, no bounds on program size, coefficient encoding length, approximation accuracy, running time, or numerical certification are supplied. The background also mentions bounds involving the Lovász theta number and stability or chromatic number, but supplies no corresponding formula or precise relationship to the displayed chromatic-number question. Consequently, the record specifies a research objective rather than a fully quantified existence assertion.

Short English statement

Seek practical, efficiently computable lower bounds on a graph's chromatic number that strengthen its fractional chromatic number, preferably through compact semidefinite programs. The intended graph class, strength of improvement, computational guarantees, and connection to the theta-number background remain unspecified. This is a statement-only draft requiring human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30001104$, title "Semidefinite Bounds Beyond Fractional Chromatic Number," exact source problem code catalogue entry; collection: Oberwolfach Reports Open Problems. No individual proposer is supplied. The proposed year is recorded as 2008.
• Supplied report citation: Combinatorial Optimization (2009), Oberwolfach Reports, pp. 2875--2942, DOI 10.4171/owr/2008/51. https://doi.org/10.4171/owr/2008/51. The background describes these reports as documenting mathematical workshops and their open-problem discussions. This URL is also supplied under the literature-source label "original Oberwolfach report."
• Supplied literature source labeled "Dukanovic--Rendl strengthening": https://optimization-online.org/?p=9934.
• Supplied literature source labeled "dual Hoffman bounds": https://doi.org/10.1137/19M1306427.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that semidefinite-programming hierarchies and copositive strengthenings exist, while the requested compact, broadly useful solution remains open. This is supplied dated curation, not an independently verified assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and explains that the complete statement was preserved while publication formatting was normalized. These are supplied editorial labels, not independent mathematical verification by this draft.