ArticleOriginal scientific text
Title
Clique packings and clique partitions of graphs without odd chordless cycles
Authors 1
Affiliations
- Institute of Mathematics, Warsaw University of Technology
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
Bibliography
- 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.
- 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.
- 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.
- Z. Lonc, Chain partitions of ordered sets, Order 11 (1994) 343-351, doi: 10.1007/BF01108766.
- L. Lovász and M.D. Plummer, Matching Theory (North Holland, Amsterdam, 1986).
Pages:
143-149
Main language of publication
English
Received
1996-04-15
Published
1996
Exact and natural sciences