✦ LIBER ✦

A polynomial algorithm for constructing the clique graph of a line graph

✍ Scribed by Bruce Hedman

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 250 KB
Volume: 15
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(86)90019-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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__‐

A polynomial algorithm for the minimum w

A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs

✍ Wen-Lian HSU; George L. Nemhauser 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 688 KB

Discrete Mathematics 3X ( 19X2) 6S-71 North-Holland Publishing Company 65 Let G = (V, E) be a graph with a positive number wt(v) assigned to each L' E V. A weighted clique saver of the vertices of G is a collection of cliques with a non-negative weight yC. assigned to each clique C in the collection

A parallel algorithm for finding a maxim

A parallel algorithm for finding a maximum weight clique of an interval graph

✍ Chii-Huah Shyu 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 339 KB

The greedy clique decomposition of a gra

The greedy clique decomposition of a graph

✍ Sean McGuinness 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract We prove that if maximal cliques are removed one by one from any graph with __n__ vertices, then the graph will be empty after at most __n__^2^/4 steps. This proves a conjecture of Winkler.

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

An algorithm for the decomposition of gr

An algorithm for the decomposition of graphs into cliques

✍ Xiang-Ying Su 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 340 KB 👁 1 views

## Abstract Chung (F. R. K. Chung, On the decomposition of graphs, __SIAM J. Algebraic Discrete Methods__ 23 (1981), 1–12.) and independently Györi and Kostochka (E. Györi and A. V. Kostochka, On a problem of G. O. H. Katona and T. Tarján, __Acta Math. Acad. Sci. Hung.__ 34 (1979), 321–327.) proved