𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Clique partitions of the cocktail party graph

✍ Scribed by D.A Gregory; S McGuinness; W Wallis

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
369 KB
Volume
59
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 show that, asymptotically, cp (To) <-v log log v.

πŸ“œ SIMILAR VOLUMES

On clique partitions of split graphs
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

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

On the partition and coloring of a graph
On the partition and coloring of a graph by cliques
✍ W.D. Wallis; Guo-Hui Zhang πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 859 KB

Wallis, W.D. and G.-H. Zhang, On the partition and coloring of a graph by cliques, Discrete Mathematics 120 (1993) 191-203. We first introduce the concept of the k-chromatic index of a graph, and then discuss some of its properties. A characterization of the clique partition number of the graph G V

Partitions of graphs into one or two ind
Partitions of graphs into one or two independent sets and cliques
✍ Andreas BrandstΓ€dt πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 417 KB

It is shown in this note that it can be recognized in polynomial time whether the vertex set of a finite undirected graph can be partitioned into one or two independent sets and one or two cliques. Such graphs generalize bipartite and split graphs and the result also shows that it can be recognized

The greedy clique decomposition of a gra
The greedy clique decomposition of a graph
✍ Sean McGuinness πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 181 KB

## Abstract We prove that if maximal cliques are removed one by one from any graph with __n__ vertices, then the graph will be empty after at most __n__^2^/4 steps. This proves a conjecture of Winkler.