Tiling tripartite graphs with 3-colorable graphs (Q2380267)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Tiling tripartite graphs with 3-colorable graphs
scientific article

    Statements

    Tiling tripartite graphs with 3-colorable graphs (English)
    0 references
    0 references
    0 references
    26 March 2010
    0 references
    Summary: For any positive real number \(\gamma\) and any positive integer \(h\), there is \(N_0\) such that the following holds. Let \(N>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 [\textit{C. Magyar} and \textit{R. R. Martin}, Discrete Math. 254, No.~1--3, 289--308 (2002; Zbl 0995.05069)] 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\).
    0 references
    tripartite graph
    0 references
    perfect tiling
    0 references

    Identifiers