
arXiv: 2206.15054
A graph $H$ is an induced subgraph of a graph $G$ if a graph isomorphic to $H$ can be obtained from $G$ by deleting vertices. Recently, there has been significant interest in understanding the unavoidable induced subgraphs for graphs of large treewidth. Motivated by this work, we consider the analogous problem for pathwidth: what are the unavoidable induced subgraphs for graphs of large pathwidth? While resolving this question in the general setting looks challenging, we prove various results for sparse graphs. In particular, we show that every graph with bounded maximum degree and sufficiently large pathwidth contains a subdivision of a large complete binary tree or the line graph of a subdivision of a large complete binary tree as an induced subgraph. Similarly, we show that every graph excluding a fixed minor and with sufficiently large pathwidth contains a subdivision of a large complete binary tree or the line graph of a subdivision of a large complete binary tree as an induced subgraph. Finally, we present a characterisation for when a hereditary class defined by a finite set of forbidden induced subgraphs has bounded pathwidth.
Graph operations (line graphs, products, etc.), pathwidth, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), bounded maximum degree, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), Combinatorics (math.CO), Paths and cycles, sparse graphs
Graph operations (line graphs, products, etc.), pathwidth, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), bounded maximum degree, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), Combinatorics (math.CO), Paths and cycles, sparse graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
