Symmetric Relation Coloring and Bounded Monochromatic Components

Definitions and mathematical statement

Two coloring questions. Determine whether the problem denoted $(4,C)$-SymRelCol has a sudden hardness jump, and determine the asymptotic order of $g(6,n)$, the least integer $g$ for which every $n$-vertex graph of maximum degree at most $6$ has a two-coloring with all monochromatic components of order at most $g$. The two requests are retained without asserting an unstated equivalence between them.

In the standard finite simple undirected graph convention, for $n\ge1$ define\[g(6,n)=\max_{\substack{|V(G)|=n\\\Delta(G)\le6}}\ \min_{c:V(G)\to\{0,1\}}\ \max\{|V(H)|:H\text{ is a connected component of }G[c^{-1}(i)],\ i\in\{0,1\}\}.\] The color classes need not be independent sets. A monochromatic component is a connected component of the induced subgraph of one color, and its order counts vertices, not edges, diameter, or number of components. The target is the growth rate as $n\to\infty$, with bounds uniform over all such graphs; no proposed asymptotic formula is supplied. The interpretation of maximum degree $6$ as an upper bound is explicit.

$(4,C)$-SymRelCol is not defined in the record. Its instance and output specification, roles of $4$ and $C$, allowed range of $C$, and whether $C$ is fixed or input data are missing. A sudden hardness jump also requires a precise threshold claim, computational model, complexity classes, and reductions. The name alone does not justify identifying it with the second two-coloring problem or assigning a guessed polynomial-time versus hardness dichotomy.

The supplied triage checked 2026-08-21 labels the combined item open and reports no located complete resolution. The report is its only source and no precise later theorem is reproduced. This dated assessment requires independent verification, particularly for the undefined decision-problem part.

Short English statement

One task asks for a complexity transition in an undefined named coloring problem; the other asks how small the largest monochromatic component can always be made in a two-coloring of a degree-six graph. The latter is formalized as a worst-case extremal function, without guessing an asymptotic answer.

Sources

• Local UnsolvedMath registry, permanent ID 30000611, code catalogue entry; Symmetric Relation Coloring and Bounded Monochromatic Components, Oberwolfach Reports Open Problems.
• Combinatorics, Probability and Computing (2007), Oberwolfach Reports, DOI 10.4171/owr/2006/48, pp. 2875--2952. https://doi.org/10.4171/owr/2006/48. Proposed year and year tag: 2006; no proposer named.
• The same full report is the sole supplied literature source; no definition of SymRelCol or separate authoritative complexity theorem is supplied.
• Literature triage checked 2026-08-21, status open; record updated 2026-09-16. The corrected_verified field reports source checking, not independently verified here.