圈与K4的临界完全图Ramsey数

对给定的2个图G和H,Ramsey数r(G,H)是最小的正整数r,使得对完全图Kr的边任意红蓝着色或存在红色子图G、或存在蓝色子图H.临界完全图Ramsey数r_K(G,H)是最大的正整数n,使得图K_r-K_n的边任意红蓝着色或存在红色子图G或存在蓝色子图H.当正整数n≥5时,r_K(C_n,K_4)=n/2,C_n为n个点的圈.     

扇形图与匹配图的临界星图Ramsey数

对于完全图Kn和一个额外的顶点v,通过在v与Kn之间添加k条边所得出的图,记为KnK1,k.设G和H是任意的图,临界星图Ramsey数r*(G,H)定义为最小的正整数k,使得图KN-1K1,k的任意红蓝2-边着色,或者存在单色的红色子图G,或者存在单色的蓝色子图H,这里N指的是Ramsey数r(G,H).文中找到了r(Fn,mK2)的所有临界图,利用这些临界图得到了临界星图Ramsey数r*(Fn,mK2)=m+1,nm≥1,以及r*(Fn,mK2)=2 m,n≤m,这里Fn=K1+nK2是扇形图.     

Ramsey数r(mC_3,nC_4)

对于图G和图H ,Ramsey数r(G ,H)定义为最小正整数 p ,使得完全图Kp 用红、蓝两色作任意边着色后 ,总含红色子图G或蓝色子图H。以mG记m个图G的不相交并 ,Ck 记长度为k的圈 ,对于正整数m、n ,n≥m≥ 1 ,本文确定了Ramsey数r(mC3 ,nC4)。     

用图的分割原理计算一些Ramsey数

Ramsey数R(G,H)为最小的正整数N,使得对完全图KN的边集的任意红蓝二着色,都存在红色的子图G或者蓝色的子图H.结合Burr的一个定理和图的分割原理,证明当n≥|G|2+2χ(G)α(G)时,R(Pn,G)=(χ(G)-1)(n-1)+σ(G).     

一些扫帚图的Ramsey数

给定图G,Ramsey数R(G)是最小的正整数N,满足对完全图K_N的边任意红蓝着色,则或者存在红色子图G或者存在蓝色子图G.扫帚图B_(k,m)是将星图K_(1,k)的中心点与路Pm的一个端点黏成一个点得到的树图.由此得到,当k为大于1的正整数时,R(B_(k,2k-1))=4k-2且R(B_(k,4))=2k+3.     

$P_n$和$C_n^k$的Ramsey数

称Fk为图F的k幂次图,如果V(Fk)=V(F),且Fk中的任意两个顶点相邻当且仅当在F中的距离至多为k.给定图G和H,Ramsey数R(G,H)为最小的正整数N,使得完全图KN的任意红蓝-边着色都会含有一个红色的子图G或者蓝色的子图H.证明了渐近阶R(Pn,Ckn)=(n-1)(χ(Ckn)-1)+σ(Ckn)+o(n),其中k是常数.     

双星图的Ramsey数的上界

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,则或者存在红色子图G,或者存在蓝色子图H.双星B(m,n)为直径是3,有两个中心顶点,其顶点度分别为m+1和n+1的树.得到,当nm时,R(B(m,n))2n+m+2;当n=m或n=m+1时,R(B(m,n))=2 m+n+2.     

书图和扇形图的Ramsey数

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,或者存在红色子图G,或者存在蓝色子图H.用G+H表示两个不交的图G和H之间完全连边所得到的图.设Bm=K2+mK1,Fn=K1+nK2.证明了当m≥1且n≥max{2,3 m-2},R(Bm,Fn)=4n+1;当n≥38,R(F2,K2,n)=2n+3.     

r(Km,n)的一个构造型下界

图G的Ramsey数r(G)是指最小的自然数N,满足当n≥N,对完全图Kn的边进行红蓝二着色时总包含单色的图G.对于完全二部图Km,n,给出了当n充分大时,r(Km,n)≥2m(n-n0.525)的一个代数构造的证明.     

边Ramsey上界研究

对于无向有限简单图G和H,边Ramsey数R(C,H)是指最小的整数e,使得对一个有e条边的图的边用红蓝两色进行2-染色后要么得到一个红色的G,要么得到一个蓝色的H.通过分支定界法,得到一些边Ramsey数的上界.     

七圈对低阶轮的Ramsey数

给定两个图F和H,Ramsey数R（E,H）是指具有如下性质的最小正整数N：对任意的N阶图G,或者F是G的子图,或者H是G的补图的子图．令Gm表示m阶圈,Wn表示n＋1阶轮．本文证明了当8≤n≤10时,R（C7,Wn）=2n＋1．     

一个实用的检验Kn(3,p)的算法

设Ｋｎ是ｎ个顶点的完全图，若对Ｋｎ的每条边着以红色或蓝色，并且图中既不包含红色团Ｋ３也不包含蓝色团Ｋｐ，这样就得到一个二色边图Ｋｎ，同时将这种染色所得的图记为Ｋｎ（３，ｐ），把使Ｋｎ（３，ｐ）成立的最大值记为Ｒ（３，ｐ），Ｒ（３，ｐ）＝ｒ（３，ｐ）－１，ｒ（３，ｐ）是Ｒａｍｓｅｙ数，本给出一个实用的算法，可以对给定连通图检验Ｋｎ（３，ｐ）是否成立 。     

图多彩染色中的2度点删除问题

对整数r0,图G的一个r-多彩染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得:(C1)相邻点获得的颜色不同;(C2)︱c(N(v))︱≥min{N(v),r}(其中N(v)代表v的邻点集)。使图G有一个正常的(k,r)-染色的最小k值称为G的多彩色数χ_r(G)。本文主要研究在图G中删掉任意一个2度点后多彩色数的变化。     

一个关于三角形和K_2+T_n的Ramsey goodness结论(英文)

研究三角形和K2＋Tn的Ramseygoodness性质．在已证明的r（K3,K2＋T4）=11基础上利用数学归纳法得出：当n≥4时,有r（K3,K2＋Tn）=2n＋3．从一个图G中删除两个点,由剩余的点导出的子图记为G’,李雨生先生得出一个关于r（G,H）的结论．作为它的推论,给出了对于“书”（Bm）和K3＋L的Ramsey数的一个上界．