✦ LIBER ✦

Chordal graphs, interval graphs, and wqo

✍ Scribed by Ding, Guoli

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 240 KB
Volume: 28
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199806)28:2<105::aid-jgt4>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

Let be the induced-minor relation. It is shown that, for every t, all chordal graphs of clique number at most t are well-quasi-ordered by . On the other hand, if the bound on clique number is dropped, even the class of interval graphs is not well-quasi-ordered by .

📜 SIMILAR VOLUMES

Graphs whose powers are chordal and grap

Graphs whose powers are chordal and graphs whose powers are interval graphs

✍ Flotow, Carsten 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

The main theorem of this paper gives a forbidden induced subgraph condition on G that is sufficient for chordality of G m . This theorem is a generalization of a theorem of Balakrishnan and Paulraja who had provided this only for m = 2. We also give a forbidden subgraph condition on G that is suffi

Restricted unimodular chordal graphs

✍ Peled, Uri N.; Wu, Julin 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

A chordal graph is called restricted unimodular if each cycle of its vertex-clique incidence bipartite graph has length divisible by 4. We characterize these graphs within all chordal graphs by forbidden induced subgraphs, by minimal relative separators, and in other ways. We show how to construct t

Random interval graphs

✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o

Tough enough chordal graphs are Hamilton

Tough enough chordal graphs are Hamiltonian

✍ Chen, Guantao; Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 2 views

We prove that every 18-tough chordal graph has a Hamiltonian cycle.

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 👁 1 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

Well covered simplicial, chordal, and ci

Well covered simplicial, chordal, and circular arc graphs

✍ Prisner, Erich; Topp, Jerzy; Vestergaard, Preben Dahl 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB 👁 1 views

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we,characterize well covered simplicial, chordal and circular arc graphs.