Metraipolis › archive › dc_4acce6fba67d

Ramsey properties of maximal (outer)planar graphs — arXiv:2609.05268

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.05268
License (as archived): CC0-1.0
Archived: 2026-10-16T23:21:16.407Z
SHA-256 of the archived text: a061326a9c17a390963fab93a123c1fb6b5a326b65ae27e3cf28504c1f0930e4
Stable URL of this page: https://metraipolis.com/documento/dc_4acce6fba67d

How to cite

Ramsey properties of maximal (outer)planar graphs — arXiv:2609.05268 — arXiv (en), https://arxiv.org/abs/2609.05268 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4acce6fba67d (Metraipolis archive dc_4acce6fba67d, sha256 a061326a9c17a390963fab93a123c1fb6b5a326b65ae27e3cf28504c1f0930e4)

BibTeX

@misc{dc4acce6fba67d,
  title = {Ramsey properties of maximal (outer)planar graphs — arXiv:2609.05268},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.05268},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4acce6fba67d; sha256 a061326a9c17a390963fab93a123c1fb6b5a326b65ae27e3cf28504c1f0930e4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05268. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathcal{K}$ of graphs and a pair of graphs $\{H,F\}$, does there exist an integer $r_{\mathcal{K}} (H, F)$ such that for every graph $G \in \mathcal{K}$ with $|G| \geq r_{\mathcal{K}}(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 $\mathcal{K}$,, and otherwise $\{H,F\}$ is avoidable in $\mathcal{K}$. Our work focuses on this problem where $\mathcal{K} = \mathcal{K}_{\mathrm{MOP}}$ and $\mathcal{K} = \mathcal{K}_{\mathrm{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 $\mathcal{K} = \{K_n \colon n \geq 2\}$ corresponds to classical Ramsey. We also study the corresponding Ramsey numbers for MOP and MP, which we denote as $r_{\mathrm{MOP}}(H, F)$ and $r_{\mathrm{MP}}(H, F)$. In the case when $\mathcal{K} = \mathcal{K}_{\mathrm{MOP}}$, we completely determine all unavoidable pairs $\{H, F\}$ with $|E(F)| \geq 2$, together with upper bounds and sometimes exact values of $r_{\mathrm{MOP}}(H, F)$. When $\mathcal{K} = \mathcal{K}_{\mathrm{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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-07 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.05268 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T23:03:13.266Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).