On decomposition of graphs
On decomposition of graphs
复制标题
DOI：
10.1007/bf02280296
复制
发表时间：
1967-09
期刊：
影响因子：
--
通讯作者：
P. Erdős;A. Hajnal
中科院分区：
文献类型：
--
作者：
P. Erdős;A. Hajnal
5<基数1~ 1表示分解的类型，称图S。两种情况下分解的元素。我们提到表达式分解通常用于边缘分解，在某些情况下顶点分解称为着色。我们的问题将是以下类型。设~ J是一个图，P是图的一个性质，通常表示w在某种意义上是“小”的。进一步设V为更强的性质，通常表示具有性质P'的图甚至更“小”。当(1)和V是表示< jP不包含完全a图的性质时，我们将详细地研究这些问题。如果(1)和V是表示< jP不包含完全a图的性质，我们将研究这个问题。当所讨论的属性是~不包含矩形或为树时，我们也会得到结果。我们将在不同的部分讨论不同的问题，并对结果做一个简短的总结。我们对边分解问题的了解很少。我们讨论了一些显然不是最终结果的问题，因为我们认为一些开放的问题是基本的。虽然我们的出发点主要是无限图，但几乎所有的问题都与有限图有关，有限图也存在一些有趣的未解决问题。
5< The cardinal number 1~ 1 will be said the type of the decomposition, and the graphs S will be called. the members of the decomposition in both cases. We mention that the expression decomposition is usually used for the edge decompositions, in some cases vertex decompositions are called colourings. Our problems will be of the following type. Let~ J be a graph and P a property of the graph usually expressing that w is" small" in a certain sense. Let further V be a stronger property usually expressing that the graph having property P'is even" smaller". We investigate the problem if then necessarily has vertex-or-edge-decompositions of relatively small types where the members of the decomposition all have property V.We will investigate these problems in details, when (1) and V are properties expressing that< jP does not contain complete a-graphs. We also have results when the properties in question are that~ does not contain rectangles or is a tree. We are going to discuss the different problems in different sections and we give a short summary of the results there. We have very little information on edge-decomposition problems. We discuss some obviously not final results-for them since we think that some of the open problems are fundamental. Though we have been motivated mostly by infinite graphs when starting this paper almost all the problems are relevant for finite graphs, and there remain some interesting unsolved problems for finite graphs too.