Ramsey properties of maximal (outer)planar graphs
Abstract
We study a natural extension of Ramsey theory relative to the classes of maximally planar and maximally outerplanar graphs. This can be seen as a continuation of the study of `Planar Ramsey theory', introduced by Axenovich et al. The question we ask is the following: For a fixed family π¦ of graphs and a pair of graphs {H,F}, does there exist an integer rπ¦ (H, F) such that for every graph G β π¦ with |G| β₯ rπ¦(H, F), every red/blue edge-colouring of G admits a red copy of H or a blue copy of F? When such an integer exists, we say {H,F} is unavoidable in π¦,, and otherwise {H,F} is avoidable in π¦. Our work focuses on this problem where π¦ = π¦MOP and π¦ = π¦MP, which denote the families of maximal outerplanar (MOP) graphs and maximal planar (MP) graphs, respectively. This framework generalises the classical Ramsey problem relative to these classes, as the case with π¦ = {Kn : n β₯ 2} corresponds to classical Ramsey. We also study the corresponding Ramsey numbers for MOP and MP, which we denote as rMOP(H, F) and rMP(H, F). In the case when π¦ = π¦MOP, we completely determine all unavoidable pairs {H, F} with |E(F)| β₯ 2, together with upper bounds and sometimes exact values of rMOP(H, F). When π¦ = π¦MP, we completely determine all unavoidable pairs in the diagonal case {H, H} when H is connected, showing that H must be one of the graphs P3, P4, P5, K1, 3 or the fork graph S2,1,1. This work opens up further possibilities in the study of Ramsey theory relative to a class, and we offer several open problems in this vein.
Related
BibTeX
@misc{baldacchino2026ramsey,
title = {{Ramsey properties of maximal (outer)planar graphs}},
author = {Adriana Baldacchino and Yair Caro and Xandru Mifsud},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05268},
eprint = {2609.05268},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05268},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Ramsey properties of maximal (outer)planar graphs
AU - Adriana Baldacchino
AU - Yair Caro
AU - Xandru Mifsud
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05268
UR - https://arxiv.org/abs/2609.05268
AB - We study a natural extension of Ramsey theory relative to the classes of maximally planar and maximally outerplanar graphs. This can be seen as a continuation of the study of `Planar Ramsey theory', introduced by Axenovich et al. The question we ask is the following: For a fixed family π¦ of graphs and a pair of graphs {H,F}, does there exist an integer r_π¦ (H, F) such that for every graph G β π¦ with |G| β₯ r_π¦(H, F), every red/blue edge-colouring of G admits a red copy of H or a blue copy of F? When such an integer exists, we say {H,F} is unavoidable in π¦,, and otherwise {H,F} is avoidable in π¦. Our work focuses on this problem where π¦ = π¦_MOP and π¦ = π¦_MP, which denote the families of maximal outerplanar (MOP) graphs and maximal planar (MP) graphs, respectively. This framework generalises the classical Ramsey problem relative to these classes, as the case with π¦ = {K_n : n β₯ 2} corresponds to classical Ramsey. We also study the corresponding Ramsey numbers for MOP and MP, which we denote as r_MOP(H, F) and r_MP(H, F). In the case when π¦ = π¦_MOP, we completely determine all unavoidable pairs {H, F} with |E(F)| β₯ 2, together with upper bounds and sometimes exact values of r_MOP(H, F). When π¦ = π¦_MP, we completely determine all unavoidable pairs in the diagonal case {H, H} when H is connected, showing that H must be one of the graphs P_3, P_4, P_5, K_1, 3 or the fork graph S_2,1,1. This work opens up further possibilities in the study of Ramsey theory relative to a class, and we offer several open problems in this vein.
ER -