Well-quasi-ordered classes of graphs and bounded linear clique-width

Speaker(s)

Aliaume Lopez

Affiliation

University of Warsaw

Language of the talk

English

Date

April 9, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Well-quasi-ordered classes of graphs and bounded linear clique-width

Seminar

Seminar Automata Theory

---

A quasi-ordered set (X, ≤) is a well-quasi-order (WQO) whenever it
contains neither infinite antichains, nor infinite decreasing sequences.
A cornerstone result of structural graph theory is the Graph Minor
Theorem of Robertson and Seymour, stating that the class of all graphs
is well-quasi-ordered by the graph minor relation. This result has
profound implications in graph theory, and algorithmic consequences such
as the polynomial-time solvability of whether a graph can be embedded
into a given surface.

The class of all (finite, undirected) graphs is not well-quasi-ordered
by the induced subgraph relation, and there has been considerable
interest in characterizing classes 𝒞 of finite graphs that are
well-quasi-ordered for this relation. Most proof schemes used to
construct such classes will actually prove that they are WQO even in the
presence of a finite number of colours on their vertices. A conjecture
from Daligault, Rao and Thomassé states that a class that is WQO with
two colours has bounded clique width.

In this talk, I will explain how to characterize classes of bounded
linear clique with that are WQO when coloured with finitely many
colours, and show that this property is actually decidable. This will
also be an opportunity to connect classical results of WQO theory
(Higman’s lemma, Kruskal’s tree theorem) to the study of such graph
classes, and answer in this (not so) restricted setting to some open
questions of Pouzet.

---