Tiling tripartite graphs with 3-colorable graphs: The extreme case

Details Tiling tripartite graphs with 3-colorable graphs: The extreme case Tiling tripartite graphs with 3-colorable graphs: The extreme case

2010-01-06

arxiv.org/abs/1001.1002v1

Mathematics

Combinatorics

29pp

Scientific paper

There is a positive integer $N_0$ such that the following holds. Let $N\ge N_0$ 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 $2N/3+2h-1$ vertices in each of the other classes, then $G$ can be tiled perfectly by copies of $K_{h,h,h}$. This extends work by the authors and also gives a sufficient condition for tiling by any fixed 3-colorable graph. Furthermore, we show that the minimum-degree $2N/3+2h-1$ in our result can not be replaced by $2N/3+ h-2$ and that if $N$ is divisible by $6h$, then the required minimum degree is $2N/3+h-1$ for $N$ large enough and this is tight.

Affiliated with

Also associated with

No associations

Rating

Tiling tripartite graphs with 3-colorable graphs: The extreme case does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tiling tripartite graphs with 3-colorable graphs: The extreme case, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tiling tripartite graphs with 3-colorable graphs: The extreme case will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-373041