Journal of Combinatorics

Volume 10 (2019)

Number 2

Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation

Pages: 327 – 337

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n2.a8

Authors

Aistis Atminas (Mathematics Institute, University of Warwick, Coventry, United Kingdom)

Vadim Lozin (Mathematics Institute, University of Warwick, Coventry, United Kingdom)

Igor Razgon (Department of Computer Science and Information Systems, Birkbeck University of London, United Kingdom)

Abstract

Recently, Daligault, Rao and Thomassé asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. While the question has been shown to have a negative answer in general [9], in the present paper we show that the statement is true for a family of hereditary classes of graphs that exclude large bicliques as subgraphs. In particular, this implies (through the use of Courcelle theorem [2]) that any problem definable in Monadic Second Order Logic can be solved in a polynomial time for all well-quasi-ordered hereditary classes of graphs that exclude large bicliques.

Full Text (PDF format)

This work was supported by EPSRC grant EP/L020408/1.

Received 26 January 2014

Published 25 January 2019