Generalized ramsey theory for graphs, I. Diagonal numbers
Generalized ramsey theory for graphs, I. Diagonal numbers
复制标题
DOI：
10.1007/bf02018466
复制
发表时间：
1973-03
影响因子：
0.8
通讯作者：
V. Chvátal;F. Harary
中科院分区：
文献类型：
--
作者：
V. Chvátal;F. Harary
我们使用[12]的符号和术语。图论中传统研究的拉姆齐数r （m, n）可以定义为最小值p，使得每个有p个点的不包含完整图Km的图必须有n个独立的点。或者，它是最小的p，其中Kp的每条线都有两种颜色，绿色和红色，包含绿色的Km或红色的K n。因此，对角线ram。~ ey数r （n, r~）可以用Kp的2色tt~ e线来描述，并且把K~看作一个不考虑颜色的禁止单色子图。这种观点提出了更一般的情况，其中任意图G的线是c色的，并且计算了禁止子图F（或禁止图族）的单色出现次数。图论中的许多问题领域都可以归入这样一个公式。这包括3点路径被禁止的线，色线。G的树性包括禁止M1个循环。图的厚度限制了库拉托夫斯基图。对于G和F可以取完全二部图，对于立方Qn和Qm也可以取完全二部图。长期以来，图论学界一直有一种观点认为极值图论与拉姆齐数之间存在着密切的关系。从另一个定理推导出TIJ~ AN定理或RA~ sEY定理似乎是不可能的。然而，极值二部图论实际上蕴涵了拉姆齐定理的二部形式。定理1揭示了这些含义背后的奥秘。将ERD6S用于寻找对角拉姆齐数r （n, n）下界的组合技术推广到任意图和禁止子图的广义拉姆齐数。
We use the notation and terminology of [12]. The ramsey number r (m, n) as traditionally studied in graph theory may be defined as the minimum number p such that every graph with p points which does not contain the complete graph Km must have n independent points. Alternatively, it is the smallest p for which every coloring of the lines of Kp with two colors, green and red, contains either a green Km or a red K n. ThuS the diagonal ram.~ ey numbers r (n, r~) can be described in terms of 2-coloring tt~ e lines: of Kp and regarding K~ as a forbidden monochromatic subgraph without regard to color. This viewpoint suggests the more general situation in which an arbitrary graph G has a c-coloring of its lines and the number of monochromatic occurrences of a forbidden subgraph F (or of a forbidden family of graphs) is Calculated. A host of problem areas within graph theory can be subsumed under such a formulation. These include the line, chromatic num}) erl ifi which the 3-point path is forbidden. The arboricity of G involves forbidding M1 cycles. The thickness of a graph forbids the Kuratowski graphs. Complete bipartite graphs can be taken for both G and F, and so can cubes Qn and Qm. There has long been a sentiment in graph theory that there is an intimate relationship between extremal graph theory and ramsey numbers. It does not appear possible to derive either TIJ~ AN's Theorem or: RA~ sEY's Theorem from the other. However, extremal bipartite graph theory does in fact imply the bipartite form of RAMSEY'S Theorem. The mystery behind these implications is revealed by Theorem 1. A combinatorial technique used by ERD6S to find a lower bound for diagonal ramsey numbers r (n, n) is extended to generalized ramsey numbers for arbitrary graphs and forbidden subgraphs.