Journal of Combinatorics
Volume 10 (2019)
Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
Pages: 327 – 337
Recently, Daligault, Rao and Thomassé asked in  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 , 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 ) 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.
This work was supported by EPSRC grant EP/L020408/1.
Received 26 January 2014
Published 25 January 2019