On a unique tree representation for \(P_ 4\)-extendible graphs
From MaRDI portal
Publication:1182318
DOI10.1016/0166-218X(91)90085-BzbMath0754.05051OpenAlexW2065581757MaRDI QIDQ1182318
Publication date: 28 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(91)90085-b
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Structural characterization of families of graphs (05C75) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs, Recognizing well covered graphs of families with special \(P _{4}\)-components, Total dominating sequences in trees, split graphs, and under modular decomposition, Unnamed Item, Clique-perfectness and balancedness of some graph classes, On the structure of graphs with few \(P_4\)s, On the \(b\)-coloring of \(P_{4}\)-tidy graphs, On the isomorphism of graphs with few P4s, Partitioning \(P_4\)-tidy graphs into a stable set and a forest, The multiple domination and limited packing problems in graphs, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Directed path graph isomorphism, Partial characterizations of circle graphs, \(N\)-extendible posets, and how to minimize total weighted completion time, Recognition and isomorphism of tree-like \(P_4\)-connected graphs, Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, On the \(P_4\)-components of graphs, Cross-series-parallel digraphs, \(b\)-coloring of tight graphs, Hitting subgraphs in \(P_4\)-tidy graphs, The clique operator on graphs with few \(P_{4}\)'s, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Representation of graphs by OBDDs, Hamiltonicity in graphs with few \(P_ 4\)'s, On some special classes of contact \(B_0\)-VPG graphs, Triangulating graphs with few \(P_4\)'s, Laplacian integrality in \(P_4\)-sparse and \(P_4\)-extendible graphs, Probe interval and probe unit interval graphs on superclasses of cographs, ON GRAPHS WITH LIMITED NUMBER OF P4-PARTNERS, Tree-like \(P_4\)-connected graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A tree representation for \(P_ 4\)-sparse graphs
- On a property of the class of n-colorable graphs
- Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- A Linear Recognition Algorithm for Cographs
- On the tree representation of chordal graphs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
