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

Du, Jin-Zhi, and Yin, Jian Hua. "The potential-Ramsey number of $K_n$ and $K_t^{-k}$." Czechoslovak Mathematical Journal 72.2 (2022): 513-522. <http://eudml.org/doc/298308>.

@article{Du2022,
abstract = {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).},
author = {Du, Jin-Zhi, Yin, Jian Hua},
journal = {Czechoslovak Mathematical Journal},
keywords = {graphic sequence; potentially $H$-graphic sequence; potential-Ramsey number},
language = {eng},
number = {2},
pages = {513-522},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The potential-Ramsey number of $K_n$ and $K_t^\{-k\}$},
url = {http://eudml.org/doc/298308},
volume = {72},
year = {2022},
}

TY - JOUR
AU - Du, Jin-Zhi
AU - Yin, Jian Hua
TI - The potential-Ramsey number of $K_n$ and $K_t^{-k}$
JO - Czechoslovak Mathematical Journal
PY - 2022
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 72
IS - 2
SP - 513
EP - 522
AB - 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).
LA - eng
KW - graphic sequence; potentially $H$-graphic sequence; potential-Ramsey number
UR - http://eudml.org/doc/298308
ER -