P-Components and the Homogeneous Decomposition of Graphs

DOI10.1137/S0895480191196812MaRDI QIDQ4847366zbMATH OpenOpenAlexFDO

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

Cited in

(36)

• scientific article; zbMATH DE number 6963897 (Why is no real title available?)
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• A fast parallel algorithm to recognize P4-sparse graphs
• On the \(P_4\)-components of graphs
• Partitioning \(P_4\)-tidy graphs into a stable set and a forest
• Distinct edge geodetic decomposition in graphs
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
• scientific article; zbMATH DE number 1312888 (Why is no real title available?)
• Locally identifying coloring of graphs with few P4s
• A new characterization of \(P_4\)-connected graphs
• Edge tree spanners
• Recognizing well covered graphs of families with special \(P _{4}\)-components
• Bipartite-perfect graphs
• Peakless functions on graphs
• Recognition and isomorphism of tree-like \(P_4\)-connected graphs
• \(2K_2\)-partition of some classes of graphs
• scientific article; zbMATH DE number 58951 (Why is no real title available?)
• Triangulating graphs with few \(P_4\)'s
• SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
• Recognizing the \(P_4\)-structure of bipartite graphs
• Minimal separators in extended \(P_4\)-laden graphs
• Hardness and efficiency on minimizing maximum distances in spanning trees
• Tree-like \(P_4\)-connected graphs
• The \(A_4\)-structure of a graph
• Path-bicolorable graphs
• Restricted coloring problems on graphs with few \(P_4\)'s
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs
• Operator Decomposition of Graphs and the Reconstruction Conjecture
• A survey of the algorithmic aspects of modular decomposition
• On the \(b\)-coloring of \(P_{4}\)-tidy graphs
• Path-bicolorable graphs. (Extended abstract)
• On the structure of graphs with few \(P_4\)s
• Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
• Maximization coloring problems on graphs with few \(P_4\)

This page was built for publication: P-Components and the Homogeneous Decomposition of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4847366)