Tiling tripartite graphs with 3-colorable graphs

MaRDI QIDQ2380267zbMATH OpenFDO

Authors Ryan R. Martin, Yi Zhao

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.4154, https://eudml.org/doc/229474, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r109.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

perfect tilingtripartite graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: For a fixed integer h>=1, let G be a tripartite graph with N vertices in each vertex class, N divisible by 6h, such that every vertex is adjacent to at least 2N/3+h-1 vertices in each of the other classes. We show that if N is sufficiently large, then G can be tiled perfectly by copies of K_{h,h,h}. This extends the work in [19] and also gives a sufficient condition for tiling by any (fixed) 3-colorable graph. Furthermore, we show that this minimum-degree condition is best possible and provide very tight bounds when N is divisible by h but not by 6h.

Review text

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\).

Recommendations

• Tiling tripartite graphs with 3-colorable graphs: the extreme case
• On the partition of 3-colorable graphs
• Triangulating 3-Colored Graphs
• Color sets of tripartite graphs
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Coloring with three‐colored subgraphs
• A class of three-colorable triangle-free graphs
• On a tiling conjecture of Komlós for 3-chromatic graphs.
• On 3-hued coloring of graphs
• Tilings with trichromatic colored-edges triangles

Cited in

(9)

• On a tiling conjecture of Komlós for 3-chromatic graphs.
• Tiling tripartite graphs with 3-colorable graphs: the extreme case
• On multipartite Hajnal-Szemerédi theorems
• Asymptotic multipartite version of the Alon-Yuster theorem
• Tiling 3-uniform hypergraphs with K₄^3-2e
• Minimum degree thresholds for bipartite graph tiling
• Triangle-tilings in graphs without large independent sets
• On 3-colorings of bipartitep-threshold graphs
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs

This page was built for publication: Tiling tripartite graphs with 3-colorable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380267)