Exact colorings of graphs

Importance: Medium ✭✭
Author(s): Erickson, Martin
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Martin Erickson
on: June 29th, 2010

\begin{conjecture} For $c \geq m \geq 1$, let $P(c,m)$ be the statement that given any exact $c$-coloring of the edges of a complete countably infinite graph (that is, a coloring with $c$ colors all of which must be used at least once), there exists an exactly $m$-colored countably infinite complete subgraph. Then $P(c,m)$ is true if and only if $m=1$, $m=2$, or $c=m$. \end{conjecture}

Stacey and Weidl have shown that given $m \geq 3$, there is an integer $C(m)$ such that $P(c,m)$ is false for all $c \geq C(m)$.


* M. Erickson, ``A Conjecture Concerning Ramsey's Theorem,'' \emph{Discrete Mathematics} \textbf{126}, 395--398 (1994); MR \textbf{95b}:05209

A. Stacey and P. Weidl, "The Existence of Exactly m-Coloured Complete Subgraphs," \emph{J. of Combinatorial Theory}, Series B \textbf{75}, 1-18 (1999)

* indicates original appearance(s) of problem.