
doi: 10.1007/pl00009828
The induced Ramsey number \(r_{\text{ind}}(G,H)\), is the smallest possible order of a graph \(F\) with the property that if the edges of \(F\) are \(2\)-colored, there is an induced subgraph of \(G\) in the first color or \(H\) in the second color. It is shown for any graphs \(G\) and \(H\) with \(k = | G| \leq | H| = t\) and \(q = \chi(H)\), the chromatic number of \(H\), that \(r_{\text{ind}}(G,H) \leq t^{Ck \log q}\) for some constant \(C\). Related results and conjectures are presented; in particular, it is conjectured that there is a constant \(f = f(G)\) such that if \(t = | H| \), then \(r_{\text{ind}}(G,H) \leq t^{f}\). When \(G\) is a tree a polynomial bound, in terms of both \(t\) and \(k\), on \(r_{\text{ind}}(G,H)\) is proved. The proofs use probabilistic techniques and random graphs that are based on projective planes.
Ramsey numbers, Generalized Ramsey theory, induced graphs
Ramsey numbers, Generalized Ramsey theory, induced graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 18 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
