A linear-time recognition algorithm for \(P_{4}\)-reducible graphs

DOI10.1016/0304-3975(95)00016-PzbMath0873.68155OpenAlexW2038893115MaRDI QIDQ673108

Juan-Miguel Gracia

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00016-p

zbMATH Keywords

cographs\(P_ 4\)-reducible graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (12)

On some domination colorings of graphs ⋮ On bipartite graphs with weak density of some subgraphs ⋮ A fast parallel algorithm to recognize P4-sparse graphs ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ Path-bicolorable graphs ⋮ Cross-series-parallel digraphs ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Path-Bicolorable Graphs ⋮ Efficient parallel recognition of cographs ⋮ ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S ⋮ A representation for the modular-pairs of a P4-reducible graph by modular decomposition

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• Dacey Graphs

This page was built for publication: A linear-time recognition algorithm for \(P_{4}\)-reducible graphs