Article contents
Clique Partitions of Chordal Graphs†
Published online by Cambridge University Press: 12 September 2008
Abstract
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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Cambridge University Press 1993
References
- 3
- Cited by