# Well-quasi-ordering does not imply bounded clique-width

**Speaker:**Igor Razgon, Birkbeck, University of London.**Date:**Tuesday, 27 October 2015 from 16:00 to 17:00**Location:**Malet 151

Suppose we have an order relation on a class ${\bf G}$ of graphs.

We say that this relation is well-quasi order WQO if ${\bf G}$ does not

contain an infinite antichain. WQO relations are an important part

of the modern graph theory research. For, example, the famous theorem

of Robertson and Seymour states that that graph minor relation is

WQO. This theorem led researchers to consider other order relations

on graph. One such widely considered relation is induced subgraph.

It is easy to show that the induced subgraph relation is not WQO:

consider the set of all cycles. Therefore, a natural research direction

is to identify classes of graphs that *are* WQO by the induced subgraph

relation. It is customary to look for hereditary classes where containement

of a graph implies containement of all its induced subgraphs. Several such

classes have been identified.

Daligault, Rao, and Thomasse (Order 2010) asked a question whether every class

that is WQO by the induced subgraph relation is of bounded cliquewidth.

(Cliquewidth is a structural graph parameter. Many computationally intractable

problems become polynomially solvable on graphs of bounded cliquewidth.)

The beauty of this question is that, on the one hand, WQO classes and cliquewidth

look completely unrelated and, on the other hand, WQO classes look quite restrictive.

So, it is conceivable that a WQO classes have *some* structural parameter restricted.

Cliquewidth is a good candidate for such a parameter because classes of bounded

cliquewidth (unlike treewidth) capture dense graphs. So, the initial working hypothesis

among the researchers was that the answer to the above questions is positive.

We have recently shown, however, that the answer is in fact, negative. In particular,

there is class of graphs, WQO by the induced subgraph relation, whose

cliquewidth cannot be bounded by any constant. The main part of my talk is related

to presentation of this result. I will also discuss the hypothesis in the above

paper that for a more restrictive labelled induced subgraph relation being WQO

*does* imply bounded cliquewidth. The talk is self contained, all the required notions,

such as well quasi orderability and cliquewidth will be introduced during the talk.

Joint work with V. Lozin and V. Zamaraev. The preprint is available at:

http://arxiv.org/abs/1503.00571