| Full text | |
| Author(s): |
Han, Jie
;
Gopal, TV
;
Jager, G
;
Steila, S
Total Authors: 4
|
| Document type: | Journal article |
| Source: | THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017); v. 10185, p. 15-pg., 2017-01-01. |
| Abstract | |
Let H be a graph of order h and let G be a graph of order n such that h vertical bar n. A perfect H-packing in G is a collection of vertex disjoint copies of H in G that covers all vertices of G. Hell and Kirk-patrick showed that the decision problem whether a graph G has a perfect H-packing is NP-complete if and only if H has a component which contains at least 3 vertices. We consider the decision problem of containment of a perfect H-packing in graphs G under the additional minimum degree condition. Our main result shows that given any gamma > 0 and any n-vertex graph G with minimum degree at least (1 - 1/chi(cr)(H) + gamma)n, the problem of determining whether G has a perfect H-packing can be solved in polynomial time, where chi(cr)(H) is the critical chromatic number of H. This answers a question of Yuster negatively. Moreover, a hardness result of Kuhn and Osthus shows that our main result is essentially best possible and closes a long-standing hardness gap for all complete multi-partite graphs H whose second smallest color class has size at least 2. (AU) | |
| FAPESP's process: | 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 15/07869-8 - Perfect matchings and Tilings in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships abroad - Research Internship - Post-doctor |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |