Clique Partitions of Chordal Graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Combinatorics, probability & computing probability & computing, 1993-12, Vol.2 (4), p.409-415
Main Authors: Erdős, Paul, Ordman, Edward T., Zalcstein, Yechezkel
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0963-5483
1469-2163
DOI:10.1017/S0963548300000808