✦ LIBER ✦

Clique partitions and clique coverings

✍ Scribed by Paul Erd'́os; Ralph Faudree; Edward T. Ordman

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 575 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90197-5

No coin nor oath required. For personal study only.

✦ Synopsis

Several new tools are presented for determining the number of cliques needed to (edge-)partition a graph. For a graph on n vertices, the clique partition number can grow et-? times as fast as the clique covering number, where c is at least l/64. If in a clique on n vertices, the edges between cn" vertices are deleted, $ =G a < 1, then the number of cliques needed to partition what is left is asymptotic to &I'"; this fills in a gap between results of Wallis for a < 4 and Pullman and Donald for a = 1, c > !. Clique coverings of a clique minus a matching are also investigated.

📜 SIMILAR VOLUMES

On the number of distinct minimal clique

On the number of distinct minimal clique partitions and clique covers of a line graph

✍ Sean McGuinness; Rolf Rees 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 812 KB

Let G be a line graph. Orlin determined the clique covering and clique partition numbers cc(G) and cp(G). We obtain a constructive proof of Orlin's result and in doing so we are able to completely enumerate the number of distinct minimal clique covers and partitions of G, in terms of easily calculab

Generalized covering designs and clique

Generalized covering designs and clique coverings

✍ Robert F. Bailey; Andrea C. Burgess; Michael S. Cavers; Karen Meagher 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

Inspired by the "generalized t-designs" defined by Cameron [P. J. Cameron, Discrete Math 309 (2009), 4835-4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimu

Surfaces, Tree-Width, Clique-Minors, and

Surfaces, Tree-Width, Clique-Minors, and Partitions

✍ Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Dirk Vertigan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 214 KB

In 1971, Chartrand, Geller, and Hedetniemi conjectured that the edge set of a planar graph may be partitioned into two subsets, each of which induces an outerplanar graph. Some partial results towards this conjecture are presented. One such result, in which a planar graph may be thus edge partitione

Minimal clique partitions and pairwise b

Minimal clique partitions and pairwise balanced designs

✍ Rolf Rees 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 666 KB

We consider the problem of determining cp(G v KC), the smallest number of cliques required to partition the edge set of the graph G v K~, where G is a finite simple graph and K~, is the empty graph on m vertices. A lower bound on cp(G v K~,,,) is obtained which, when applied to the case G = K,, shar

On clique partitions of split graphs

✍ W.D. Wallis; J. Wu 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 204 KB

Wallis, W.D. and J. Wu, On clique partitions of split graphs, Discrete Mathematics 92 (1991) 427-429. Split graphs are graphs formed by taking a complete graph and an empty graph disjoint from it and some or all of the possible edges joining the two. We prove that the problem of deciding the clique

Clique partitions of the cocktail party

Clique partitions of the cocktail party graph

✍ D.A Gregory; S McGuinness; W Wallis 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 369 KB

Let To denote the complement of a perfect matching in the complete graph on v vertices, v even, and let cp(To) be the minimum number of cliques needed to partition the edge-set of To. We prove that cp(To)>-v for v 1> 8 and give a design characterization of the cases where equality holds. We also sho