Colorings Without Disjoint Color-Isomorphic Triangles

Definitions and mathematical statement

For each positive integer $n$, let $K_n$ be the complete simple graph on vertex set $[n]=\{1,\ldots,n\}$. An edge-coloring with at most $q$ colors is a map $\chi:E(K_n)\to[q]$, where $q$ is a nonnegative integer and $[0]=\varnothing$. No properness condition is imposed. Two triangles on disjoint three-element vertex sets $A,B\subseteq[n]$ are color-isomorphic if there is a bijection $f:A\to B$ such that \[ \chi(\{u,v\})=\chi(\{f(u),f(v)\}) \qquad\text{for every }\{u,v\}\in\binom{A}{2}. \] Thus the bijection preserves the actual color labels. Define \[ g(n)=\min\left\{q\in{\mathbb{Z}}_{\geq0}:\text{there exists an edge-coloring }\chi:E(K_n)\to[q] \text{ with no two vertex-disjoint color-isomorphic triangles}\right\}. \] The convention allowing $q=0$ handles the edgeless graph $K_1$. For $n<6$, the forbidden configuration cannot occur. The source does not explicitly specify these small-order conventions or define color-isomorphism; the definitions above make the usual color-preserving interpretation explicit.

Problem (David Conlon, Question 14). Determine the asymptotic order of $g(n)$ as $n\to\infty$. In particular, is \[ g(n)=\Theta(n), \] meaning that there exist constants $a,b>0$ and an integer $N\geq1$ such that $an\leq g(n)\leq bn$ for every integer $n\geq N$? More strongly, is \[ g(n)=n-O(1), \] meaning that there exist a constant $C\geq0$ and an integer $N\geq1$ such that $|g(n)-n|\leq C$ for every integer $n\geq N$?

Supplied context and qualifications. The supplied dated assessment describes bounds between order $\sqrt n$ and $n-4$. The original excerpt contains a displaced square-root symbol and a corrupted lower-bound display, so that display is not reliable as transcribed. The excerpt additionally attributes to Conlon, Fox and Pham an improvement of the form \[ g(n)\geq c n^{1/2+\varepsilon} \] for some constants $c>0$ and $\varepsilon>0$. These bounds are recorded as supplied contextual claims, with no independently verified range of validity; in particular, the displayed upper bound $n-4$ cannot apply to all positive integers $n$. The source labels the problem open and describes both linear growth and the stronger bounded-distance assertion as unproved. These are supplied status assessments, not independent verification.

Short English statement

Color the edges of a complete graph so that no two triangles with disjoint vertex sets have exactly matching edge colors under a bijection of their vertices. How many colors are necessary as the number of vertices grows? The supplied question asks whether this minimum grows linearly, and even whether it stays within a constant of the number of vertices. The source reports the problem as open; its contextual bounds and status require review.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $30006563$, source problem code catalogue entry, title Colorings Without Disjoint Color-Isomorphic Triangles; collection: Oberwolfach Reports Open Problems. The original excerpt attributes the question to David Conlon as Question 14, although the structured proposer field is empty.
• Supplied report citation: Combinatorics (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/1, pp. 5--79. https://doi.org/10.4171/owr/2026/1. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: Oberwolfach Report 1/2026, https://doi.org/10.4171/owr/2026/1. Literature checked at: 2026-08-22. This is supplied dated curation, not independently verified. Its assessment reports square-root-order to $n-4$ bounds and states that linear growth and $n-O(1)$ behavior remain unproved; the original excerpt also attributes a stronger lower bound to Conlon, Fox and Pham without a separate bibliographic reference.
• The registry labels the statement corrected_verified and says that the official report was checked, the question isolated from surrounding exposition, and its notation repaired. These are supplied verification claims; no source was visited or independently checked in preparing this draft.