Multiplicities of subgraphs
Multiplicities of subgraphs
复制标题
DOI：
10.1007/bf01300130
复制
发表时间：
1996-01-01
期刊：
影响因子：
1.1
通讯作者：
Thomason, A
中科院分区：
文献类型：
--
作者：
Jagger, C;Stovicek, P;Thomason, A
Burr和罗斯塔[1]的一个猜想推广了Erdos [2]的一个猜想，即在一个大的完全图的边的任何两种着色中，与固定图G同构的单色子图的比例至少是随机着色中的比例。现在我们知道，对于某些图G，包括G=K-p（p ≥ 4），这个猜想是不成立的。我们的主要结果是，猜想失败，如果G包含K-4作为一个子图，特别是它失败的几乎所有的图。
A former conjecture of Burr and Rosta [1], extending a conjecture of Erdos [2], asserted that in any two-colouring of the edges of a large complete graph, the proportion of subgraphs isomorphic to a fixed graph G which are monochromatic is at least the proportion found in a random colouring. It is now known that the conjecture fails for some graphs G, including G=K-p for p greater than or equal to 4.We investigate for which graphs G the conjecture holds. Our main result is that the conjecture fails if G contains K-4 as a subgraph, and in particular it fails for almost all graphs.