Publications of (and about) Paul Erdös
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 n2/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)n2/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