×

Subdivided graphs have linear Ramsey numbers. (English) Zbl 0811.05046

If \(G_ n\) is a graph of order \(n\) such that no two vertices of degree at least 3 are adjacent, then the Ramsey number \(r(G_ n) \leq 12n\). Thus, if each edge of an arbitrary graph \(H\) is subdivided, then the Ramsey number \(r(H)\) is linear in the number of vertices of the subdivided graph. This answers a question raised by Burr and Erdős.

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and , On the magnitude of generalized Ramsey numbers. Colloquia Mathematica Societatis János Bolyai, 10, Infinite and Finite Sets, Vol. 1, North Holland, Amsterdam (1973) 215–240.
[2] Chen, J. Combinat. Theory Ser. B 57 pp 138– (1993)
[3] Chvátal, J. Combinat. Theory Ser. B 34 pp 239– (1983)
[4] Erdös, Discrete Math. 67 pp 227– (1987)
[5] and , An upper bound for the Ramsey numbers r(K3, G). To appear.
[6] Sidorenko, G. J. Graph Theory 15 pp 15– (1991)
[7] Sidorenko, J. Combinat. Theory Ser. B.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.