Home » Subject » Graph Theory

Exact colorings of graphs

Importance: Medium ✭✭
Author(s): Erickson, Martin
Subject: Graph Theory
Keywords: graph coloring
ramsey theory
Recomm. for undergrads: no
Posted by: Martin Erickson
on: June 29th, 2010
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) $.

Bibliography

* 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.
add new comment