An Overview of Universal Obstructions for Graph Parameters
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914521991348224 |
|---|---|
| author | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. |
| author_facet | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. |
| contents | In a recent work, we introduced a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $\leqslant$ on graphs. Towards this, we proposed the concepts of class obstruction, parametric obstruction, and universal obstruction as combinatorial objects that determine the approximate behaviour of a graph parameter. In this work, we explore its potential as a unifying framework for classifying graph parameters. Under this framework, we survey existing graph-theoretic results on many known graph parameters. Additionally, we provide some unifying results on their classification. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_14121 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Overview of Universal Obstructions for Graph Parameters Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Discrete Mathematics Combinatorics 05C85, 05C83, 05C75 G.2.2 In a recent work, we introduced a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $\leqslant$ on graphs. Towards this, we proposed the concepts of class obstruction, parametric obstruction, and universal obstruction as combinatorial objects that determine the approximate behaviour of a graph parameter. In this work, we explore its potential as a unifying framework for classifying graph parameters. Under this framework, we survey existing graph-theoretic results on many known graph parameters. Additionally, we provide some unifying results on their classification. |
| title | An Overview of Universal Obstructions for Graph Parameters |
| topic | Discrete Mathematics Combinatorics 05C85, 05C83, 05C75 G.2.2 |
| url | https://arxiv.org/abs/2304.14121 |