✦ LIBER ✦

The greedy clique decomposition of a graph

✍ Scribed by Sean McGuinness

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 181 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180412

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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

Clique: A suite of programs for extracti

Clique: A suite of programs for extracting cliques from a symmetric graph

✍ J. E. Alt; N. Schofield 📂 Article 📅 1975 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 1 views

An upper bound on the size of a largest

An upper bound on the size of a largest clique in a graph

✍ Dennis P. Geoffroy; David P. Sumner 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB 👁 1 views

## Abstract A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set __G__^O^ of all vertices, __v__, such that __G__–__v__ is point determining. In this paper we show that the size, ω(__G__), of a maximum clique in __G__ sat

An upper bound on the number of cliques

An upper bound on the number of cliques in a graph

✍ Martin Farber; Mihály Hujter; Zsolt Tuza 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

Revised Greedy algorithm for formation o

Revised Greedy algorithm for formation of a minimal cycle basis of a graph

✍ Kaveh, A. ;Roosta, G. R. 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB 👁 1 views

## SUM MARY An efficient algorithm is developed for the formation of a minimal cycle basis of a graph. This method reduces the number of cycles to be considered as (candidates for being the elements of a minimal basis and makes practical use of the Greedy algorithm feasible. A comparison is made b

An upper bound on the size of the larges

An upper bound on the size of the largest cliques in a graph

✍ Alain Billionnet 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB 👁 1 views

## Abstract We produce in this paper an upper bound for the number of vertices existing in a clique of maximum cardinal. The proof is based in particular on the existence of a maximum cardinal clique that contains no vertex __x__ such that the neighborhood of __x__ is contained in the neighborhood