๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Variations of maximum-clique transversal sets on graphs

โœ Scribed by Chuan-Min Lee

Publisher
Springer US
Year
2009
Tongue
English
Weight
882 KB
Volume
181
Category
Article
ISSN
0254-5330

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,(

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

Hitting all maximum cliques with a stabl
Hitting all maximum cliques with a stable set using lopsided independent transversals
โœ Andrew D. King ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 82 KB

Rabern recently proved that any graph with โ‰ฅ 3 4 ( +1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with > 2 3 ( +1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding a