Three-Color Edge-Folkman Numbers for Triangles

Definitions and mathematical statement

Work with finite simple undirected graphs, the conventional interpretation of the supplied graph terminology. For such a graph $G=(V,E)$, its order is $|V|$. Let $K_t$ denote the complete graph on $t$ vertices. Write \[ G\longrightarrow(K_3)^3 \] if, for every map $c:E\to\{1,2,3\}$, there exist distinct vertices $x,y,z\in V$ such that $xy,xz,yz\in E$ and \[ c(xy)=c(xz)=c(yz). \] The coloring need not use all three colors. Say that $G$ is $K_4$-free if it contains no subgraph isomorphic to $K_4$, whether induced or otherwise.

The supplied statement asks for good bounds on the order of a graph satisfying $G\longrightarrow(K_3)^3$, but does not explicitly impose a host restriction or specify a minimum. Interpreting the requested order as the smallest possible order gives the unrestricted parameter \[ m_3=\inf\left\{|V(G)|:G\text{ is a finite simple undirected graph and }G\longrightarrow(K_3)^3\right\}. \] In contrast, the supplied background and literature assessment explicitly describe a $K_4$-free edge-Folkman question. Under that additional restriction, the corresponding parameter is \[ F_e(3,3,3;4)=\inf\left\{|V(G)|:G\text{ is a finite simple undirected graph},\ K_4\nsubseteq G,\ G\longrightarrow(K_3)^3\right\}. \] Here the infimum of an empty set is understood as $+\infty$; for a nonempty set of possible orders it is its least element.

Problem, with unresolved qualification. Obtain good lower and upper bounds on the smallest possible order of the intended host graph. The literal statement leads to $m_3$, whereas the supplied background leads to $F_e(3,3,3;4)$. The record does not resolve this difference, so neither formulation is silently substituted for the other. It also does not specify a numerical benchmark for "good bounds." The minimum-order interpretation requires confirmation; the wording alone does not explicitly state this optimization target.

Short English statement

Find bounds on the smallest graph whose every three-color edge coloring contains a monochromatic triangle. The background additionally requires the graph to be $K_4$-free, but the displayed source statement omits that restriction. These give different targets, and the intended formulation requires review.

Sources

• Local UnsolvedMath registry, permanent ID $30002030$, source problem code catalogue entry, title "Three-Color Edge-Folkman Numbers for Triangles," in the Oberwolfach Reports Open Problems collection. The supplied proposed year is 2012; no proposer is named.
• Supplied report citation: Mini-Workshop: Hypergraph Turán Problem (2013), Oberwolfach Reports, pp. 1149--1182, DOI 10.4171/owr/2012/19. https://doi.org/10.4171/owr/2012/19. The citation's parenthetical year is 2013, whereas the supplied proposed year and DOI string indicate 2012; this discrepancy is unresolved.
• Supplied literature source, "Oberwolfach report": https://ems.press/content/serial-article-files/46390?nt=1.
• Supplied literature source, "Multicolor Ramsey numbers of 3-graphs": https://link.springer.com/article/10.1007/s40687-024-00463-w.
• Supplied literature source, "Multicolor triple-system Ramsey numbers": https://arxiv.org/abs/1302.5304.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the three-color $K_4$-free edge-Folkman bounds question open and says that multicolor Ramsey results give related bounds without settling this host-restricted problem. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment; its status and cited claims require independent verification.
• The registry labels the problem open and the statement corrected_verified. Its supplied verification note reports a manual semantic, typographic, and LaTeX review of a meaning-preserving cleanup. These are source metadata, not mathematical verification of this draft or resolution of the conflicting host conditions.