Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes

Daligault, Rao and Thomasse 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) = (triangle, P-2 + P-4) by proving that the class of (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 (triangle, H)-free graphs are well-quasi-ordered.