Copy the page URI to the clipboard
Cocks, Daniel
(2024).
DOI: https://doi.org/10.21954/ou.ro.00099116
Abstract
In the study of graphs, clique-width is a parameter that has received much attention due its significance in the tractability of algorithms on certain classes of graph. Of particular interest are hereditary graph classes, those classes closed under taking induced subgraphs. A number of minimal hereditary graph classes of unbounded clique-width (abbreviated to minimal classes) have recently been identified; that is, classes containing graphs with arbitrarily large clique-width but where every proper hereditary subclass has bounded clique-width. There are also hereditary classes of unbounded clique-width that do not contain a minimal subclass, but instead contain graph structures known as t-basic obstructions to bounded clique-width for arbitrarily large t. These graphs form a sequence known as an antichain of unbounded clique-width. We identify many new minimal classes and place all known minimal classes inside two `frameworks'. We also identify new t-basic obstructions to bounded clique-width.
In Chapters 2 and 3 we create our first framework for dense minimal classes, consisting of graph classes constructed by taking the finite induced subgraphs of an infinite graph Pδ whose vertices form a two-dimensional array and whose edges are defined by three objects, denoted as a triple δ =(α, β, γ). We introduce new methods to the study of clique-width, and identify uncountably many new minimal classes in the framework.
In sparse classes clique-width is unbounded if and only if the (widely studied) parameter, tree-width, is unbounded. In Chapter 4 we identify a new t-basic obstruction, a t-sail. We construct `path-star' graph classes defined by a nested word, with a recursive structure, in which a graph has large tree-width if and only if it contains a large t-sail. We show that these classes are infinitely defined and do not contain a minimal subclass.
In Chapter 5 we create an alternative framework for minimal classes to the one developed in Chapters 2 and 3, containing `path-clique' graph classes consisting of the finite induced subgraphs of an infinite graph created from the symmetric difference of edges between an infinite path and a partition of the path vertices forming infinite cliques or independent sets that are complete or anti-complete to each other. We identify another uncountable family of minimal classes different to those from the first framework.
In Chapter 6 we identify a new t-basic obstruction -- a t-clipper. We show that a graph in the class of permutation-partition graphs has large clique-width if and only if it contains a large t-clipper. We also identify other likely t-basic obstructions.
CORE (COnnecting REpositories)
CORE (COnnecting REpositories)
