Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes
verfasst von : Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (WG 2015) gave a negative answer to this question, but their counterexample is a class that can only be characterised by infinitely many forbidden induced subgraphs. This raises the issue of whether their question has a positive answer for finitely defined hereditary graph classes. Apart from two stubborn cases, this has been confirmed when at most two induced subgraphs \(H_1,H_2\) are forbidden. We confirm it for one of the two stubborn cases, namely for the case \((H_1,H_2)=(\text {triangle},P_2+P_4)\) by proving that the class of \((\text {triangle},P_2+P_4)\)-free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of 3-partite graphs. We also use this technique to completely determine which classes of \((\text {triangle},H)\)-free graphs are well-quasi-ordered.