×

Packings by cliques and by finite families of graphs. (English) Zbl 0582.05046

If F is a family of connected graphs and G is a graph, then an F-packing of G is a subgraph of G each component of which belongs to F. This paper contains a polynomially bounded algorithm for finding an F-packing of G which as many vertices as possible when F contains \(K_ 2\) and all other graphs in F are hypomatchable, i.e., the deletion of any vertex leaves a graph with a perfect matching. If F does not contain \(K_ 2\), then the problem of finding an F-packing with as many vertices as possible is often NP-complete. This is shown to be the case when F consists of complete graphs of order at least 3 or when F consists of cycles of length at least 6.

MathOverflow Questions:

A decision problem in graph coloring

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[2] Bondy, J. A.; Murty, U. S.R, Graph Theory with Applications (1976), American Elsevier: American Elsevier New York · Zbl 1134.05001
[3] Cornuejols, G.; Pulleyblank, W., A matching problem with side conditions, Discrete Math., 29, 135-159 (1980) · Zbl 0446.05031
[4] Cunningham, W. H.; Marsh, A. B., A primal algorithm for optimum matching, Math. Programming Study, 8, 50-72 (1978) · Zbl 0409.90081
[5] Edmonds, J., Paths, trees, and flowers, Canad. J. Math., 17, 449-467 (1965) · Zbl 0132.20903
[6] Edmonds, J., Maximum matching and a polyhedron with (0, 1) vertices, J. Res. Nat. Bureau of Standards, 69B, 125-130 (1965) · Zbl 0141.21802
[7] Edmonds, J.; Johnson, E. L., Matching: a well-solved class of integer linear programs, (Guy, R. K.; etal., Combinatorial Structures and their Applications (1970), Gordon and Breach: Gordon and Breach New York), 89-92
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[9] Hell, P.; Kirkpatrick, D. G., Scheduling, matching, and coloring, (Colloq. Math. Soc. Janos Bolyai, 25 (1978), North-Holland: North-Holland Amsterdam), 272-280, Algebraic Methods in Graph Theory, Szeged (Hungary) · Zbl 0474.05054
[10] Hell, P.; Kirkpatrick, D. G., On generalized matching problems, Inform. Process. Letters, 12, 33-35 (1981) · Zbl 0454.68077
[11] P. Hell and D.G. Kirkpatrick, Packings by complete bipartite graphs, submitted to SIAM J. Algebraic Discrete Methods.; P. Hell and D.G. Kirkpatrick, Packings by complete bipartite graphs, submitted to SIAM J. Algebraic Discrete Methods. · Zbl 0597.05050
[12] P. Hell and D.G. Kirkpatrick, (g, \(f\); P. Hell and D.G. Kirkpatrick, (g, \(f\)
[13] Kirkpatrick, D. G.; Hell, P., On the completeness of a generalized matching problem, (Proc. Tenth Annual ACM Symposium on Theory of Computing (1978)), 240-245 · Zbl 1282.68182
[14] Kirkpatrick, D. G.; Hell, P., On the complexity of general graph factor problems, SIAM J. Computing, 12, 601-609 (1983) · Zbl 0525.68023
[15] Kuhn, H. W., The Hungarian method for the assignment problem, Naval Res. Logist. Quart., 2, 83-97 (1955) · Zbl 0143.41905
[16] Lawler, E. L., Combinatorial Optimization (1976), Holt, Rinehart, and Winston: Holt, Rinehart, and Winston New York · Zbl 0362.90076
[17] Lovász, L., Combinatorial Problems and Exercises (1979), North-Holland: North-Holland Amsterdam · Zbl 0439.05001
[18] Tutte, W. T., The factorisation of linear graphs, J. London Math. Soc., 22, 107-111 (1947) · Zbl 0029.23301
[19] Vornberger, O., Komplexität von Wegeproblemen in Graphen, Reihe Teoretische Informatik, 5 (1979), Universität Paderborn · Zbl 0461.05041
[20] Cornuejols, G.; Hartvigsen, D.; Pulleyblank, W., Packing Subgraphs in a Graph, Operations Research Letters, 4, 139-143 (Sept. 1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.