Induced subgraphs and well‐quasi‐ordering | Zendy

Damaschke Peter | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Induced subgraphs and well‐quasi‐ordering

Author(s) -

Damaschke Peter

Publication year - 1990

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.3190140406

Subject(s) - mathematics , combinatorics , induced subgraph , class (philosophy) , simple (philosophy) , cograph , chordal graph , ideal (ethics) , order (exchange) , discrete mathematics , graph , 1 planar graph , computer science , philosophy , epistemology , finance , artificial intelligence , vertex (graph theory) , economics

We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤ i , and (2) well‐quasi‐ordered (WQO) by this relation. The main result shows that the class of cographs ( P 4 ‐free graphs) is WQO by ≤ i , and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove that P 4 ‐reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤ i are also given.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research