Scattered classes of graphs

DOI10.1137/19M1293776MaRDI QIDQ4959761zbMATH OpenFDO

Authors O-joung Kwon, Sang-Il Oum

Publication date 7 April 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.06004

zbMATH Keywords

graph structuresubgraphvertex-minor

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: For a class $mathcalC$ of graphs $G$ equipped with functions $f_G$ defined on subsets of $E(G)$ or $V(G)$, we say that $mathcalC$ is $k$-scattered with respect to $f_G$ if there exists a constant $ell$ such that for every graph $GinmathcalC$, 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.

Recommendations

• Graphs of bounded depth‐2 rank‐brittleness
• Excluded vertex-minors for graphs of linear rank-width at most k.
• First order properties on nowhere dense structures
• Rank-width and vertex-minors
• Rank-width and tree-width of \(H\)-minor-free graphs

Cites work

• Algorithmic meta-theorems for restrictions of treewidth
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Clique-width of graphs defined by one-vertex extensions
• Complement reducible graphs
• Decomposition of Directed Graphs
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Excluding a bipartite circle graph from line graphs
• Graph theory
• scientific article; zbMATH DE number 15493 (Why is no real title available?)
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• scientific article; zbMATH DE number 4183450 (Why is no real title available?)
• Intersection Theorems for Systems of Sets
• Isotropic systems
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Matrices and matroids for systems analysis
• Obstructions for bounded shrub-depth and rank-depth
• On the relationship between NLC-width and linear NLC-width
• Parameterized Algorithms for Modular-Width
• Rank-width and vertex-minors
• Rank-width: algorithmic and structural results
• Sparsity. Graphs, structures, and algorithms
• The complexity of the vertex-minor problem
• The grid theorem for vertex-minors
• Thread graphs, linear rank-width and their algorithmic applications
• Unavoidable minors of large 3-connected binary matroids
• Unavoidable vertex-minors in large prime graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited in

(4)

• Obstructions for bounded shrub-depth and rank-depth
• The grid theorem for vertex-minors
• Graphs of bounded depth‐2 rank‐brittleness
• An overview of universal obstructions for graph parameters

This page was built for publication: Scattered classes of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959761)