𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs

✍ Scribed by Zuosong Liang; Erfang Shan

Book ID
113663251
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
133 KB
Volume
111
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Clique-transversal sets of line graphs a
Clique-transversal sets of line graphs and complements of line graphs
✍ Thomas Andreae; Martin Schughart; Zsolt Tuza πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 704 KB

Andreae, T., M. Schughart and Z. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Mathematics 88 (1991) 11-20. A clique-transversal set T of a graph G is a set of vertices of G such that T meets all maximal cliques of G. The clique-transversal number, denoted t,(

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

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.