Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details

Dabrowski, K.K., Lozin, V.V. & Paulusma, D. (2020). Clique-width and well-quasi ordering of triangle-free graph classes. Journal of Computer and System Sciences 108: 64-91.

Author(s) from Durham

Abstract

We obtain a complete classification of graphs H for which the class of -free graphs is well-quasi-ordered by the induced subgraph relation and an almost complete classification of graphs H for which the class of -free graphs has bounded clique-width. In particular, we show that for these graph classes, well-quasi-orderability implies boundedness of clique-width. To obtain our results, we further refine a known method based on canonical decomposition. This leads to a new decomposition technique that is applicable to both notions, well-quasi-orderability and clique-width.