arxiv: 2605.02387 · v1 · submitted 2026-05-04 · 💻 cs.DS

Recognition: 3 theorem links

· Lean Theorem

On the power of standard DFS and BFS

Binh-Minh Bui-Xuan, Fabien de Montgolfier, Michel Habib, Renaud Torfs

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:24 UTC · model grok-4.3

classification 💻 cs.DS

keywords graph recognitionDFSBFStrivially perfect graphssplit graphsproper interval graphsvertex orderingspattern avoidance

0 comments

The pith

Standard DFS and BFS traversals recognize and certify trivially perfect, split, and proper interval graphs via pattern-avoiding orderings.

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

The paper establishes that a single depth-first search produces a vertex ordering that both recognizes and certifies trivially perfect graphs, simplifying earlier methods. A single breadth-first search suffices to recognize split graphs and bipartite chain graphs. Two consecutive BFS runs recognize proper interval graphs, improving on prior algorithms that needed three specialized searches. These capabilities rest on characterizations of the classes by vertex orderings that avoid specific forbidden patterns. The work also includes a structural proof that, for connected proper interval graphs, the characterizing orderings are unique up to reversal and swapping of true twins.

Core claim

The central claim is that the vertex orderings generated by ordinary DFS and BFS can be checked directly against pattern-avoidance properties to recognize and certify the listed graph classes. This yields linear-time procedures that use fewer or simpler traversals than previous approaches. For connected proper interval graphs the paper proves that any two orderings satisfying the characterization differ only by reversal or by exchanging true twins.

What carries the argument

Pattern-avoiding vertex orderings produced by standard DFS and BFS traversals

If this is right

Trivially perfect graphs can be recognized and certified by one standard DFS pass.
Split graphs and bipartite chain graphs can be recognized by one standard BFS pass.
Proper interval graphs can be recognized by two consecutive standard BFS passes.
Certifications consist of verifying that the produced ordering avoids the relevant forbidden patterns.
For connected proper interval graphs the characterizing orderings are unique up to reversal and true-twin swaps.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

These results indicate that basic search procedures may suffice for recognition of additional hereditary classes whose definitions rest on ordering characterizations.
The uniqueness property for proper interval graphs could support canonical representations or faster isomorphism checks.
The approach suggests a route toward unifying recognition algorithms across multiple graph classes around ordinary traversals rather than specialized searches.

Load-bearing premise

The vertex orderings produced by standard DFS and BFS traversals match the pattern-avoiding characterizations of these graph classes.

What would settle it

A single counterexample graph that is trivially perfect yet whose DFS ordering contains a forbidden pattern, or a graph whose DFS ordering avoids all forbidden patterns yet is not trivially perfect.

Figures

Figures reproduced from arXiv: 2605.02387 by Binh-Minh Bui-Xuan, Fabien de Montgolfier, Michel Habib, Renaud Torfs.

**Figure 1.** Figure 1: Cocomparability pattern. A graph is a cocomparability graph iff there exists an ordering of its vertices avoiding the cocomparability pattern. By drawing conventions the patterns is ordered from left to right. To satisfy the pattern, a black (resp. dashed) edge means a mandatory edge (resp. non-edge). Otherwise, the pattern is avoided. Search orderings also can be characterized using pattern. We use indee… view at source ↗

**Figure 2.** Figure 2: The forbidden pattern of stars (left) and split graphs (right). It is well-known that a similar approach with maxBFS also leads to a certifying algorithm for the recognition of threshold graphs, see [33], which are a particular case of split graphs. A bipartite chain graph is a 2K2-free bipartite graph, that is a bipartite graph that does not have two independent edges that are not linked by a third edge (… view at source ↗

**Figure 3.** Figure 3: The forbidden patterns of bipartite chain graphs. A particular subclass of bipartite chain graphs is used in graph theory for coloration problems under the name Half-Graphs, see [15] mainly because they contains long chains of inclusion of neighbourhoods. Of course to recognize bipartite chain graph one can test its bipartiteness using a BFS and then check the inclusion of neighbourhoods. This can be don… view at source ↗

**Figure 4.** Figure 4: Example of bipartite chain graphs. And τ = a, b, c, 1, 2, 3 is a minBFS visiting ordering of G, avoiding the patterns of view at source ↗

**Figure 5.** Figure 5: The two forbidden patterns of a trivially perfect ordering. Lemma 1. Let G = (V, E) be a graph. If there exist x, y, z ∈ V such that xy ∈ E, yz ∈ E, xz /∈ E and degree(y) ≤ degree(z), then G has an induced C4 or an induced P4. Proof. Since y has lower degree, the existence of a private neighbor x of y implies the existence of a private neighbor of z, a vertex t ∈ N(z) \ N(y). Then, either xt ∈ E and x, y, … view at source ↗

**Figure 6.** Figure 6: The two forbidden patterns of an interval graph. As a consequence using the 4-points conditions introduced in [9], a total ordering of the vertices avoiding the patterns of view at source ↗

**Figure 7.** Figure 7: K1,3 (also known as Claw), 3−Sun and Net graphs and then noticing that they are K1,3-free graphs. So in section 2, we already process a particular case of Proper Interval graphs. Among the other characterizations of UIG, some can be formalized in terms of total orderings of the vertices. Let us first define these orderings: – The Interval Ordering of a realizer consists in sorting the intervals by leftmost… view at source ↗

**Figure 8.** Figure 8: 3 patterns: chordal, co-chordal and cocomparability one after it. Vertex orderings avoiding the 3 patterns of view at source ↗

**Figure 9.** Figure 9: The 3 types of connected components and their associated Modular Decomposition Tree P-node . . . Q-node Q-node . . . Q-node σ(x1) . . . σ(xk) z1 P-node . . . z2 P-node . . . b1 bp y1 . . . yh a1 P-node ap u1 . . . ul t1 . . . tr view at source ↗

**Figure 10.** Figure 10: The associated PQ-tree. Notice the differences with the Modular Decomposition Tree as for example that σ must be an Left Ordering of the underlying prime graph UIG view at source ↗

read the original abstract

It is well-known since the seventies of last century that Depth First Search (DFS) can be used to compute strongly connected components [RE. Tarjan. SIAM Journal on Computing, 1972] and Breadth First Search (BFS) can be used to compute distance in graphs [GY. Handler. Transportation Science, 1973]. We furthermore demonstrate that these standard graph searches are powerful enough to recognize and certify several well-structured graph classes. Specifically, we provide a single DFS approach for recognizing and certifying trivially perfect graphs that is significantly simpler than previous methods using [FPM. Chu. Information Processing Letters, 2008]. We further show that a single BFS can recognize split graphs and bipartite chain graphs, and we improve upon the triple LexBFS algorithm for proper interval graphs [DG. Corneil. Discrete Applied Mathematics, 2004] by proposing a two consecutive BFS recognition scheme. These results are underpinned by characterizations using vertex orderings that avoid specific patterns [L. Feuilloley, M. Habib. SIAM Journal on Discrete Mathematics, 2021]. Finally, we provide a structural study of connected proper interval graphs, proving that their characterizations via special orderings are unique up to reversal and the permutation of true twins.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Standard DFS and BFS produce usable orderings for recognizing four specific graph classes, with concrete simplifications over prior algorithms.

read the letter

The core point is that ordinary DFS and BFS, without lexicographic ordering, can certify trivially perfect graphs (one DFS), split graphs and bipartite chain graphs (one BFS each), and proper interval graphs (two consecutive BFS runs). These procedures check the output vertex orderings against the pattern-avoidance conditions from Feuilloley-Habib 2021, and the paper supplies explicit algorithms plus correctness arguments that link the search stacks and queues to those ordering properties. A structural uniqueness result for connected proper interval graphs (up to reversal and true-twin permutation) is included as well. This is a genuine simplification on the cited earlier work: Chu's 2008 method for trivially perfect graphs and Corneil's 2004 triple-LexBFS scheme for proper interval graphs. The proofs appear to go through without circularity or unstated cases, and the reductions rest on standard search mechanics rather than new machinery. Within algorithmic graph theory this is useful because it replaces more specialized traversals with the most basic ones while preserving certification power. The scope stays narrow—only these four classes—and the paper does not claim runtime improvements beyond the reduction in search passes or provide implementation benchmarks. That keeps the contribution proportionate: solid for readers who care about recognition procedures for perfect or interval-related graphs, but not a broad methodological shift. The work is for specialists in graph algorithms who already know the 2021 ordering characterizations and want simpler certifying searches. It shows clear engagement with the literature and delivers reproducible algorithms, so it merits a serious referee even if revisions are needed on exposition or edge cases.

Referee Report

0 major / 3 minor

Summary. The paper claims that standard (non-lexicographic) DFS and BFS traversals suffice to recognize and certify trivially perfect graphs (via single DFS), split graphs and bipartite chain graphs (via single BFS), and proper interval graphs (via two consecutive BFS), by producing vertex orderings that directly verify the pattern-avoidance characterizations of Feuilloley-Habib (2021). It also proves that the special orderings for connected proper interval graphs are unique up to reversal and true-twin permutation, and supplies explicit algorithms together with correctness proofs.

Significance. If the derivations hold, the work demonstrates that ordinary DFS and BFS are already powerful enough for recognition and certification of these classes, yielding simpler procedures than the prior single-DFS method of Chu (2008) for trivially perfect graphs and the triple-LexBFS method of Corneil (2004) for proper interval graphs. The explicit algorithms, the direct reduction from search stacks/queues to the required ordering properties, the absence of free parameters or ad-hoc entities, and the structural uniqueness result for proper interval graphs are concrete strengths that strengthen the contribution.

minor comments (3)

[Abstract] The abstract states that the DFS method is 'significantly simpler' than Chu (2008); a brief complexity comparison or operation count in the introduction would make the improvement concrete.
The two-BFS scheme for proper interval graphs is presented as an improvement over the triple-LexBFS algorithm; clarifying whether the two BFS runs are consecutive on the same graph or involve an auxiliary structure would aid readability.
The structural uniqueness theorem for connected proper interval graphs is a useful addition; a short remark on whether the result extends immediately to disconnected graphs would complete the picture.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. The referee's summary accurately captures our main results on the use of standard DFS and BFS for recognition and certification of trivially perfect graphs, split graphs, bipartite chain graphs, and proper interval graphs, as well as the uniqueness result for connected proper interval graphs. We appreciate the recognition of the simplicity of our methods relative to prior work such as Chu (2008) and Corneil (2004).

Circularity Check

0 steps flagged

Minor self-citation of characterization; derivations independent

full rationale

The paper underpins its DFS/BFS recognition schemes on pattern-avoiding vertex orderings from Feuilloley-Habib 2021 (SIAM J. Discrete Math.), which shares an author (Habib) with the present work. This constitutes a minor self-citation. However, the central claims consist of new, explicit algorithms (single DFS for trivially perfect graphs, single BFS for split and bipartite chain graphs, two BFS for proper interval graphs), correctness proofs relating search stacks/queues to the required ordering properties, and an original structural uniqueness result for connected proper interval graphs (up to reversal and true-twin permutation). None of these reduce by construction to the cited characterizations; the prior work supplies external benchmarks, while the derivations here are self-contained and falsifiable via the supplied algorithms and proofs. No fitted parameters, self-definitions, or load-bearing self-citation chains appear.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph traversal properties and prior characterizations without introducing new free parameters or invented entities.

axioms (2)

standard math Standard correctness and ordering properties of DFS and BFS traversals
Invoked throughout as the foundation for the recognition procedures, referencing Tarjan 1972 and Handler 1973.
domain assumption Graph classes admit characterizations by forbidden patterns in linear orderings
Directly used for the recognition claims, citing Feuilloley and Habib 2021.

pith-pipeline@v0.9.0 · 5531 in / 1303 out tokens · 48070 ms · 2026-05-08T18:24:10.997433+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

39 extracted references · 23 canonical work pages · 1 internal anchor

[1]

Beisegel, J., Denkert, C., Köhler, E., Krnc, M., Pivac, N., Scheffler, R., Strehler, M.: The recognition problem of graph search trees. SIAM J. Discret. Math.35(2), 1418–1446 (2021). https://doi.org/10.1137/20M1313301, https://doi.org/10.1137/ 20M1313301

work page doi:10.1137/20m1313301 2021
[2]

Bhaduri, S.: Finding a maximum clique of a chordal graph by removing vertices of minimum degree. Tech. rep., Master Thesis, Kent University USA (2008)

2008
[3]

Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci.13(3), 335–379 (1976). https://doi.org/10.1016/S0022-0000(76)80045-1, https://doi.org/ 10.1016/S0022-0000(76)80045-1

work page doi:10.1016/s0022-0000(76)80045-1 1976
[4]

Charbit, P., Habib, M., Mamcarz, A.: Influence of the tie-break rule on the end- vertex problem. Discret. Math. Theor. Comput. Sci.16(2), 57–72 (2014). https: //doi.org/10.46298/DMTCS.2081, https://doi.org/10.46298/dmtcs.2081

work page doi:10.46298/dmtcs.2081 2014
[5]

Chu, F.P.M.: A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements. Inf. Process. Lett.107(1), 7–12 (2008) 26 Authors Suppressed Due to Excessive Length

2008
[6]

Discrete Applied Mathematics138(3), 371–379 (2004)

Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Applied Mathematics138(3), 371–379 (2004). https://doi.org/10. 1016/j.dam.2003.07.001, http://dx.doi.org/10.1016/j.dam.2003.07.001

work page doi:10.1016/j.dam.2003.07.001 2004
[8]

Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett.55(2), 99–104 (1995). https: //doi.org/10.1016/0020-0190(95)00046-F, https://doi.org/10.1016/0020-0190(95) 00046-F

work page doi:10.1016/0020-0190(95)00046-f 1995
[9]

Corneil, D.G., Krueger, R.: A unified view of graph searching. SIAM J. Discret. Math.22(4), 1259–1276 (2008). https://doi.org/10.1137/050623498, https://doi. org/10.1137/050623498

work page doi:10.1137/050623498 2008
[10]

Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs. SIAM J. Discret. Math.23(4), 1905–1953 (2009). https://doi.org/ 10.1137/S0895480100373455, https://doi.org/10.1137/S0895480100373455

work page doi:10.1137/s0895480100373455 1905
[11]

Cournier, A., Ille, P.: Minimal indecomposable graphs. Discret. Math.183(1-3), 61–80 (1998). https://doi.org/10.1016/S0012-365X(97)00077-0, https://doi.org/ 10.1016/S0012-365X(97)00077-0

work page doi:10.1016/s0012-365x(97)00077-0 1998
[12]

Dissertation, University of Montepllier II (2007)

Crespelle, C.: Représentations dynamiques de graphes. Dissertation, University of Montepllier II (2007)

2007
[13]

Topics in Combinatorics and Graph Theory, R

Damaschke, P.: Forbidden ordered subgraphs. Topics in Combinatorics and Graph Theory, R. Bodendiek and R. Hennm Eds pp. 219–229 (1990)

1990
[14]

and Imai, H

Ducoffe, G., Feuilloley, L., Habib, M., Pitois, F.: Pattern detection in ordered graphs. CoRRabs/2302.11619(2023). https://doi.org/10.48550/ARXIV.2302. 11619, https://doi.org/10.48550/arXiv.2302.11619

work page internal anchor Pith review doi:10.48550/arxiv.2302 2023
[15]

(eds.), Measure Theory Oberwolfach 1983, Lecture Notes in Mathematics, vol

Erdős, P.: Kölzow, D.; Maharam-Stone, D. (eds.), Measure Theory Oberwolfach 1983, Lecture Notes in Mathematics, vol. 1089, Springer (1984)

1983
[16]

SIAM Journal on Discrete Mathematics (SIDMA)35(1), 55–90 (2021)

Feuilloley, L., Habib, M.: Graph classes and forbidden patterns on three vertices. SIAM Journal on Discrete Mathematics (SIDMA)35(1), 55–90 (2021). https:// doi.org/10.1137/19M1280399

work page doi:10.1137/19m1280399 2021
[17]

Information Processing Letters56(3), 179–184 (1995)

de Figueiredo1, C.M., Meidanis, J., de Mello, C.P.: A linear-time algorithm for proper interval graph recognition. Information Processing Letters56(3), 179–184 (1995). https://doi.org/https://doi.org/10.1016/0020-0190(95)00133-W

work page doi:10.1016/0020-0190(95)00133-w 1995
[18]

Fishburn, P.C.: Interval graphs and interval orders. Discret. Math.55(2), 135–149 (1985). https://doi.org/10.1016/0012-365X(85)90042-1, https://doi.org/10.1016/ 0012-365X(85)90042-1

work page doi:10.1016/0012-365x(85)90042-1 1985
[19]

Discrete Mathematics24(1), 105–107 (1978)

Golumbic, M.C.: Trivially perfect graphs. Discrete Mathematics24(1), 105–107 (1978)

1978
[20]

North-Holland Publishing Co., NLD (2004)

Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs (Annals of Dis- crete Mathematics, Vol 57). North-Holland Publishing Co., NLD (2004)

2004
[21]

Pattern Recog- nition153, 110500 (2024).https://doi.org/https://doi.org/10.1016/j

Habib,M.,Limouzy,V.:Onsomesimplicialeliminationschemesforchordalgraphs. Electron. Notes Discrete Math.32, 125–132 (2009). https://doi.org/10.1016/J. ENDM.2009.02.017, https://doi.org/10.1016/j.endm.2009.02.017

work page doi:10.1016/j 2009
[22]

Habib, M., Paul, C., Viennot, L.: Linear time recognition of p4-indifference graphs. Discret. Math. Theor. Comput. Sci.4(2), 173–178 (2001). https://doi.org/10. 46298/DMTCS.269, https://doi.org/10.46298/dmtcs.269

work page doi:10.46298/dmtcs.269 2001
[23]

Trans- portation Science7(3), 287–293 (1973), https://pubsonline.informs.org/doi/abs/ 10.1287/trsc.7.3.287 On the power of standard DFS and BFS 27

Handler, G.Y.: Minimax location of a facility in an undirected tree graph. Trans- portation Science7(3), 287–293 (1973), https://pubsonline.informs.org/doi/abs/ 10.1287/trsc.7.3.287 On the power of standard DFS and BFS 27

work page doi:10.1287/trsc.7.3.287 1973
[24]

Heggernes, P., Kratsch, D.: Linear-time certifying recognition algorithms and for- bidden induced subgraphs. Nord. J. Comput.14(1-2), 87–108 (2007)

2007
[25]

Electronic Notes in Discrete Mathematics32, 27–34 (2009)

Heggernes, P., Meister, D., Papadopoulos, C.: A new representation of proper interval graphs with an application to clique-width. Electronic Notes in Discrete Mathematics32, 27–34 (2009). https://doi.org/https://doi.org/10.1016/j.endm. 2009.02.005, dIMAP Workshop on Algorithmic Graph Theory

work page doi:10.1016/j.endm 2009
[26]

Hell, P., Huang, J.: Certifying LexBFS recognition algorithms for proper in- terval graphs and proper interval bigraphs. SIAM J. Discret. Math.18(3), 554–570 (2004). https://doi.org/10.1137/S0895480103430259, https://doi.org/10. 1137/S0895480103430259

work page doi:10.1137/s0895480103430259 2004
[27]

Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recog- nizing and representing proper interval graphs. SIAM J. Comput.31(1), 289–305 (2001). https://doi.org/10.1137/S0097539700372216, https://doi.org/10. 1137/S0097539700372216

work page doi:10.1137/s0097539700372216 2001
[28]

In: Mayr, E.W

Hsu, W.: A simple test for interval graphs. In: Mayr, E.W. (ed.) Graph- Theoretic Concepts in Computer Science, 18th International Workshop, WG ’92, Wiesbaden-Naurod, Germany, June 19-20, 1992, Proceedings. Lecture Notes in Computer Science, vol. 657, pp. 11–16. Springer (1992). https://doi.org/10.1007/ 3-540-56402-0_31, https://doi.org/10.1007/3-540-56402-0_31

work page doi:10.1007/3-540-56402-0_31 1992
[29]

Discrete Ap- plied Mathematics69(3), 247–255 (1996)

Jing-Ho, Y., Jer-Jeong, C., Chang, G.J.: Quasi-threshold graphs. Discrete Ap- plied Mathematics69(3), 247–255 (1996). https://doi.org/https://doi.org/10. 1016/0166-218X(96)00094-7, https://www.sciencedirect.com/science/article/pii/ 0166218X96000947

1996
[30]

In: Tinhofer, G., Schmidt, G

Korte, N., Möhring, R.H.: A simple linear -time algorithm to recognize interval graphs. In: Tinhofer, G., Schmidt, G. (eds.) Graphtheoretic Concepts in Com- puter Science, International Workshop, WG ’86, Bernried, Germany, June 17- 19, 1986, Proceedings. Lecture Notes in Computer Science, vol. 246, pp. 1–16. Springer (1986). https://doi.org/10.1007/3-540-...

work page doi:10.1007/3-540-17218-1_45 1986
[31]

Dis- cret

Li, P., Wu, Y.: A four-sweep LBFS recognition algorithm for interval graphs. Dis- cret. Math. Theor. Comput. Sci.16(3), 23–50 (2014). https://doi.org/10.46298/ DMTCS.2094, https://doi.org/10.46298/dmtcs.2094

work page doi:10.46298/dmtcs.2094 2014
[32]

Looges, P., Olariu, S.: Optimal greedy algorithm for indifference graphs. Comput. Math. Appl.25, 15–25 (1993)

1993
[33]

Mahadev, N.V., Peled, U.N.: Threshold graphs and related topics, vol. 56. Elsevier (1995)

1995
[34]

In: Beyersdorff, O., Kanté, M.M., Kupferman, O., Lokshtanov, D

Paul, C., Protopapas, E.: Tree-layout based graph classes: Proper chordal graphs. In: Beyersdorff, O., Kanté, M.M., Kupferman, O., Lokshtanov, D. (eds.) 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France. LIPIcs, vol. 289, pp. 55:1– 55:18. Schloss Dagstuhl - Leibniz-Zentrum für ...

work page doi:10.4230/lipics.stacs.2024.55 2024
[35]

in Proof Techniques in Graph Theory (F

Roberts, F.: Indifference graphs. in Proof Techniques in Graph Theory (F. Harary ed.), Academic Press pp. 301–310 (1969)

1969
[36]

Shevrin, L., Filipov, N.: Partially ordered sets and their comparability graphs. Siber. Math. J.11, 497–509 (1970)

1970
[37]

SIAM Journal on Computing13(3), 566–579 (1984)

Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hyper- graphs. SIAM Journal on Computing13(3), 566–579 (1984). https://doi.org/10. 1137/0213035 28 Authors Suppressed Due to Excessive Length

1984
[38]

Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972). https://doi.org/10.1137/0201010, https://doi.org/10.1137/ 0201010

work page doi:10.1137/0201010 1972
[39]

Dissertation, University of Göttingen (1967)

Wegner, G.: Eignenschaften der Nerven Homologisch-einfacher Familien imRn. Dissertation, University of Göttingen (1967)

1967
[40]

Proceedings of the American Math- ematical Society13, 789–795 (1962)

Wolk, E.S.: The comparability graph of a tree. Proceedings of the American Math- ematical Society13, 789–795 (1962)

1962