DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 16(2) (1996) 143-149
DOI: 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).