P-Components and the Homogeneous Decomposition of Graphs

DOI10.1137/S0895480191196812zbMath0830.05056OpenAlexW2040514941MaRDI QIDQ4847366

Beverly Jamison, Stephan Olariu

Publication date: 10 October 1995

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480191196812

zbMATH Keywords

graph algorithmsgraph decompositiontree representation\(p\)-connectedness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs, Recognizing well covered graphs of families with special \(P _{4}\)-components, The A4-structure of a graph, Unnamed Item, Unnamed Item, A fast parallel algorithm to recognize P4-sparse graphs, A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs, On the structure of graphs with few \(P_4\)s, Locally identifying coloring of graphs with few P4s, On the \(b\)-coloring of \(P_{4}\)-tidy graphs, Hardness and efficiency on minimizing maximum distances in spanning trees, Partitioning \(P_4\)-tidy graphs into a stable set and a forest, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, A survey of the algorithmic aspects of modular decomposition, Recognition and isomorphism of tree-like \(P_4\)-connected graphs, Maximization coloring problems on graphs with few \(P_4\), Path-bicolorable graphs, On the \(P_4\)-components of graphs, Restricted coloring problems on graphs with few \(P_4\)'s, Graphs with few \(P_4\)'s under the convexity of paths of order three, Peakless functions on graphs, \(2K_2\)-partition of some classes of graphs, Minimal separators in extended \(P_4\)-laden graphs, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Bipartite-perfect graphs, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Edge tree spanners, Triangulating graphs with few \(P_4\)'s, Path-Bicolorable Graphs, Recognizing the \(P_4\)-structure of bipartite graphs, Tree-like \(P_4\)-connected graphs, Operator Decomposition of Graphs and the Reconstruction Conjecture, Distinct edge geodetic decomposition in graphs