Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Clique-width and well-quasi ordering of triangle-free graph classes.

Dabrowski, K.K. and Lozin, V.V. and Paulusma, D. (2017) 'Clique-width and well-quasi ordering of triangle-free graph classes.', in Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers. Cham: Springer, pp. 220-233. Lecture notes in computer science. (10520).

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 H1,H2H1,H2 are forbidden. We confirm it for one of the two stubborn cases, namely for the case (H1,H2)=(triangle,P2+P4)(H1,H2)=(triangle,P2+P4) by proving that the class of (triangle,P2+P4)(triangle,P2+P4) -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)(triangle,H) -free graphs are well-quasi-ordered.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(449Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-319-68705-6_17
Publisher statement:The final publication is available at Springer via https://doi.org/10.1007/978-3-319-68705-6_17.
Date accepted:31 July 2017
Date deposited:29 August 2017
Date of first online publication:02 November 2017
Date first made open access:02 November 2018

Save or Share this output

Export:
Export
Look up in GoogleScholar