Skip to content Search
Search our website:

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