Tiling Tripartite Graphs with 3-Colorable Graphs
Tiling Tripartite Graphs with 3-Colorable Graphs
复制标题
用三色图平铺三部分图
DOI：
--
复制
发表时间：
2008
影响因子：
0.7
通讯作者：
Yi Zhao
中科院分区：
文献类型：
--
作者：
Ryan R. Martin;Yi Zhao
对于任何正实数 $gamma$ 和任何正整数 $h$，存在 $N_0$ 使得以下成立。令$Nge N_0$ 使得$N$ 可以被$h$ 整除。如果 $G$ 是一个三方图，每个顶点类中有 $N$ 个顶点，并且每个顶点与其他每个类中至少 $(2/3+ gamma) N$ 个顶点相邻，则 $G$ 可以通过 $K_{h,h,h}$ 的副本完美平铺。这扩展了[离散数学。 254 (2002), 289–308] 并且还给出了通过任何固定的 3 色图进行平铺的充分条件。此外，我们表明结果中的最小度 $(2/3+ gamma) N$ 不能被 $2N/3+ h-2$ 替换。
For any positive real number $gamma$ and any positive integer $h$, there is $N_0$ such that the following holds. Let $Nge N_0$ be such that $N$ is divisible by $h$. If $G$ is a tripartite graph with $N$ vertices in each vertex class such that every vertex is adjacent to at least $(2/3+ gamma) N$ vertices in each of the other classes, then $G$ can be tiled perfectly by copies of $K_{h,h,h}$. This extends the work in [Discrete Math. 254 (2002), 289–308] and also gives a sufficient condition for tiling by any fixed 3-colorable graph. Furthermore, we show that the minimum-degree $(2/3+ gamma) N$ in our result cannot be replaced by $2N/3+ h-2$.
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus