𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Clique and anticlique partitions of graphs

✍ Scribed by Krzysztof Bryś; Zbigniew Lonc

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
408 KB
Volume
185
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In the paper we prove that, for a fixed k, the problem of deciding whether a graph admits a partition of its vertex set into k-element cliques or anticliques (i.e. independent sets) is polynomial.

📜 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

Clique partitions and clique coverings
Clique partitions and clique coverings
✍ Paul Erd'́os; Ralph Faudree; Edward T. Ordman 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 575 KB

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" ve

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

Partitioning chordal graphs into indepen
Partitioning chordal graphs into independent sets and cliques
✍ Pavol Hell; Sulamita Klein; Loana Tito Nogueira; Fábio Protti 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 217 KB

We consider the following generalization of split graphs: A graph is said to be a (k; ')-graph if its vertex set can be partitioned into k independent sets and ' cliques. (Split graphs are obtained by setting k = ' = 1.) Much of the appeal of split graphs is due to the fact that they are chordal, a

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