Chromatic Ramsey Theory

✍ Scribed by Norbert Sauer; Robert Woodrow; Vojtech Rödl

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 307 KB
• Volume: 18
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1993.0075

✦ Synopsis

Let ᑡ be a countable graph which has infinite chromatic number . If ␥ is a coloring of [G] 2 with two colors , is there then a subset H ' G such that ␥ is constant on [ H ] 2 and ᑡ 3 H , the graph induced by ᑡ on H , has infinite chromatic number? As edges and non-edges can be colored with dif ferent colors this will be the case if f ᑡ contains an infinite clique . It turns out that if the clique size of ᑡ is unbounded but ᑡ does not contain an infinite clique then for every coloring of [ G ] 2 with τ colors , there are some two of the τ colors such that there is an infinite chromatic subgraph of ᑡ the vertex set of which forms only pairs colored in those two colors ; and this is best possible , because one can always distinguish between edges and non-edges . In the case in which the graphs do not contain the complete graph on n vertices the situation is much more complicated . We will show that for every 3 р n there is a graph ᑡ , which does not embed the complete graph on n vertices , with the property that for every positive number τ there exists a coloring of [ G ] 2 with τ colors such that the vertex set of every infinite chromatic subgraph of ᑡ forms pairs in each of the τ colors . On the other hand there is a graph ᑡ , which does not embed the complete graph on n vertices , and which has the property