Home » Subject » Algebra

Graphs of exact colorings

Importance: Medium ✭✭
Author(s):
Subject: Algebra
Keywords:
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.

Bibliography



* indicates original appearance(s) of problem.
add new comment