Ramsey linear families and generalized subdivided graphs |
| |
Authors: | Yusheng Li, Cecil C. Rousseau,ubomí r olt s |
| |
Affiliation: | a Department of Mathematical Sciences, Campus Box 526429, The University of Memphis, Memphis, TN 38152-6429, USA b Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310, USA |
| |
Abstract: | The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V1, V2,…, Va such that for each i at most d vertices in V1 … Vi have neighbors in Vi+1 and r(Kk, Vi) p | V(G) |, where Vi denotes the subgraph of G induced by Vi. Then there exists a number c depending only on p, d, and k such that r(Kk, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of G−I has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|