Czechoslovak Mathematical Journal, Vol. 72, No. 2, pp. 513-522, 2022
The potential-Ramsey number of $K_n$ and $K_t^{-k}$
Jin-Zhi Du, Jian-Hua Yin
Received January 19, 2021. Published online March 1, 2022.
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\ge2$ 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\ge3$, $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).
Keywords: graphic sequence; potentially $H$-graphic sequence; potential-Ramsey number
References: [1] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. American Elsevier, New York (1976). MR 0411988 | Zbl 1226.05083
[2] A. Busch, M. J. Ferrara, S. G. Hartke, M. S. Jacobson: A degree sequence variant of graph Ramsey numbers. Graphs Comb. 30 (2014), 847-859. DOI 10.1007/s00373-013-1307-y | MR 3223948 | Zbl 1298.05078
[3] A. Busch, M. J. Ferrara, S. G. Hartke, M. S. Jacobson, H. Kaul, D. B. West: Packing of graphic $n$-tuples. J. Graph Theory 70 (2012), 29-39. DOI 10.1002/jgt.20598 | MR 2916065 | Zbl 1243.05191
[4] J. Du, J. Yin: A further result on the potential-Ramsey number of $G_1$ and $G_2$. Filomat 36 (2019), 1605-1617. DOI 10.2298/FIL1906605D | MR 4034026
[5] J.-Z. Du, J.-H. Yin: A new lower bound on the potential-Ramsey number of two graphs. Acta Math. Appl. Sin., Engl. Ser. 37 (2021), 176-182. DOI 10.1007/s10255-021-0999-7 | MR 4196622 | Zbl 1464.05043
[6] Z. Dvořák, B. Mohar: Chromatic number and complete graph substructures for degree sequences. Combinatorica 33 (2013), 513-529. DOI 10.1007/s00493-013-2649-z | MR 3132924 | Zbl 1313.05117
[7] P. Erdős, T. Gallai: Graphs with prescribed degrees of vertices. Mat. Lapok 11 (1960), 264-274. (In Hungarian.) Zbl 0103.39701
[8] P. Erdős, M. S. Jacobson, J. Lehel: 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 1170797 | Zbl 0840.05093
[9] M. J. Ferrara, T. D. Lesaulnier, C. K. Moffatt, P. S. Wenger: On the sum necessary to ensure a degree sequence is potentially $H$-graphic. Combinatorica 36 (2016), 687-702. DOI 10.1007/s00493-015-2986-1 | MR 3597587 | Zbl 1399.05038
[10] M. J. Ferrara, J. Schmitt: A general lower bound for potentially $H$-graphic sequences. SIAM J. Discrete Math. 23 (2009), 517-526. DOI 10.1137/080715275 | MR 2476846 | Zbl 1215.05036
[11] R. J. Gould, M. S. Jacobson, J. Lehel: Potentially $G$-graphical degree sequences. Combinatorics, Graph Theory and Algorithms. Vol. I. New Issues Press, Kalamazoo (1999), 451-460. MR 1985076
[12] S. L. Hakimi: 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 10.1137/0110037 | MR 0148049 | Zbl 0109.16501
[13] V. Havel: A remark on the existence of finite graphs. Čas. Pěstování Mat. 80 (1955), 477-480. (In Czech.) DOI 10.21136/CPM.1955.108220 | MR 0089165 | Zbl 0068.37202
[14] A. R. Rao: 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 0553948 | Zbl 0483.05038
[15] N. Robertson, Z.-X. Song: Hadwiger number and chromatic number for near regular degree sequences. J. Graph Theory 64 (2010), 175-183. DOI 10.1002/jgt.20447 | MR 2674490 | Zbl 1209.05098
[16] J. Yin, J. Li: A variation of a conjecture due to Erdős and Sós. Acta Math. Sin., Engl. Ser. 25 (2009), 795-802. DOI 10.1007/s10114-009-7260-2 | MR 2505310 | Zbl 1229.05161
[17] J.-H. Yin, J.-S. Li: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math. 301 (2005), 218-227. DOI 10.1016/j.disc.2005.03.028 | MR 2171314 | Zbl 1119.05025
[18] J.-H. Yin, L. Meng, M.-X. Yin: Graphic sequences and split graphs. Acta Math. Appl. Sin., Engl. Ser. 32 (2016), 1005-1014. DOI 10.1007/s10255-016-0622-5 | MR 3552867 | Zbl 1410.05027
Affiliations: Jin-Zhi Du, Jian-Hua Yin (corresponding author), School of Science, Hainan University, Renmin Rd, Meilan Qu, Haikou 570228, P. R. China, e-mail: yinjh@hainanu.edu.cn
