The potential-Ramsey number of $K_n$ and $K_t^{-k}$

Du, Jin-Zhi ; Yin, Jian-Hua

Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 513-522

Abstract (VO)

A nonincreasing sequence $\pi =(d_1,\ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. In this case, $G$ is referred to as a realization of $\pi $. Given two graphs $G_1$ and $G_2$, A. Busch et al. (2014) introduced the potential-Ramsey number of $G_1$ and $G_2$, denoted by $r_{\rm pot}(G_1,G_2)$, as the smallest nonnegative integer $m$ such that for every $m$-term graphic sequence $\pi $, there is a realization $G$ of $\pi $ with $G_1\subseteq G$ or with $G_2\subseteq \bar {G}$, where $\bar {G}$ is the complement of $G$. For $t\ge 2$ and $0\le k\le \lfloor \frac {t}{2}\rfloor $, let $K_t^{-k}$ be the graph obtained from $K_t$ by deleting $k$ independent edges. We determine $r_{\rm pot}(K_n,K_t^{-k})$ for $t\ge 3$, $1\le k\le \lfloor \frac {t}{2}\rfloor $ and $n\ge \lceil \sqrt {2k}\rceil +2$, which gives the complete solution to a result in J. Z. Du, J. H. Yin (2021).

Détail

DOI : 10.21136/CMJ.2022.0017-21

Classification : 05C07, 05C35
Keywords: graphic sequence; potentially $H$-graphic sequence; potential-Ramsey number