##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 793.05081

**Autor: ** Erdös, Paul; Ordman, Edward T.; Zalcstein, Yechezkel

**Title: ** Clique partitions of chordal graphs. (In English)

**Source: ** Comb. Probab. Comput. 2, No.4, 409-415 (1993).

**Review: ** To partition the edges of a chordal graph on n vertices into cliques may require as many as n^{2}/6 cliques; there is an example requiring this many, which is also a threshold graph and a split graph. It is unknown whether this many cliques will always suffice. We are able to show that (1- c)n^{2}/4 cliques will suffice for some c > 0.

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C70 Factorization, etc.

**Keywords: ** clique covering; clique partition; partition; chordal graph; cliques; threshold graph; split graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag