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 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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page