Discussiones Mathematicae Graph Theory 16(2) (1996)
143-149
DOI: https://doi.org/10.7151/dmgt.1029
CLIQUE PACKINGS AND CLIQUE PARTITIONS OF GRAPHS WITHOUT ODD CHORDLESS CYCLES
Zbigniew Lonc
Institute of Mathematics, Warsaw University of
Technology
00-661 Warsaw, Poland
Abstract
In this paper we consider partitions (resp. packings) of graphs without odd chordless cycles into cliques of order at least 2. We give a structure theorem, min-max results and characterization theorems for this kind of partitions and packings.
Keywords: clique partition, matching, min-max theorems.
1991 Mathematics Subject Classification: 05C70.
References
[1] | G. Cornuéjols, D. Hartvigsen and W. Pulleyblank, Packings subgraphs in a graph, Operations Research Letters 1 (1982) 139-143, doi: 10.1016/0167-6377(82)90016-5. |
[2] | P. Hell and D.G. Kirkpatrick, On the complexity of general graph factor problems, SIAM Journal of Computing 12 (1983) 601-609, doi: 10.1137/0212040. |
[3] | P. Hell and D.G. Kirkpatrick, Packing by cliques and by finite families of graphs, Discrete Math. 49 (1984) 45-59, doi: 10.1016/0012-365X(84)90150-X. |
[4] | Z. Lonc, Chain partitions of ordered sets, Order 11 (1994) 343-351, doi: 10.1007/BF01108766. |
[5] | L. Lovász and M.D. Plummer, Matching Theory (North Holland, Amsterdam, 1986). |
Close