On a problem of El-Zahar and Erdos
On a problem of El-Zahar and Erdos
复制标题
关于扎哈尔和鄂尔多斯问题
DOI：
10.1016/j.jctb.2023.11.004
复制
发表时间：
2024
期刊：
影响因子：
--
通讯作者：
Nguyen T
中科院分区：
文献类型：
--
作者：
Nguyen T
图G的两个子图A，B是反完全的，如果它们是点不相交的，并且没有边连接它们。如果G是一个团数有界且色数足够大的图，那么它是否有两个反完全子图，且都具有大的色数？这是扎哈尔和埃尔德什在1986年提出的一个问题，至今仍未解决。如果是，则至少应该有两个反完全子图都具有大的最小度，这是我们的结果之一。我们证明了两个变种。第一，强化：我们可以要求这两个子图中的一个具有大的色数：即对所有t，c≥ 1，存在d≥ 1使得如果G的色数至少为d，且不包含完全图Kt作为子图，则存在反完全子图A，B，其中A的最小度至少为c，B的色数至少为c.其次，我们看看会发生什么，如果我们取代的假设，G有足够大的色数的假设，G有足够大的最小程度。这，连同排除K t，是不足以保证两个反完全子图都具有大的最小程度;但它的工作，而不是排除K t，我们排除完全二分图K t，t。更确切地说：对任意的t，c≥ 1，存在d≥ 1使得若G的最小度至少为d，且不含完全二部图Kt，t作为子图，则存在两个最小度至少为c的反完全子图.
Two subgraphs A, B of a graph G are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number: that is, for all t, c≥ 1 there exists d≥ 1 such that if G has chromatic number at least d, and does not contain the complete graph K t as a subgraph, then there are anticomplete subgraphs A, B, where A has minimum degree at least c and B has chromatic number at least c. Second, we look at what happens if we replace the hypothesis that G has sufficiently large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding K t, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding K t we exclude the complete bipartite graph K t, t. More exactly: for all t, c≥ 1 there exists d≥ 1 such that if G has minimum degree at least d, and does not contain the complete bipartite graph K t, t as a subgraph, then there are two anticomplete subgraphs both with minimum degree at least c.