Color Bounds for Weight-Modified Reed Fractional Coloring

Definitions and mathematical statement

For reference, in the conventional setting of a finite simple graph $G=(V,E)$, let $\mathcal I(G)$ be the family of independent vertex sets. A fractional coloring assigns a weight $x_I\in{\mathbb{R}}_{\geq 0}$ to each $I\in\mathcal I(G)$ such that \[ \sum_{\substack{I\in\mathcal I(G)\\v\in I}}x_I\geq 1 \qquad\text{for every }v\in V. \] Its total weight, interpreted as the fractional number of colors used, is \[ W(x)=\sum_{I\in\mathcal I(G)}x_I. \] The supplied record does not specify the intended graph class, so this conventional setting is explanatory and is not a recovered source hypothesis.

Let $\mathcal G$ stand for the intended, unspecified class of admissible input graphs, and let $A$ stand for the procedure called the "weight-modified Reed fractional-coloring algorithm" in the supplied record. Write $x^A(G)$ for its output when that output is defined. The source question has the following formal template: does $A$, on every admissible input $G\in\mathcal G$, return a fractional coloring satisfying \[ W\left(x^A(G)\right)\leq \max_{v\in V(G)}\gamma_\ell(v)? \] Here $\gamma_\ell(v)$ is retained exactly as supplied. Neither its definition nor the meaning of the subscript $\ell$ is given. The algorithm, its weight modification, any additional input data, and any rules governing its choices are also absent. Consequently, this is an unresolved formal template, not a fully specified conjecture. In particular, the treatment of an empty vertex set and the quantification over any algorithmic choices remain unspecified.

The source additionally asks whether better bounds can be proved. It supplies neither a candidate stronger bound nor a criterion for improvement, and does not say whether improvement must concern this algorithm or fractional coloring more generally.

The accompanying literature assessment concerns a "clique-averaged fractional inequality" described as Conjecture 7. No formula for that inequality, or equivalence between it and the algorithmic question above, is supplied. These formulations therefore cannot be identified on the available evidence.

Short English statement

The question asks whether a named modification of Reed's fractional-coloring algorithm always produces a coloring whose total weight is at most $\max_{v\in V(G)}\gamma_\ell(v)$, and whether stronger bounds are possible. The record does not define the algorithm, $\gamma_\ell$, or the admissible inputs. Its accompanying discussion of a clique-averaged conjecture does not establish that this is the same question.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $30002272$, title "Color Bounds for Weight-Modified Reed Fractional Coloring," exact source problem code catalogue entry, proposed year $2013$. No individual proposer is identified.
• Supplied report citation: Graph Theory (2013), Oberwolfach Reports, pp. 67--128, DOI 10.4171/owr/2013/02. https://doi.org/10.4171/owr/2013/02. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions; no specific problem page is supplied.
• Supplied literature source, labeled "Edwards--King, clique-averaged conjecture": https://doi.org/10.37236/2666. The record does not provide the conjecture's formula or establish its relationship to the algorithmic question.
• Supplied literature source, labeled "original Oberwolfach report": https://doi.org/10.4171/owr/2013/02.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open, says that the clique-averaged fractional inequality is stated as Conjecture 7, and reports that the report gives no proof and that no general resolution was found. This is supplied dated curation, not an independently verified literature assessment. The background expressly calls for independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that its mathematical content was checked against the official Oberwolfach report, with notation, context, and question form normalized without changing the source-level claim. This is supplied verification metadata; no independent source verification is asserted here.