Clique packings and clique partitions of graphs without odd chordless cycles

• Autorzy: Zbigniew Lonc
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

clique partition; matching; min-max theorems

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1996
• Tom: 16
• Numer: 2
• Strony: 143-149

Daty

wydano

1996

otrzymano

1996-04-15

Twórcy

autor

Zbigniew Lonc

• Institute of Mathematics, Warsaw University of Technology, 00-661 Warsaw, Poland

Bibliografia

• [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).

Identyfikatory

DOI

10.7151/dmgt.1029