
arXiv: 1801.06004
For a class $\mathcal C$ of graphs $G$ equipped with functions $f_G$ defined on subsets of $E(G)$ or $V(G)$, we say that $\mathcal{C}$ is $k$-scattered with respect to $f_G$ if there exists a constant $\ell$ such that for every graph $G\in \mathcal C$, the domain of $f_G$ can be partitioned into subsets of size at most $k$ so that the union of every collection of the subsets has $f_G$ value at most $\ell$. We present structural characterizations of graph classes that are $k$-scattered with respect to several graph connectivity functions. In particular, our theorem for cut-rank functions provides a rough structural characterization of graphs having no $mK_{1,n}$ vertex-minor, which allows us to prove that such graphs have bounded linear rank-width.
42 pages, 5 figures. Final version.(Fixing minor typos in 7.4)
graph structure, vertex-minor, FOS: Mathematics, Mathematics - Combinatorics, 05C75, Graph minors, Structural characterization of families of graphs, subgraph, Combinatorics (math.CO)
graph structure, vertex-minor, FOS: Mathematics, Mathematics - Combinatorics, 05C75, Graph minors, Structural characterization of families of graphs, subgraph, Combinatorics (math.CO)
| 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). | 3 | |
| 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. | Average | |
| 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. | Average |
