Greedy maximum-clique decompositions |
| |
Authors: | Sean McGuinness |
| |
Institution: | (1) Present address: Dept. of Mathematics, University of Umeå, Umeå, Sweden;(2) Department of Mathematics and Computer Science, Odense University, Odense, Denmark |
| |
Abstract: | A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. We have recently shown that any greedy clique decomposition of a graph of ordern has at mostn
2/4 cliques. A greedy max-clique decomposition is a particular kind cf greedy clique decomposition where maximum cliques are removed, instead of just maximal ones. In this paper, we show that any greedy max-clique decompositionC of a graph of ordern has, wheren(C) is the number of vertices inC. |
| |
Keywords: | 05 C 35 |
本文献已被 SpringerLink 等数据库收录! |
|