论文标题
有界变性和程度的图表的分区普遍性
Partition universality for graphs of bounded degeneracy and degree
论文作者
论文摘要
我们证明，在图$ g $的边数中，必须具有渐近最佳的界限，以便为$ e（g）$的任何$ r $颜色颜色具有颜色类，其中包含$ n $ dementer的每$ d $ devenerate图，$ n $ n $ dembergrage in $ n $ vertices具有最高限制的最高学位。我们还必须提高边缘数量$ g $必须具有的上限，以便任何$ e（g）$的$ r $颜色具有一个颜色类，其中包含每$ n $ vertex图，最高度$δ$，每$δ\ ge 4 $。在这两种情况下，我们都表明，具有$ CN $顶点的二项式随机图，合适的边缘概率可能会提供所需的$ G $。
We prove asymptotically optimal bounds on the number of edges a graph $G$ must have in order that any $r$-colouring of $E(G)$ has a colour class which contains every $D$-degenerate graph on $n$ vertices with bounded maximum degree. We also improve the upper bounds on the number of edges $G$ must have in order that any $r$-colouring of $E(G)$ has a colour class which contains every $n$-vertex graph with maximum degree $Δ$, for each $Δ\ge 4$. In both cases, we show that a binomial random graph with $Cn$ vertices and a suitable edge probability is likely to provide the desired $G$.
