Exact colorings of graphs

Definitions and mathematical statement

For a positive integer $c$, an exact $c$-coloring of the complete graph on $\mathbb N$ is a surjective function $\varphi:[\mathbb N]^2\to\{1,\ldots,c\}$, where $[X]^2$ denotes the unordered two-element subsets of a set $X$. Exactness concerns the whole infinite graph: every color must occur on at least one edge, but a color need not occur infinitely often.

For positive integers $c,m$, let $P(c,m)$ mean that every exact $c$-coloring admits an infinite subset $W\subseteq\mathbb N$ for which precisely $m$ colors occur among its edges: \[ \left|\{\varphi(e):e\in[W]^2\}\right|=m. \] The proposed classification is \[ P(c,m)\quad\Longleftrightarrow\quad m\in\{1,2,c\}, \qquad 1\le m\le c. \] Repeated entries in this set are harmless for $c=1$ or $2$. The restriction $m\le c$ is explicit, since more colors cannot appear on a subgraph than in the whole graph.

The positive direction requires an infinite vertex set for every admissible coloring, and may use different sets for different values of $m$. The negative direction asks, for each pair $3\le m<c$, for an exact $c$-coloring such that no infinite vertex set realizes exactly $m$ colors. Finite complete subgraphs realizing $m$ colors do not suffice. No density, regularity, or effectiveness restriction is placed on either the coloring or the infinite subset.

Short English statement

Which exact numbers of edge colors must appear on some infinite complete subgraph of every finite exact coloring?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3114 (OPG-37229), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Exact colorings of graphs. Original problem and discussion. http://www.openproblemgarden.org/op/exact_colorings_of_graphs.