Graphs of exact colorings

Importance: Medium ✭✭
Subject: Algebra
Recomm. for undergrads: no
Posted by: sabisood
on: October 3rd, 2013

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  $.

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,'' Discrete Mathematics 126, 395--398 (1994); MR 95b:05209

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

* indicates original appearance(s) of problem.


* indicates original appearance(s) of problem.