𝔖 Bobbio Scriptorium
✦   LIBER   ✦

More characterizations of triangulated graphs

✍ Scribed by Claude Benzaken; Yves Crama; Pierre Duchet; Peter L. Hammer; Frédéric Maffray

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
420 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

New characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability function has all its coefficients equal to 0, +1 or −1.

📜 SIMILAR VOLUMES

Chromaticity of triangulated graphs
Chromaticity of triangulated graphs
✍ Paul Vaderlind 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

A graph G is called triangulated (or rigid-circuit graph, or chordal graph) if every circuit of G with length greater than 3 has a chord. It can be shown (see, UI, . . . , u,, . Let G = G,.

Characterizations of signed graphs
Characterizations of signed graphs
✍ Thomas Zaslavsky 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 271 KB

## Abstract The possible classes of balanced circles of a signed graph are characterized in two ways.

Partial characterizations of circular-ar
Partial characterizations of circular-arc graphs
✍ F. Bonomo; G. Durán; L.N. Grippo; M.D. Safe 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

## Abstract A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minim

Metric characterizations of proper inter
Metric characterizations of proper interval graphs and tree-clique graphs
✍ Gutierrez, M.; Oubi�a, L. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

On the Interval Number of a Triangulated
On the Interval Number of a Triangulated Graph
✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 2 views

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect