Representing distance-hereditary graphs with multi-rooted trees

Guillaume E. Scholz

REVIEW 3 major objections 3 minor 37 references

Representing distance-hereditary graphs with multi-rooted trees

T0 review · 3 major / 3 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The undirected graphs explainable by a labelled multi-rooted tree are precisely the distance-hereditary graphs.

desk verdict New characterization of distance-hereditary graphs as arboreal-explainable: solid, clean, with a minor unproved tree fact and a typo, easily fixed. read the letter →

arxiv 2502.08251 v1 pith:5YIYGSVG submitted 2025-02-12 math.CO

Guillaume E. Scholz This is my paper · ORCID

classification math.CO MSC 05C0505C2005C62

keywords arborealnetworksdistance-hereditarygraphsmulti-rootedtreescographsleastcommonancestorgraphrepresentationPtolemaicGATEX

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the undirected graphs explainable by a labelled arboreal network — a tree-like directed graph with possibly several roots and 0/1 labels on its branching vertices — are exactly the distance-hereditary graphs. This generalizes the classical correspondence between cographs and labelled rooted trees, where the root is unique. The forward direction is constructive: given any distance-hereditary graph, Algorithm 1 builds a binary labelled arboreal network that explains it. The reverse direction shows that no other graph admits such an explanation. If correct, the result gives a single tree-like representation for an entire well-studied graph class.

What carries the argument

The central object is the labelled arboreal network (N,t): a directed acyclic graph whose underlying undirected graph is a tree, allowing multiple roots, where t labels every vertex of outdegree at least two by 0 or 1. The argument is carried by the unique least common ancestor lemma for arboreal networks: leaves sharing an ancestor have a well-defined lca, so adjacency in the explained graph is determined by the label of that lca. For the constructive direction, Algorithm 1 turns the standard recursive generation of distance-hereditary graphs by pendant-vertex, false-twin, and true-twin operations into network-building steps that subdivide incoming arcs.

What would settle it

Enumerate all trees with five or more leaves and no degree-2 vertices, and check whether every such tree contains a vertex adjacent to at least two leaves and at most one non-leaf vertex; exhibiting one without such a vertex would falsify the unproved structural step on which the converse of Theorem 4 rests. Alternatively, run Algorithm 1 on every distance-hereditary graph up to a given size and verify that the returned labelled arboreal network explains the input graph, and check that no non-distance-hereditary graph is explained by any small arboreal network.

Watch

Extended reading notes

Core claim

Theorem 4 establishes an exact characterization: an undirected graph G is arboreal-explainable if and only if G is distance-hereditary. Here an arboreal network is a connected directed acyclic graph whose underlying undirected graph is a tree, with no vertex of both indegree and outdegree one, and a labelling assigns each branching vertex a 0 or 1; the network explains G when two distinct leaves are adjacent exactly when they share an ancestor and the label of their unique least common ancestor is 1. The paper further shows that every distance-hereditary graph with at least two vertices can be built, from any sequence of one-vertex extensions, into a binary labelled arboreal network (Algorithm 1), and it characterizes which graphs need exactly two roots (Theorem 7).

Load-bearing premise

The converse of Theorem 4 relies on an unproved structural fact: after suppressing degree-2 vertices, the underlying tree of an arboreal network with at least five leaves has some vertex adjacent to at least two leaves and to at most one non-leaf vertex; if this fact failed, the induction removing leaves one at a time would break.

Editorial extensions

If this is right

Every distance-hereditary graph admits a binary labelled arboreal network of the same leaf set, so the tree-like representation is available for the whole class, not just cographs.
The one-root case recovers exactly the cographs; the constant-label-1 case recovers the connected Ptolemaic graphs, so distance-hereditary graphs interpolate between these two classical families.
Algorithm 1 constructs the network from any sequence of one-vertex extensions in time proportional to finding that sequence, giving an explicit representation for every distance-hereditary graph.
Corollary 1 restates the characterization in forbidden-subgraph form: arboreal-explainable graphs are exactly the hole-free graphs with no induced house, gem, or domino.
Theorem 7 pins down the two-root case: a non-cograph is explainable with exactly two roots precisely when it is a distance-hereditary GATEX graph with exactly one non-cograph connected component.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because cograph algorithms often run on the labelled tree rather than on the graph itself, the same two-layer approach may now be tried on distance-hereditary graphs using arboreal networks, potentially turning NP-hard problems into polynomial ones for a much larger class.
The unproved tree lemma in the converse is standard and likely true; making it explicit would make the induction fully self-contained.
In evolutionary orthology inference, where a graph of paralog/ortholog relations may fail to be a cograph, multi-rooted networks offer a representation that relaxes the single-root assumption while staying within a tree-like structure.
The Ptolemaic supergraph characterization of Section 6 could serve as a tool for studying minimum chordal completions of distance-hereditary graphs, connecting to the open question the paper states.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Clean result, mostly airtight. The paper proves that distance-hereditary graphs are exactly the graphs explainable by labelled arboreal networks, and gives a construction (Algorithm 1) that turns a one-vertex-extension sequence into a binary arboreal network. That's a genuine new characterization, not just a reformulation: cographs as labelled rooted trees and Ptolemaic graphs as shared-ancestry graphs were known, but nobody had put distance-hereditary graphs in this particular spot.

The proof is careful. The forward direction is an induction on the extension sequence, with the network operations matching the three extension operations. The converse is a leaf-peeling induction on the reduced underlying tree. The one soft spot is an unproved tree fact in the converse: the claim that the reduced tree has a vertex adjacent to at least two leaves and at most one non-leaf. It's stated without proof, and it's load-bearing for the case analysis. The stress-test note is right that it's true—a longest path argument does it—but it should be stated as a lemma and proved. There's also a typo in subcase c3: 't(lca_N(y,z))' should be 't(lca_N(x,z))'. Both are minor editorial issues, not mathematical gaps.

Sections 6 and 7 extend the story: Section 6 characterizes which Ptolemaic supergraphs are realizable, using the symbolic-map machinery from [27]; Section 7 gives a forbidden-subgraph characterization for two-root networks via GATEX graphs. These are secondary but useful, and they tie the result into the existing literature cleanly. The paper relies heavily on [27] for symbolic maps and for the Ptolemaic characterization; since [27] is published and the results are directly relevant, that's legitimate.

No data, no code, but the algorithm is specified in pseudocode and the proof is constructive. The writing is dense but clear. If I were refereeing, I'd ask for the tree lemma to be made explicit and for the typo fixed, and then I'd be happy to accept. Worth sending to a serious referee.

Referee Report

3 major / 3 minor

Summary. The paper introduces arboreal networks, a generalization of rooted phylogenetic trees in which several roots are allowed, and studies undirected graphs that can be represented by such networks with a {0,1}-labelling of the branching vertices. The main result, Theorem 4, states that a graph is arboreal-explainable if and only if it is distance-hereditary. The forward direction is proved constructively by Algorithm 1, which converts a sequence of one-vertex extensions of a distance-hereditary graph into a labelled arboreal network. The converse is proved by induction on the number of leaves, using a reduction of the underlying tree and a case analysis on a suitably chosen vertex. The paper also contains a characterization of pairs (G,G*) consisting of a graph and a Ptolemaic supergraph realizable by the same arboreal network (Theorem 6), and a characterization of graphs explainable by a two-rooted arboreal network (Theorem 7).

Significance. If the main theorem is taken together with the standard cograph/rooted-tree correspondence, it gives a clean analogue for distance-hereditary graphs: the class of graphs explainable by labelled arboreal networks is exactly a well-studied hereditary graph class. The proof is constructive in one direction and the algorithm uses the known linear-time construction of one-vertex extension sequences. The additional theorems on Ptolemaic supergraphs and two-rooted networks are nontrivial and make the paper more than a single equivalence. The result is likely to be of interest to researchers working on graph representations and phylogenetic networks.

major comments (3)

[Section 3 and Theorem 4] As stated, the main equivalence is false for the single-vertex graph. Under the definition of a network in Section 3, every indegree-0 vertex must have outdegree at least 2 and every leaf must have indegree 1, so no arboreal network can have exactly one leaf. The single-vertex graph is distance-hereditary but not arboreal-explainable, and Algorithm 1 explicitly assumes |X| >= 2. Please either add an explicit degenerate-case exception (for example, allowing a one-vertex network, or treating the single-vertex graph vacuously) or state Theorem 4 and related results for graphs with at least two vertices.
[Theorem 4, converse proof] The induction in the converse direction relies on the assertion that after suppressing degree-2 vertices, the reduced tree N contains a vertex v that is adjacent to at least two leaves and to at most one non-leaf vertex. This fact is stated without proof or citation, and it is load-bearing because the subsequent case analysis (a)-(c) requires such a vertex. The statement is true and can be proved by taking a longest leaf-to-leaf path and examining the neighbour of an endpoint, but it should be stated and proved as a lemma before being used.
[Theorem 4, case (c3)] In the subcase t(v)=0, the proof reads "t(lca_N(y,z)) = t(v) = 0". This is incorrect as written, since lca_N(y,z)=r and t(r)=1. The argument needs the statement "t(lca_N(x,z)) = t(v) = 0", which together with t(lca_N(y,z))=1 justifies the conclusion that x is pendant to y. Please correct this typo, as the current wording makes the inference in that subcase invalid.

minor comments (3)

[Throughout] There are numerous typographical errors, including "unidrected" in Section 1, "aboreal" in the output line of Algorithm 1, "charactarize" in Section 1, and "manucript" in the Acknowledgements. A careful proofreading pass is needed.
[Section 3, definition of binary network] The text says "if N is binary, V*(N) ∩ H(N) =/ 0", but by the immediately preceding definition every vertex in V*(N) has indegree 0 or 1 and every vertex in H(N) has outdegree 1, so the intersection should be empty. Please replace this with the intended statement.
[Lemma 7(ii)] In the proof, the notation "lca(y,z)" is used instead of "lca_N(y,z)" in one place. This is cosmetic but should be made uniform for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is proved from the definitions and external characterizations; the same-author citations to [27] are independent prior theorems supporting auxiliary results, not the main equivalence.

full rationale

The paper's central claim, Theorem 4, is not circular. Arboreal-explainability is defined independently in Section 3 via labelled arboreal networks (N,t) and the graph C(N,t), while distance-hereditariness is defined in Section 2 via the standard induced-subgraph and one-vertex-extension characterizations quoted from [2] and [15]. The forward direction of Theorem 4 is established by Algorithm 1 and Proposition 3: the algorithm takes a one-vertex-extension sequence of a distance-hereditary graph as input and constructs a labelled arboreal network by subdividing arcs and adding new vertices; the correctness proof verifies that edge membership in G is exactly captured by t(lca_N(x,y)), so the conclusion is not assumed as an input. The converse direction of Theorem 4 is an induction on |X|: it removes a leaf via Lemma 9, applies the induction hypothesis to a smaller arboreal-explainable graph, and identifies the removed vertex as a pendant, false-twin, or true-twin extension in cases (a), (b), and (c). None of these steps invoke Theorem 4 or the distance-hereditary characterization as a premise. The structural assertion in the converse proof that the reduced tree has a vertex adjacent to at least two leaves and at most one non-leaf is stated without proof; this is a presentation/correctness gap that can be repaired by a standard longest-path argument, and it is not an equation-level reduction of the theorem to itself. The cited results from the author's own [27]—Theorem 1 on Ptolemaic shared-ancestry graphs, Theorem 5 on symbolic arboreal maps, and Lemma 4 on unique least common ancestors—are independent prior theorems with stated assumptions and proofs; they support auxiliary statements such as Observations 2–3, Proposition 2, and Theorem 6, but they are not the source of the main equivalence. There is no fitted parameter renamed as a prediction and no ansatz smuggled in via citation. The only blemishes are the unproved tree fact and a typographical slip in subcase c3, both of which concern correctness presentation rather than circularity. Hence the derivation is self-contained with respect to the claimed main result.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper is a pure combinatorial proof; no parameters are fitted to data. The central equivalence relies on published characterizations of distance-hereditary graphs (forbidden subgraphs and one-vertex extensions) and on prior results about arboreal networks and symbolic maps, including work by the same author. These external theorems are cited and not machine-checked here, but they concern shared ancestry graphs and Ptolemaic graphs, not the main equivalence, so they do not make the argument circular. No new entities are introduced; 'arboreal-explainable graph' is only a name for a class already defined by labelled arboreal networks.

assumptions (6)

standard math A graph is distance-hereditary iff it has no induced hole, house, gem, or domino (Hammer and Maffray [15]).
Used in Section 2 and in Corollary 1 to translate the new class into forbidden-subgraph language; the theorem is proved in the cited literature.
standard math A graph is distance-hereditary iff it can be built from a single vertex by repeatedly adding a pendant vertex, a false twin, or a true twin (Bandelt and Mulder [2]).
This recursive characterization is the input taxonomy for Algorithm 1 and Proposition 3; it is not proved in this paper.
domain assumption In an arboreal network, any two leaves sharing an ancestor have a unique least common ancestor (Lemma 4 from Huber, Moulton and Scholz [27]).
Imported from prior work; without it the definition of C(N,t) would be ambiguous.
domain assumption A symbolic map is representable by a labelled arboreal network iff it satisfies conditions A1-A4 (Theorem 5 from [27]).
Used in the proof of Theorem 6 to characterize realizable Ptolemaic completions; this is a substantial external characterization.
standard math A connected graph is Ptolemaic iff it is chordal and distance-hereditary, and connected Ptolemaic graphs are exactly shared-ancestry graphs of arboreal networks (Howorka [25] and Theorem 1 from [27]).
Used in Observation 3 and Section 6 to identify A(N) as a connected Ptolemaic supergraph of G.
domain assumption GATEX graphs are characterized by the 25 forbidden induced subgraphs of Hellmuth and Scholz [20].
Used in the proof of Theorem 7 to pass from distance-hereditary plus GATEX to forbidden-subgraph conditions; source is a cited preprint by the author and coauthor.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Representing distance-hereditary graphs with multi-rooted trees." pith.science (2026). https://pith.science/paper/5YIYGSVG

@misc{pith2026250208251,
  author       = {Pith},
  title        = {Pith review of: Representing distance-hereditary graphs with multi-rooted trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5YIYGSVG}},
  note         = {Machine review of arXiv:2502.08251}
}

read the original abstract

Arboreal networks are a generalization of rooted trees, defined by keeping the tree-like structure, but dropping the requirement for a single root. Just as the class of cographs is precisely the class of undirected graphs that can be explained by a labelled rooted tree (T,t), we show that the class of distance-hereditary graphs is precisely the class of undirected graphs that can be explained by a labelled arboreal network (N,t).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 36 canonical work pages

[27]

SIAM journal on Discrete Mathe- matics 38(4), 2553–2577 (2024)

Huber, K.T., Moulton, V ., Scholz, G.E.: Shared ancestry graphs and symbolic arboreal maps. SIAM journal on Discrete Mathe- matics 38(4), 2553–2577 (2024)

work page 2024
[1]

PLoS Comput Biol

Altenhoff, A.M., Dessimoz, C.: Phylogenetic and functional assessment of orthologs inference projects and methods. PLoS Comput Biol. 5, e1000262 (2009)

work page 2009
[2]

Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. J. Combin. Theory Ser. B 41, 182–208 (1986)

work page 1986
[3]

Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)

Brandst ¨adt, A., Le, V .B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)

work page 1999
[4]

Discrete Applied Math- ematics 310, 1–9 (2022)

Bruckmann, C., Stadler, P., Hellmuth, M.: From modular decomposition trees to rooted median graphs. Discrete Applied Math- ematics 310, 1–9 (2022)

work page 2022
[5]

Corneil, D.G., Lerchs, H., Stewart Burlingham, L.K.: Complement reducible graphs. Discr. Appl. Math. 3, 163–174 (1981)

work page 1981
[6]

SIAM Journal on Computing14(4), 926–934 (1985)

Corneil, D.G., Perl, Y ., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM Journal on Computing14(4), 926–934 (1985)

work page 1985
[7]

WG 2021: Graph- Theoretic Concepts in Computer Science pp

Crespelle, C., Gras, B., Perez, A.: Completion to chordal distance-hereditary graphs: a quartic vertex-kernel. WG 2021: Graph- Theoretic Concepts in Computer Science pp. 156–168 (2021)

work page 2021

Show all 37 references

[8]

Damiand, G., Habib, M., Paul, C.: A simple paradigm for graph recognition: Application to cographs and distance-hereditary graphs. Theoret. Comput. Sci. 263, 99–111 (2001)

2001
[9]

Discrete Applied Mathematics 160(18), 2669–2680 (2012)

Di Stefano, G.: Distance-hereditary comparability graphs. Discrete Applied Mathematics 160(18), 2669–2680 (2012). V Latin American Algorithms, Graphs, and Optimization Symposium — Gramado, Brazil, 2009

2012
[10]

Journal of Bioinformatics and Computational Biology 10(4), 1250004.1–1250004.23 (2012)

Gambette, P., Berry, V ., Paul, C.: Quartets and unrooted phylogenetic networks. Journal of Bioinformatics and Computational Biology 10(4), 1250004.1–1250004.23 (2012)

2012
[11]

Journal of mathematical biology 74(7), 1729–1751 (2017)

Gambette, P., Huber, K., Kelk, S.: On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters. Journal of mathematical biology 74(7), 1729–1751 (2017)

2017
[12]

Discrete Mathematics 313(23), 2763–2771 (2013)

Gao, Y ., Hare, D.R., Nastos, J.: The cluster deletion problem for cographs. Discrete Mathematics 313(23), 2763–2771 (2013)

2013
[13]

Discrete Applied Mathematics 160(6), 708–733 (2012)

Gioan, E., Paul, C.: Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs. Discrete Applied Mathematics 160(6), 708–733 (2012)

2012
[14]

CSB ’03: Proceedings of the IEEE Computer Society Conference on Bioinformatics pp

Gusfield, D., Eddhu, S., Langley, C.: Efficient reconstruction of phylogenetic networks with constrained recombination. CSB ’03: Proceedings of the IEEE Computer Society Conference on Bioinformatics pp. 363–374 (2003)

2003
[15]

Discrete Applied Mathematics 27(1), 85–99 (1990)

Hammer, P.L., F.Maffray: Completely separable graphs. Discrete Applied Mathematics 27(1), 85–99 (1990)

1990
[16]

Hellmuth, M., Hernandez-Rosales, M., Huber, K.T., Moulton, V ., Stadler, P.F., Wieseke, N.: Orthology relations, symbolic ultra- metrics, and cographs. J. Math. Biology 66(1-2), 399–420 (2013)

2013
[17]

Theory in Biosciences (2023)

Hellmuth, M., Schaller, D., Stadler, P.F.: Clustering systems of phylogenetic networks. Theory in Biosciences (2023). DOI 10.1007/s12064-023-00398-w

2023 doi
[18]

Discrete Applied Mathematics 321, 179–219 (2022)

Hellmuth, M., Scholz, G.E.: From modular decomposition trees to level-1 networks: Pseudo-cographs, polar-cats and prime polar-cats. Discrete Applied Mathematics 321, 179–219 (2022)

2022
[19]

ArXiv:2306.04367

Hellmuth, M., Scholz, G.E.: Linear time algorithms for NP-hard problems restricted to GaTEx graphs (2023). ArXiv:2306.04367

2023 arXiv
[20]

ArXiv:2211.16854

Hellmuth, M., Scholz, G.E.: Resolving prime modules: The structure of pseudo-cographs and galled-tree explainable graphs (2023). ArXiv:2211.16854

2023 arXiv
[21]

Evolu- tionary Biology: Convergent Evolution, Evolution of Complex Traits, Concepts and Methods pp

Hellmuth, M., Wieseke, N.: From sequence data including orthologs, paralogs, and xenologs to gene and species trees. Evolu- tionary Biology: Convergent Evolution, Evolution of Complex Traits, Concepts and Methods pp. 373–392 (2016)

2016
[22]

Proceedings of the National Academy of Sciences 112(7), 2058–2063 (2015)

Hellmuth, M., Wieseke, N., Lechner, M., Lenhof, H.P., Middendorf, M., Stadler, P.F.: Phylogenomics with paralogs. Proceedings of the National Academy of Sciences 112(7), 2058–2063 (2015)

2015
[23]

BMC Bioinformatics 13(Suppl 19), S6 (2012)

Hernandez-Rosales, M., Hellmuth, M., Wieseke, N., Huber, K.T., Moulton, V ., Stadler, P.F.: From event-labeled gene trees to species trees. BMC Bioinformatics 13(Suppl 19), S6 (2012)

2012
[24]

Howorka, E.: A characterization of distance-hereditary graphs. Quart. J. Math. Oxford, Ser. 2(28), 417–420 (1977)

1977
[25]

Howorka, E.: A characterization of ptolemaic graphs. J. Graph Theory 5, 323–321 (1981)

1981
[26]

Bulletin of Mathematical Biology 84(10), 119 (2022)

Huber, K.T., Moulton, V ., Scholz, G.E.: Forest-based networks. Bulletin of Mathematical Biology 84(10), 119 (2022)

2022
[28]

Algorithmica 80(1), 73–103 (2018)

Huber, K.T., Scholz, G.E.: Beyond representing orthology relations by trees. Algorithmica 80(1), 73–103 (2018)

2018
[29]

Kay, D.C., Chartrand, G.: A characterization of certain ptolemaic graphs. Canad. J. Math. 17, 342–346 (1965)

1965
[30]

Algorithms for Molecular Biology 11(1), 1 (2016)

Lafond, M., Dondi, R., El-Mabrouk, N.: The link between orthology relations and gene trees: a correction perspective. Algorithms for Molecular Biology 11(1), 1 (2016)

2016
[31]

BMC Genomics 15(6), S12 (2014)

Lafond, M., El-Mabrouk, N.: Orthology and paralogy constraints: satisfiability and consistency. BMC Genomics 15(6), S12 (2014)

2014
[32]

International Workshop on Algo- rithms in Bioinformatics pp

Lafond, M., El-Mabrouk, N.: Orthology relation and gene tree correction: complexity results. International Workshop on Algo- rithms in Bioinformatics pp. 66–79 (2015)

2015
[33]

Rossello, F., Valiente, G.: All that glisters is not galled. Math. Bioisci. 221(1), 54–59 (1965)

1965
[34]

Systematic Biology 68(5), 717–729 (2019)

Scholz, G.E., Popescu, A.A., Taylor, M.I., Moulton, V ., Huber, K.T.: OSF-Builder: A new tool for constructing and representing evolutionary histories involving introgression. Systematic Biology 68(5), 717–729 (2019)

2019
[35]

Journal of Combinatorial Theory, Series B 16(2), 191–193 (1974)

Seinsche, D.: On a property of the class of n-colorable graphs. Journal of Combinatorial Theory, Series B 16(2), 191–193 (1974)

1974
[36]

Journal of the Australian Mathematical Society 18(4), 492–502 (1974)

Sumner, D.P.: Dacey graphs. Journal of the Australian Mathematical Society 18(4), 492–502 (1974)

1974
[37]

Discrete Applied Mathematics157(7), 1533–1543 (2009)

Uehara, R., Uno, Y .: Laminar structure of ptolemaic graphs with applications. Discrete Applied Mathematics157(7), 1533–1543 (2009)

2009

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [27]

SIAM journal on Discrete Mathe- matics 38(4), 2553–2577 (2024)

Huber, K.T., Moulton, V ., Scholz, G.E.: Shared ancestry graphs and symbolic arboreal maps. SIAM journal on Discrete Mathe- matics 38(4), 2553–2577 (2024)

work page 2024

[2] [1]

PLoS Comput Biol

Altenhoff, A.M., Dessimoz, C.: Phylogenetic and functional assessment of orthologs inference projects and methods. PLoS Comput Biol. 5, e1000262 (2009)

work page 2009

[3] [2]

Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. J. Combin. Theory Ser. B 41, 182–208 (1986)

work page 1986

[4] [3]

Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)

Brandst ¨adt, A., Le, V .B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)

work page 1999

[5] [4]

Discrete Applied Math- ematics 310, 1–9 (2022)

Bruckmann, C., Stadler, P., Hellmuth, M.: From modular decomposition trees to rooted median graphs. Discrete Applied Math- ematics 310, 1–9 (2022)

work page 2022

[6] [5]

Corneil, D.G., Lerchs, H., Stewart Burlingham, L.K.: Complement reducible graphs. Discr. Appl. Math. 3, 163–174 (1981)

work page 1981

[7] [6]

SIAM Journal on Computing14(4), 926–934 (1985)

Corneil, D.G., Perl, Y ., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM Journal on Computing14(4), 926–934 (1985)

work page 1985

[8] [7]

WG 2021: Graph- Theoretic Concepts in Computer Science pp

Crespelle, C., Gras, B., Perez, A.: Completion to chordal distance-hereditary graphs: a quartic vertex-kernel. WG 2021: Graph- Theoretic Concepts in Computer Science pp. 156–168 (2021)

work page 2021