Globally sparse vertex-ramsey graphs |
| |
Authors: | Andrzej Kurek Andrzej Ruciski |
| |
Institution: | Andrzej Kurek,Andrzej Ruciński |
| |
Abstract: | For graphs G and F we write F → (G)1r if every r-coloring of the vertices of F results in a monochromatic copy of G. The global density m(F) of F is the maximum ratio of the number of edges to the number of vertices taken over all subgraphs of F. Let We show that The lower bound is achieved by complete graphs, whereas, for all r ≥ 2 and ? > 0, mcr(Sk, r) > r - ? for sufficiently large k, where Sk is the star with k arms. In particular, we prove that ![equation image equation image](/cms/asset/19a8f8a7-c2a2-40ac-a9ce-8a83aac5774a/tex2gif-ueqn-3.gif) |
| |
Keywords: | |
|
|