Ramseyan properties and conjectures of Graffiti

This paper concerns new variations of Ramsey Theory, and some related conjectures of Graffiti. We show that every k-chromatic graph with more than {dollar}k(r - 1)(b - 1){dollar} vertices has either a b-element independent set such that if any two vertices of the set are joined by an edge then the chromatic number stays the same or an r-element independent set of vertices such that if any two of them are joined by an edge then the chromatic number increases. We put R(3, r) to be the classical finite Ramsey number. In January 1996, Paul Erdos, Siemion Fajtlowicz and I conjectured that every triangle-free graph on more than (b {dollar}-{dollar} 1)(R(3, r) {dollar}-{dollar} 1) vertices has either a b-element independent set of vertices such that if any two of them are joined by an edge then the resulting graph is triangle-free or an r-element independent set such that if any two of them are joined by an edge a triangle is created. I have shown that for r {dollar}le{dollar} 4 our conjecture is correct. Conjectures of Graffiti, which relate such independent sets to projective planes, polar-matching and counter-independent sets are presented.; Another variation of Ramsey Theory is defined as follows. Let k be a positive integer, we define {dollar}Rsb{lcub}k{rcub}(r, b){dollar} as the smallest n such that every connected n-vertex graph G contains an r-vertex induced subgraph of diameter k or a b-element independent set such that any two vertices of the set are at distance more than k. A lower bound is given for the order of a largest independent set such that any two vertices of the set are at distance more than k. Using a result of Siemion Fajtlowicz, we give an upper bound on the numbers {dollar}Rsb{lcub}k{rcub}(r, b),{dollar} for {dollar}k ge{dollar} 2.