Extension of hereditary classes with substitutions

✍ Scribed by Igor Zverovich

• Book ID: 104294110
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 272 KB
• Volume: 128
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00507-3

✦ Synopsis

Let G and H be graphs.

For a hereditary class of graphs P, the substitutional closure of P is deÿned as the class P * consisting of all graphs which can be obtained from graphs in P by repeated substitutions.

Let P be an arbitrary hereditary class for which a characterization in terms of forbidden induced subgraphs is known. We propose a method of constructing forbidden induced subgraphs for P * .