Universal Obstructions of Graph Parameters

Authors Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos

Publication date 27 April 2023

Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We introduce a graph-parametric framework for obtaining obstruction characterizations of graph parameters with respect to partial ordering relations. For this, we define the notions of class obstruction, parametric obstruction, and universal obstruction as combinatorial objects that determine the asymptotic behavior of graph parameters. Our framework permits a unified framework for classifying graph parameters. Under this framework, we survey existing graph- theoretic results on most known graph parameters. Also we provide some unifying results on their classification.

This page was built for publication: Universal Obstructions of Graph Parameters

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