Planar Ramsey numbers for cycles
type: Item
instance of: scholarly article
title: Planar Ramsey numbers for cycles
zbMATH Open document ID: 1161.05046
author: Izolda Gorgol
author: Andrzej Ruciński
published in: Discrete Mathematics
publication date: 2008-09-04T00:00:00Z
review text: The planar Ramsey number \(\text{PR}(G,H)\) is the least \(n\) such that every \(n\)-vertex planar graph \(F\) contains either \(G\) or its complement contains \(H\). The paper determines all planar Ramsey numbers when \(G\) and \(H\) are cycles. The key idea is that the complement of a planar graph is very dense, and therefore is almost Hamiltonian. For example, Theorem 4 asserts that the complement of every planar graph on \(n\geq 9\) vertices contains \(C_{n-2}\), which implies that \(\text{PR}(C_m,C_n)\leq n+2\) whenever \(n\geq 7\). The matching bound \(\text{PR}(C_m,C_n)\geq n+2\) for \(m\geq 5\) is due the graph \(K_{2,n-1}\).
reviewed by: Boris Bukh
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 5321311
zbMATH Keywords: planar graph
zbMATH Keywords: planar Ramsey numbers
zbMATH Keywords: cycles
zbMATH Keywords: Hamiltonicity
MaRDI profile type: Publication
full work available at URL: j.disc.2007.08.085
OpenAlex ID: W2019664724
cites work: A note on the Ramsey number and the planar Ramsey number for C4 and complete graphs
cites work: The planar Ramsey number for \(C_4\) and \(K_5\) is 13
cites work: Q3852212
cites work: Graphs without four-cycles
cites work: Q4342632
cites work: All Ramsey numbers for cycles in graphs
cites work: Q3997075
cites work: On a Ramsey-type problem of J. A. Bondy and P. Erdős. I
cites work: On a Ramsey-type problem of J. A. Bondy and P. Erdős. II
cites work: Planar Ramsey numbers
cites work: The Analogue of Ramsey Numbers for Planar Graphs
DOI: 10.1016/J.DISC.2007.08.085
Recommended article: Planar Ramsey numbers
Recommended article: Planar Ramsey Numbers
Recommended article: Planar anti-Ramsey numbers of paths and cycles
Recommended article: Planar Ramsey graphs
Recommended article: Ramsey numbers for cycles in graphs
Recommended article: Gallai-Ramsey numbers for cycles
Recommended article: Q3378337
Recommended article: Ramsey Numbers for Nontrivial Berge Cycles
Recommended article: Q4657588
Recommended article: Ramsey numbers of a cycle
description: scientific article; zbMATH DE number 5321311