On Ramsey minimal graphs
On Ramsey minimal graphs
复制标题
关于拉姆齐最小图
DOI：
10.1016/j.disc.2003.11.043
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
E. Sidorowicz
中科院分区：
文献类型：
--
作者：
M. Borowiecki;Mariusz Haluszczak;E. Sidorowicz
对于图G，F和H，我们写G→（F，H）表示如果G的边用两种颜色着色，比如红色和蓝色，则红色子图包含F的副本，或者蓝色子图包含H的副本。如果对任意真子图G′ ∈ G，G →（F，H）但G′ ∈（F，H），则图G是（F，H）-极小的（Ramsey-极小的）.所有（F，H）-极小图的类记为R（F，H）.本文给出了两个等价定理，它们刻画了当m ≠ 3时属于R（K1，2，K1，m）的图.
For graphs G, F and H we write G→(F,H) to mean that if the edges of G are coloured with two colours, say red and blue, then the red subgraph contains a copy of F or the blue subgraph contains a copy of H. The graph G is (F,H)-minimal (Ramsey-minimal) if G→(F,H) but G′↛(F,H) for any proper subgraph G′⊆G. The class of all (F,H)-minimal graphs will be denoted by R (F,H) . In this paper we will give two equivalent theorems which characterize the graphs belonging to R (K1,2,K1,m) for m⩾3.