A tree representation for \(P_ 4\)-sparse graphs

DOI10.1016/0166-218X(92)90036-AzbMath0763.05092OpenAlexW2087405099MaRDI QIDQ1183332

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90036-a

zbMATH Keywords

chromatic number cographs graph isomorphism problem \(P_ 4\)- reducible graphs \(P_ 4\)-sparse graphs tree-representation

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (75)

Minimal separators in \(P_4\)-sparse graphs ⋮ The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs ⋮ An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs ⋮ PSPACE-hardness of two graph coloring games ⋮ 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 ⋮ Isomorphism of chordal (6, 3) graphs ⋮ Hierarchical and modularly-minimal vertex colorings ⋮ Dot product dimensions of graphs ⋮ Linear time optimization algorithms for \(P_ 4\)-sparse graphs ⋮ Inapproximability of the lid-chromatic number ⋮ Matroids arisen from matrogenic graphs ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Scattering number and modular decomposition ⋮ An optimal path cover algorithm for cographs ⋮ Unnamed Item ⋮ On some domination colorings of graphs ⋮ Unnamed Item ⋮ Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs ⋮ A fast parallel algorithm to recognize P4-sparse graphs ⋮ PSPACE-completeness of two graph coloring games ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ On the structure of graphs with few \(P_4\)s ⋮ Locally identifying coloring of graphs with few P4s ⋮ 2K2 vertex-set partition into nonempty parts ⋮ On the isomorphism of graphs with few P4s ⋮ The general position avoidance game and hardness of general position games ⋮ Hardness and efficiency on minimizing maximum distances in spanning trees ⋮ Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques ⋮ On variations of \(P_{4}\)-sparse graphs ⋮ The multiple domination and limited packing problems in graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Directed path graph isomorphism ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ Stability number of bull- and chair-free graphs revisited ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ The connected greedy coloring game ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ On prime inductive classes of graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ \(N\)-extendible posets, and how to minimize total weighted completion time ⋮ Recognition and isomorphism of tree-like \(P_4\)-connected graphs ⋮ Hardness and inapproximability of convex recoloring problems ⋮ The parametric complexity of graph diameter augmentation ⋮ Maximization coloring problems on graphs with few \(P_4\) ⋮ On a unique tree representation for \(P_ 4\)-extendible graphs ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ Cross-series-parallel digraphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ \(L(2, 1)\)-labelling of graphs with few \(P_4\)'s ⋮ Intersection of longest paths in graph classes ⋮ Complexity and parameterized algorithms for cograph editing ⋮ \(2K_2\)-partition of some classes of graphs ⋮ \(2K_{2}\) vertex-set partition into nonempty parts ⋮ A simple linear time algorithm for cograph recognition ⋮ The clique operator on graphs with few \(P_{4}\)'s ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Representation of graphs by OBDDs ⋮ On the minimum sum coloring of \(P_4\)-sparse graphs ⋮ Hamiltonicity in graphs with few \(P_ 4\)'s ⋮ Faster algorithms for cograph edge modification problems ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Minimum Sum Coloring of P4-sparse graphs ⋮ Laplacian integrality in \(P_4\)-sparse and \(P_4\)-extendible graphs ⋮ On the b-coloring of cographs and \(P_{4}\)-sparse graphs ⋮ Tree-like \(P_4\)-connected graphs ⋮ On the \(b\)-dominating coloring of graphs ⋮ A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs ⋮ A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs ⋮ The P4-sparse Graph Sandwich Problem ⋮ Aα and Lα-spectral properties of spider graphs

Cites Work

This page was built for publication: A tree representation for \(P_ 4\)-sparse graphs