✦ LIBER ✦

On covering all cliques of a chordal graph

✍ Scribed by Thomas Andreae; Carsten Flotow

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 205 KB
Volume: 149
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00276-o

No coin nor oath required. For personal study only.

✦ Synopsis

For a graph G = (V,E), a vertex set XC_ V is called a clique if Ixl>~2 and the graph G [X] induced by X is a complete subgraph maximal under inclusion. We say that a vertex set T is a clique-transversal set if T N X ~ 0 for all cliques X of G, and define the clique-transversal number re(G) as the minimum cardinality of a clique-transversal set. Let f~ be the class of * Corresponding author.

📜 SIMILAR VOLUMES

Covering all cliques of a graph

✍ Zsolt Tuza 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 701 KB

The following conjecture of T. Gallai is proved: If G is a chordal graph on n vertices, such that all its maximal complete subgraphs have order at least 3, then there is a vertex set of cardinality ~n/3 which meets all maximal complete subgraphs of G. Further related results are given.

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

Covering the cliques of a graph with ver

Covering the cliques of a graph with vertices

✍ Paul Erdős; Tibor Gallai; Zsolt Tuza 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 681 KB

The following problem is investigated. Given an undirected graph G, determine the smallest cardinality of a vertex set that meets all complete subgraphs KC G maximal under inclusion.

On clique covers and independence number

On clique covers and independence numbers of graphs

✍ Robert C. Brigham; Ronald D. Dutton 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 485 KB

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

On the chordality of a graph

✍ Terry A. McKee; Edward R. Scheinerman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 574 KB

## Abstract The __chordality__ of a graph __G__ = (__V, E__) is defined as the minimum __k__ such that we can write __E__ = __E__~1~ ∩ … ∩ __E__~__k__~ with each (__V, E__~__i__~) a chordal graph. We present several results bounding the value of this generalization of boxicity. Our principal result