The minimum degree of Ramsey‐minimal graphs
The minimum degree of Ramsey‐minimal graphs
复制标题
Ramsey 最小图的最小度
DOI：
10.1002/jgt.20199
复制
发表时间：
2007
影响因子：
0.9
通讯作者：
Kathy Lin
中科院分区：
文献类型：
--
作者：
J. Fox;Kathy Lin
我们记为H → G，如果图H的每一条边的2-染色都包含图G的一个单色副本。一个图H是G-极小的，如果H → G，但对H的每个真子图H′，H′ ∈ G。我们定义s（G）为最小值s，使得存在一个顶点度为s的G-极小图。我们证明了s（Kk）=（k − 1）2和s（Ka，B）= 2 min（a，B）− 1。我们还提出了几个相关的开放问题。© 2006 Wiley Periodicals，Inc. J Graph Theory 54：167-177，2007
We write H → G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G‐minimal if H → G, but for every proper subgraph H′ of H, H′ ↛ G. We define s(G) to be the minimum s such that there exists a G‐minimal graph with a vertex of degree s. We prove that s(Kk) = (k − 1)2 and s(Ka,b) = 2 min(a,b) − 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007