Title of article :
Generalizations of some Ramsey-type theorems for matchings
Author/Authors :
Arie Bialostocki، نويسنده , , William Voxman، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2001
Abstract :
For a graph G let RM(G) be the smallest integer R, if it exists, such that every coloring of the edges of KR by an arbitrary number of colors implies a subgraph of KR isomorphic to G that is either monochromatic or has the property that no two of its edges have the same color. We generalize the theorem r(nK2,n−1)=n2−n+2, where r(nK2,n−1) is the Ramsey number for n matchings in an (n−1)-coloring of the complete graph. Namely, we prove that RM(nK2)=r(nK2,n−1)=n2−n+2. In addition, we generalize the theorem r(nK2,2)=3n−1 by considering colorings with three and five colors. Several further possible generalizations for hypermatchings in hypergraphs are suggested.
Keywords :
Matchings , Generalized Ramsey numbers , Hypermatchings , Kneser graph , Fractional Ramsey numbers
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics