A New Lower Bound on the Potential-Ramsey Number of Two Graphs

• 作 者: Jin-zhi DU Jian-hua YIN
• 机 构: School of Science,Hainan University,Haikou 570228,China
• 出 处: 应用数学学报（英文版）
• 发表日期: 2021年1期
• 关键词: graphic sequence potential-Ramsey number

A nonincreasing sequence 7r =(d1,…,dn)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 π.Given a graph H,a graphic sequence 7r is potentially H-graphic if π has a realization containing H as a subgraph.For graphs G1 and G2,the potential-Ramsey number rpot(G1,G2)is the smallest integer k such that for every κ-term graphic sequence π,either π is potentially G1-graphic or the complementary sequence π =(k-1-dκ,…,k-1-d1)is potentially G2-graphic.For 0 ≤ k ≤[t/2],denote Kt-k to be the graph obtained from Kt by deleting k independent edges.If k = 0,Busch et al.(Graphs Combin.,30(2014)847-859)present a lower bound on rpot(G,Kt)by using the 1-dependence number of G.In this paper,we utilize i-dependence number of G for i ≥ 1 to give a new lower bound on rpot(G,Ktk)for any k with 0 ≤ k ≤[t/2].Moreover,we also determine the exact values of rpot(Kn,Kt-k)for 1 ≤ κ ≤ 2.