Generalizing the Ramsey problem through diameter (Q1856336)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalizing the Ramsey problem through diameter |
scientific article |
Statements
Generalizing the Ramsey problem through diameter (English)
0 references
13 May 2003
0 references
Let \(G\) be a graph and \(d,k\) be positive integers. Then \(f_d^k(G)\) is defined as the maximum \(t\) with the property that every \(k\)-colouring of \(E(G)\) yields a monochromatic subgraph with at least \(t\) vertices and diameter at most \(d\). The invariant \(f_d^k(G)\) provides a generalization of the classical Ramsey number. The lower and upper bounds for \(f_d^k(K_{a,b})\), that differ by one, are obtained. Moreover, the value of \(f_d^3(K_n)\) for \(d\geq 4\) and the lower bound of \(f_3^k(K_n)\) for \(k\geq 2\) are presented. It is shown that the last result is almost sharp.
0 references
generalised Ramsey number
0 references
diameter
0 references
biaprtite graph
0 references
complete graph
0 references