Graph Parameters, Universal Obstructions, and WQO

MaRDI QIDQ6432438zbMATH OpenFDO

Authors Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos

Publication date 7 April 2023

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics of partially ordered sets (06A07)

Abstract: We introduce the notion of universal obstruction of a graph parameter, with respect to some quasi-ordering relation. Universal obstructions may serve as compact characterizations of the asymptotic behavior of graph parameters. We provide order-theoretic conditions which imply that such a characterization is finite and, when this is the case, we present some algorithmic implications on the existence of fixed-parameter algorithms.

This page was built for publication: Graph Parameters, Universal Obstructions, and WQO

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432438)