Letter graphs and modular decomposition

DOI10.1016/J.DAM.2021.11.007MaRDI QIDQ2065788zbMATH OpenOpenAlexFDO

Authors Robert Ferguson, Vincent Vatter

Publication date 13 January 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

lettericitymodular decompositionprime graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: We prove that if the prime graphs in a graph class have bounded lettericity, then the entire class has bounded lettericity if and only if it does not contain arbitrary large matchings, co-matchings, or a family of graphs that we call stacked paths.

Recommendations

• Letter graphs and well-quasi-order by induced subgraphs
• Modularity of minor‐free graphs
• Letter graphs and geometric grid classes of permutations
• Incremental modular decomposition
• Letter graphs and geometric grid classes of permutations: characterization and recognition

Cites work

• A simple proof of a theorem of Schmerl and Trotter for permutations
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• Geometric grid classes of permutations
• Inflations of geometric grid classes of permutations
• Labelled induced subgraphs and well-quasi-ordering
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Letter graphs and well-quasi-order by induced subgraphs
• Minimal indecomposable graphs
• On the stability number of AH‐free graphs
• Permutation classes
• The Micro-world of Cographs
• Transitiv orientierbare Graphen

Cited in

(4)

• scientific article; zbMATH DE number 5540038 (Why is no real title available?)
• Letter graphs and geometric grid classes of permutations
• Bounds on the lettericity of graphs
• Generalized lettericity of graphs

This page was built for publication: Letter graphs and modular decomposition

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