Geodesic
The potential-Ramsey number of $K_n$ and $K_t^{-k}$
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 513-522
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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).
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).
DOI : 10.21136/CMJ.2022.0017-21
Classification : 05C07, 05C35
Keywords: graphic sequence; potentially $H$-graphic sequence; potential-Ramsey number 
@article{10_21136_CMJ_2022_0017_21,
     author = {Du, Jin-Zhi and Yin, Jian-Hua},
     title = {The {potential-Ramsey} number of $K_n$ and $K_t^{-k}$},
     journal = {Czechoslovak Mathematical Journal},
     pages = {513--522},
     year = {2022},
     volume = {72},
     number = {2},
     doi = {10.21136/CMJ.2022.0017-21},
     mrnumber = {4412772},
     zbl = {07547217},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0017-21/}
}
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
SP  - 513
EP  - 522
VL  - 72
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0017-21/
DO  - 10.21136/CMJ.2022.0017-21
LA  - en
ID  - 10_21136_CMJ_2022_0017_21
ER  - 
%0 Journal Article
%A Du, Jin-Zhi
%A Yin, Jian-Hua
%T The potential-Ramsey number of $K_n$ and $K_t^{-k}$
%J Czechoslovak Mathematical Journal
%D 2022
%P 513-522
%V 72
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0017-21/
%R 10.21136/CMJ.2022.0017-21
%G en
%F 10_21136_CMJ_2022_0017_21
Du, Jin-Zhi; Yin, Jian-Hua. The potential-Ramsey number of $K_n$ and $K_t^{-k}$. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 513-522. doi: 10.21136/CMJ.2022.0017-21

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. American Elsevier, New York (1976). | MR | JFM

[2] Busch, A., Ferrara, M. J., Hartke, S. G., Jacobson, M. S.: A degree sequence variant of graph Ramsey numbers. Graphs Comb. 30 (2014), 847-859. | DOI | MR | JFM

[3] Busch, A., Ferrara, M. J., Hartke, S. G., Jacobson, M. S., Kaul, H., West, D. B.: Packing of graphic $n$-tuples. J. Graph Theory 70 (2012), 29-39. | DOI | MR | JFM

[4] Du, J., Yin, J.: A further result on the potential-Ramsey number of $G_1$ and $G_2$. Filomat 36 (2019), 1605-1617. | DOI | MR

[5] Du, J.-Z., Yin, J.-H.: A new lower bound on the potential-Ramsey number of two graphs. Acta Math. Appl. Sin., Engl. Ser. 37 (2021), 176-182. | DOI | MR | JFM

[6] Dvořák, Z., Mohar, B.: Chromatic number and complete graph substructures for degree sequences. Combinatorica 33 (2013), 513-529. | DOI | MR | JFM

[7] Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok 11 (1960), 264-274 Hungarian. | MR | JFM

[8] Erdős, P., Jacobson, M. S., Lehel, J.: Graphs realizing the same degree sequences and their respective clique numbers. Graph Theory, Combinatorics and Applications. Vol. 1 John Wiley & Sons, New York (1991), 439-449. | MR | JFM

[9] Ferrara, M. J., Lesaulnier, T. D., Moffatt, C. K., Wenger, P. S.: On the sum necessary to ensure a degree sequence is potentially $H$-graphic. Combinatorica 36 (2016), 687-702. | DOI | MR | JFM

[10] Ferrara, M. J., Schmitt, J.: A general lower bound for potentially $H$-graphic sequences. SIAM J. Discrete Math. 23 (2009), 517-526. | DOI | MR | JFM

[11] Gould, R. J., Jacobson, M. S., Lehel, J.: Potentially $G$-graphical degree sequences. Combinatorics, Graph Theory and Algorithms. Vol. I New Issues Press, Kalamazoo (1999), 451-460. | MR

[12] Hakimi, S. L.: On realizability of a set of integers as degrees of vertices of a linear graph. I. J. Soc. Ind. Appl. Math. 10 (1962), 496-506. | DOI | MR | JFM

[13] Havel, V.: A remark on the existence of finite graphs. Čas. Pěstován{'ı Mat. 80 (1955), 477-480 Czech. | DOI | MR | JFM

[14] Rao, A. R.: The clique number of a graph with a given degree sequence. Proceedings of the Symposium on Graph Theory ISI Lecture Notes 4. Macmillan, New Delhi (1979), 251-267. | MR | JFM

[15] Robertson, N., Song, Z.-X.: Hadwiger number and chromatic number for near regular degree sequences. J. Graph Theory 64 (2010), 175-183. | DOI | MR | JFM

[16] Yin, J., Li, J.: A variation of a conjecture due to Erdős and Sós. Acta Math. Sin., Engl. Ser. 25 (2009), 795-802. | DOI | MR | JFM

[17] Yin, J.-H., Li, J.-S.: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math. 301 (2005), 218-227. | DOI | MR | JFM

[18] Yin, J.-H., Meng, L., Yin, M.-X.: Graphic sequences and split graphs. Acta Math. Appl. Sin., Engl. Ser. 32 (2016), 1005-1014. | DOI | MR | JFM

Cité par Sources :