Leírás
Vera T. Sós asked in 1991 how many 3-edge-colorings of the
complete graph on n vertices is needed for each triangle to be
3-colored in at least one of them. Jointly with János Körner we
have shown in a 1995 paper that this optimum is (stating it only
vaguely) between the base 2 and base 3 logarithm of n. We had no good
bounds
when the triangle is replaced by a path on four vertices. In
this talk some observations related to variants of this latter
problem will be presented.
In particular, we call an edge-coloring of the complete graph
F-caring if it leaves no F-subgraph monochromatic and at the
same time every subset of |V(F)| vertices contains in it at
least one completely multicolored version of F. For the first
two meaningful cases, when F is a path or a star on four
vertices we determine for infinitely many n the minimum number
of colors needed for an F-caring edge-coloring of the n-vertex
complete graph. We also show an explicit family of about 2logn (base
of the logarithm is 2) 3-edge-colorings of the n-vertex complete graph
so that every
quadruple of its vertices contains a totally multicolored
4-vertex path in at least one of them. Relations to other
Ramsey-type problems and Shannon capacity will also be
discussed.