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

(39)

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

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)