P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs

DOI10.1002/sapm198981179zbMath0699.05054OpenAlexW22831093MaRDI QIDQ3476849

No author found.

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1002/sapm198981179

zbMATH Keywords

computational complexitycographstree representation

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Related Items (max. 100)

Minimal separators in \(P_4\)-sparse graphs ⋮ Recognizing well covered graphs of families with special \(P _{4}\)-components ⋮ Isomorphism of chordal (6, 3) graphs ⋮ Linear time optimization algorithms for \(P_ 4\)-sparse graphs ⋮ An optimal path cover algorithm for cographs ⋮ Unnamed Item ⋮ Total dominating sequences in trees, split graphs, and under modular decomposition ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ On bipartite graphs with weak density of some subgraphs ⋮ A fast parallel algorithm to recognize P4-sparse graphs ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ 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 ⋮ Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Spiders can be recognized by counting their legs ⋮ Classes of perfect graphs ⋮ \(N\)-extendible posets, and how to minimize total weighted completion time ⋮ Recognition and isomorphism of tree-like \(P_4\)-connected graphs ⋮ Path-bicolorable graphs ⋮ On the \(P_4\)-components of graphs ⋮ On a unique tree representation for \(P_ 4\)-extendible graphs ⋮ A tree representation for \(P_ 4\)-sparse graphs ⋮ Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs ⋮ A linear-time recognition algorithm for \(P_{4}\)-reducible graphs ⋮ \(b\)-coloring of tight graphs ⋮ A simple linear time algorithm for cograph recognition ⋮ Linear-time modular decomposition of directed graphs ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ The clique operator on graphs with few \(P_{4}\)'s ⋮ The perfection and recognition of bull-reducible Berge graphs ⋮ Representation of graphs by OBDDs ⋮ Hamiltonicity in graphs with few \(P_ 4\)'s ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Path-Bicolorable Graphs ⋮ Laplacian integrality in \(P_4\)-sparse and \(P_4\)-extendible graphs ⋮ ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S ⋮ Tree-like \(P_4\)-connected graphs ⋮ Bull-Reducible Berge Graphs are Perfect ⋮ A representation for the modular-pairs of a P4-reducible graph by modular decomposition

Cites Work

• Unnamed Item
• Complement reducible graphs
• On a class of posets and the corresponding comparability graphs
• On a property of the class of n-colorable graphs
• A Linear Recognition Algorithm for Cographs
• Dacey Graphs

This page was built for publication: P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs