Tiling tripartite graphs with 3-colorable graphs
The electronic journal of combinatorics, Tome 16 (2009) no. 1
For any positive real number $\gamma$ and any positive integer $h$, there is $N_0$ such that the following holds. Let $N\ge 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$.
@article{10_37236_198,
author = {Ryan Martin and Yi Zhao},
title = {Tiling tripartite graphs with 3-colorable graphs},
journal = {The electronic journal of combinatorics},
year = {2009},
volume = {16},
number = {1},
doi = {10.37236/198},
zbl = {1186.05055},
url = {http://geodesic.mathdoc.fr/articles/10.37236/198/}
}
Ryan Martin; Yi Zhao. Tiling tripartite graphs with 3-colorable graphs. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/198
Cité par Sources :