Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs

DOI10.1016/J.DAM.2023.09.034zbMATH Open1529.05131arXiv2211.16854MaRDI QIDQ6180640FDOQ6180640

Authors: Marc Hellmuth, G. E. Scholz 

Publication date: 2 January 2024

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

Abstract: The modular decomposition of a graph $G$ is a natural construction to capture key features of $G$ in terms of a labeled tree $(T,t)$ whose vertices are labeled as "series" ($1$), "parallel" ($0$) or "prime". However, full information of $G$ is provided by its modular decomposition tree $(T,t)$ only, if $G$ is a cograph, i.e., $G$ does not contain prime modules. In this case, $(T,t)$ explains $G$, i.e., $x,yinE(G)$ if and only if the lowest common ancestor $mathrm{lca}_T(x,y)$ of $x$ and $y$ has label "$1$". Pseudo-cographs, or, more general, GaTEx graphs $G$ are graphs that can be explained by labeled galled-trees, i.e., labeled networks $(N,t)$ that are obtained from the modular decomposition tree $(T,t)$ of $G$ by replacing the prime vertices in $T$ by simple labeled cycles. GaTEx graphs can be recognized and labeled galled-trees that explain these graphs can be constructed in linear time. In this contribution, we provide a novel characterization of GaTEx graphs in terms of a set $mathfrak{F}_{mathrmGT}$ of 25 forbidden induced subgraphs. This characterization, in turn, allows us to show that GaTEx graphs are closely related to many other well-known graph classes such as $P_4$-sparse and $P_4$-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs, murky graphs as well as interval graphs, Meyniel graphs or very strongly-perfect and brittle graphs. Moreover, we show that every GaTEx graph as twin-width at most 1 and and provide linear-time algorithms to solve several NP-hard problems (clique, coloring, independent set) on GaTEx graphs by utilizing the structure of the underlying galled-trees they explain.

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

zbMATH Keywords

graph classesforbidden subgraphstwin-widthgalled-tree\textsc{GaTEx} graphpseudo-cograph

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Graph Classes: A Survey
• Complement reducible graphs
• Modular decomposition and transitive orientation
• Algorithmic graph theory and perfect graphs
• Title not available (Why is that?)
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Representation of a finite graph by a set of intervals on the real line
• Transitiv orientierbare Graphen
• A Characterization of Comparability Graphs and of Interval Graphs
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Weakly triangulated graphs
• On Comparability and Permutation Graphs
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Title not available (Why is that?)
• A survey of the algorithmic aspects of modular decomposition
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Distance-hereditary comparability graphs
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Indecomposable graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• On a property of the class of n-colorable graphs
• The cluster deletion problem for cographs
• Minimal indecomposable graphs
• Primitivity is hereditary for 2-structures
• Dacey Graphs
• Theory of 2-structures. II: Representation through labeled tree families
• On a conjecture of Meyniel
• Completely separable graphs
• Efficient and practical algorithms for sequential modular decomposition
• Algorithmische Graphentheorie
• P-Components and the Homogeneous Decomposition of Graphs
• Complexity and parameterized algorithms for cograph editing
• Title not available (Why is that?)
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Beyond representing orthology relations by trees
• On brittle graphs
• Orthology relations, symbolic ultrametrics, and cographs
• Approximating modular decomposition is hard
• Title not available (Why is that?)
• A new characterization of HH-free graphs
• Title not available (Why is that?)
• Murky graphs
• On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions
• Best match graphs and reconciliation of gene trees with species trees
• Reconstructing gene trees from Fitch's xenology relation
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
• Twin-width and generalized coloring numbers
• Twin-width. I: Tractable FO model checking
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Twin-width IV: ordered graphs and matrices

Cited In (2)

• Shared ancestry graphs and symbolic arboreal maps
• The weighted total cophenetic index: a novel balance index for phylogenetic networks

This page was built for publication: Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs

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