Clustered Colorings of Triangulated Grids

Definitions and mathematical statement

For a finite graph $G$ and integer $k\geq1$, define its $k$-color cluster bound by \[ \xi_k(G)=\min_{c:V(G)\to\{1,\ldots,k\}} \max\{|V(C)|:C\text{ is a connected component of }G[c^{-1}(j)],\ 1\leq j\leq k\}. \] This is equivalent to bounding every monochromatic connected subgraph. The coloring need not be proper and may use fewer than $k$ colors. The parameter counts vertices, not diameter or edges.

Let $[n]=\{1,\ldots,n\}$, and retain $T_n^d$ for the intended triangulated $d$-dimensional grid, usually its one-skeleton with vertex set $[n]^d$. Define the layers, as in the source, by \[ L_n^d(i)=\{x\in[n]^d:\sum_{j=1}^d x_j=i\}. \] The nonempty layer indices lie between $d$ and $dn$. The allowed triangulations, grid diagonals and boundary conventions, and the index $i_{1/2}$, are not defined in the record.

There are two conjectures. First, the worst-case value of $\xi_2(T_n^d)$ is asserted to be \[ |L_n^d(i_{1/2})|, \] so that the intended diagonal-layer coloring is optimal. To express the quantifier, if $\mathfrak T_{n,d}$ is the missing allowed triangulation class, put $F_k(n,d)=\sup_{T\in\mathfrak T_{n,d}}\xi_k(T)$; the first claim is $F_2(n,d)=|L_n^d(i_{1/2})|$. The index is retained symbolically, without guessing a median/floor convention, and no unprovided coloring construction is asserted to work for every triangulation.

Second, for fixed $d$ and $3\leq k\leq d-1$, the stated order is $n^{d-k+1}$. In a worst-case interpretation this means constants $c_{d,k},C_{d,k}>0$ and $n_0$ such that \[ c_{d,k}n^{d-k+1}\leq F_k(n,d)\leq C_{d,k}n^{d-k+1} \quad(n\geq n_0). \] If the source instead fixes one canonical triangulation or asks for such bounds for every allowed triangulation, those are different formulations. Its second sentence does not explicitly repeat the worst-case quantifier. The degree range is retained exactly and is nonempty only for $d\geq4$; no statement for $k=d$ or other missing values is added.

The literature triage checked 2026-08-21 reports no authoritative complete resolution found. The open label and verification note preserving both conjectures remain dated metadata, not independently checked current results.

Short English statement

The first conjecture identifies the worst two-color cluster size with a specified diagonal layer. The second predicts exponent $d-k+1$ for fixed intermediate color counts. The graph parameter is explicit, but the triangulation class, middle-layer index and worst-case scope of the second conjecture are missing.

Sources

• Local UnsolvedMath registry, permanent ID 30000688, source code catalogue entry, "Clustered Colorings of Triangulated Grids," including both original conjectures, cleaned definitions and verification metadata.
• Geometric and Topological Combinatorics (2007), Oberwolfach Reports, pp. 195--272, DOI 10.4171/owr/2007/04: https://doi.org/10.4171/owr/2007/04. This is also the sole supplied literature reference.
• Literature triage checked 2026-08-21; record updated 2026-09-16. No external source has been visited or independently checked here.