𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of chordal graphs and the maximum clique problem

✍ Scribed by Assef Chmeiss; Philippe Jégou

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
584 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is chordal or triangulated if it has no chordless cycle with four or more vertices. Chordal graphs are well known for their combinatorial and algorithmic properties. Here we introduce a generalization of chordal graphs, namely CSGk graphs. Informally, a CSG' graph is a complete graph, and for k > 0, the class of CSGk graphs is defined inductively in a such manner that CSG' Graphs are chordal graphs. We show that CSGk Graphs inherit of the same kind of properties as chordal graph. As a consequence, we show that the maximum clique problem is polynomial on CSGk graphs while this problem is NP-hard in the general case. @ 1997 Elsevier Science B.V.

📜 SIMILAR VOLUMES

A generalization of chordal graphs
A generalization of chordal graphs
✍ P. D. Seymour; R. W. Weaver 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t

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

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