Scattered classes of graphs

Abstract

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 $m{K}_{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)

Cited by in corpus (3)

• The grid theorem for vertex-minors
• Obstructions for bounded shrub-depth and rank-depth
• Graphs of bounded depth-$2$ rank-brittleness