## Abstract

It is known that the set of all simple graphs is not well-quasi-ordered by the induced subgraph relation, i.e. it contains infinite antichains (sets of incomparable elements) with respect to this relation. However, some particular graph classes are well-quasi-ordered by induced subgraphs. Moreover, some of them are well-quasi-ordered by a stronger relation called labelled induced subgraphs. In this paper, we conjecture that a hereditary class X which is well-quasi-ordered by the induced subgraph relation is also well-quasi-ordered by the labelled induced subgraph relation if and only if X is defined by finitely many minimal forbidden induced subgraphs. We verify this conjecture for a variety of hereditary classes that are known to be well-quasi-ordered by induced subgraphs and prove a number of new results supporting the conjecture.

Original language | English |
---|---|

Pages (from-to) | 313-328 |

Number of pages | 16 |

Journal | Order |

Volume | 32 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1 Nov 2015 |

Externally published | Yes |

## Keywords

- Induced subgraph
- Infinite antichain
- Labelled induced subgraphs
- Well-quasi-order