𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partitions of graphs into one or two independent sets and cliques

✍ Scribed by Andreas Brandstädt

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
417 KB
Volume
152
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 in polynomial time whether a graph can be partitioned into two split graphs.

A time bound O(n 3 ) is given for the recognition of graphs which can be partitioned into two independent sets and one clique (one independent set and two cliques, resp.), and a time bound O(n 4 ) is given for the recognition of graphs which can be partitioned into two independent sets and two cliques.

📜 SIMILAR VOLUMES

Clique polynomials and independent set p
Clique polynomials and independent set polynomials of graphs
✍ Cornelis Hoede; Xueliang Li 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 492 KB

This paper introduces two kinds of graph polynomials, clique polynomial and independent set polynomial. The paper focuses on expansions of these polynomials. Some open problems are mentioned.

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

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

Algorithms for a maximum clique and a ma
Algorithms for a maximum clique and a maximum independent set of a circle graph
✍ F. Gavril 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 523 KB

## Abstract Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum indepen