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

Clique covering and clique partition in generalizations of line graphs

โœ Scribed by Erich Prisner

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
387 KB
Volume
56
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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

A common generalization of line graphs a
A common generalization of line graphs and clique graphs
โœ Erich Prisner ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 664 KB

## Abstract Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a __k__โ€edge of a graph we mean a complete subgraph with __k__ vertices or a clique with fewer than __k__ vertices. The __k__โ€

Clique and anticlique partitions of grap
Clique and anticlique partitions of graphs
โœ Krzysztof Bryล›; Zbigniew Lonc ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 408 KB

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.

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