Scattered Classes of Graphs

Abstract

Abstract. For a class C of graphs G equipped with functions fG dened on subsets of EpGq or V pGq, we say that C is k-scattered with respect to fG if there exists a constant ` such that for every graph G P C, the domain of fG can be partitioned into subsets of size at most k so that the union of every collection of the subsets has fG value at most `. 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 mK1;n vertex-minor, which allows us to prove that such graphs have bounded linear rank-width.