A tree representation for P_ 4-sparse graphs
\(P_ 4\)- reducible graphs\(P_ 4\)-sparse graphschromatic numbercographsgraph isomorphism problemtree-representation
Trees (05C05) Distance in graphs (05C12) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
A tree-representation for a class \(\Gamma\) of graphs is the association with every graph \(G\in\Gamma\) of a unique rooted tree \(T(G)\), whose leaves are elements of \(G\), and whose internal vertices correspond to certain graph operations. ``If \(T(G)\) can be obtained efficiently ... and if its leaves can be tested efficiently for isomorphism, then the graph isomorphism problem...can be solved efficiently for graphs in \(\Gamma\), since it reduces to tree isomorphism. The class of cographs (complement-reducible graphs or \(P_ 4\)-restricted graphs), generated from the single-vertex graph by complementation and union, consists precisely of all graphs having no chordless path on four vertices (a \(P_ 4\)). This class is contained in the class of \(P_ 4\)- reducible graphs, in which no vertex is contained in more than one \(P_ 4\). Unique tree representations have been obtained for these classes. The class of \(P_ 4\)-reducible graphs is contained in the class of \(P_ 4\)-sparse graphs, in which every set of five vertices induces at most one \(P_ 4\). ``We give several characterizations of \(P_ 4\)-sparse graphs, and show that they can be constructed from single-vertex graphs by a finite sequence of operations. Our characterization implies that the \(P_ 4\)-sparse graphs admit a tree representation unique up to isomorphism. Furthermore, this tree representation can be obtained in polynomial time. ... this tree representation can be used to provide efficient solutions to the four classical graph optimization problems: ... finding the largest number \(\omega(G)\) of pairwise adjacent vertices, ... the largest number \(\alpha(G)\) of pairwise adjacent vertices in the complement, the chromatic number \(\chi(G)\), and the chromatic number of the complement \(\theta(G)=\chi(\overline G)\). Finally, it is shown that the problem of finding a largest induced \(P_ 4\)-free subgraph is provided by a greedy algorithm in polynomial time.
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- A Linear Recognition Algorithm for Cographs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- A new property of critical imperfect graphs and some consequences
- A note on superbrittle graphs
- Complement reducible graphs
- Dacey Graphs
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- scientific article; zbMATH DE number 4206028 (Why is no real title available?)
- scientific article; zbMATH DE number 3920497 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- On a class of posets and the corresponding comparability graphs
- On a property of the class of n-colorable graphs
- Representation of graphs by OBDDs
- The graph sandwich problem for P₄-sparse graphs
- Algorithmic aspects of a general modular decomposition theory
- On the b-coloring of cographs and \(P_{4}\)-sparse graphs
- On a unique tree representation for \(P_ 4\)-extendible graphs
- \(P_ 4\)-trees and substitution decomposition
- Triangulating graphs with few \(P_4\)'s
- A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
- Matroids arisen from matrogenic graphs
- On semi-\(P_ 4\)-sparse graphs
- Scattering number and modular decomposition
- A fast parallel algorithm to recognize P4-sparse graphs
- On extended P₄-reducible and extended P₄-sparse graphs
- On the structure of graphs with few P₄s
- On variations of \(P_{4}\)-sparse graphs
- Stability number of bull- and chair-free graphs revisited
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Tree-like P₄-connected graphs
- Locally identifying coloring of graphs with few P4s
- The convexity of induced paths of order three and applications: complexity aspects
- \(L(2, 1)\)-labelling of graphs with few \(P_4\)'s
- \(2K_2\)-partition of some classes of graphs
- A simple linear time algorithm for cograph recognition
- Hamiltonicity in graphs with few \(P_ 4\)'s
- Isomorphism of chordal (6, 3) graphs
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
- An optimal path cover algorithm for cographs
- The multiple domination and limited packing problems in graphs
- \(N\)-extendible posets, and how to minimize total weighted completion time
- Recognition and isomorphism of tree-like \(P_4\)-connected graphs
- On the \(P_4\)-components of graphs
- Cross-series-parallel digraphs
- 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
- PSPACE-completeness of two graph coloring games
- Hardness and efficiency on minimizing maximum distances in spanning trees
- Faster algorithms for cograph edge modification problems
- Laplacian integrality in \(P_4\)-sparse and \(P_4\)-extendible 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
- Recognizing well covered graphs of families with special \(P _{4}\)-components
- On some domination colorings of graphs
- Fixed-parameter algorithms for the cocoloring problem
- Hardness and inapproximability of convex recoloring problems
- The parametric complexity of graph diameter augmentation
- Maximization coloring problems on graphs with few \(P_4\)
- The clique operator on graphs with few \(P_{4}\)'s
- On the \(b\)-dominating coloring of graphs
- Dot product dimensions of graphs
- Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs
- Spy game: FPT-algorithm, hardness and graph products
- The connected greedy coloring game
- SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
- Minimum sum coloring of \(P_{4}\)-sparse graphs
- An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
- The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
- Inapproximability of the lid-chromatic number
- The P4-sparse Graph Sandwich Problem
- scientific article; zbMATH DE number 4139767 (Why is no real title available?)
- 2K2 vertex-set partition into nonempty parts
- scientific article; zbMATH DE number 4068899 (Why is no real title available?)
- Recognizing P₄ -Sparse Graphs in Linear Time
- A fully dynamic algorithm for the recognition of P₄-sparse graphs
- A survey of the algorithmic aspects of modular decomposition
- 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
- Hierarchical and modularly-minimal vertex colorings
- A_ and L_-spectral properties of spider graphs
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- Intersection of longest paths in graph classes
- Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
- On the isomorphism of graphs with few P4s
- The general position avoidance game and hardness of general position games
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- Directed path graph isomorphism
- Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
- On prime inductive classes of graphs
- A new characterization of P₄-connected graphs
- Perfect Italian domination on some generalizations of cographs
- Recoloring some hereditary graph classes
- Recoloring via modular decomposition
- Complexity and parameterized algorithms for cograph editing
- On z-coloring and \(\mathrm{b}^\ast \)-coloring of graphs as improved variants of the b-coloring
- 2-polarity and algorithmic aspects of polarity variants on cograph superclasses
- Structural characterizations of tree t-spanners for graphs with few P₄'s and (0, )-graphs
- Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
- Graph classes with few P₄'s: universality and Brownian graphon limits
- Improved bounds on proper conflict-free coloring of graphs
- On the minimum sum coloring of P₄-sparse graphs
- Minimal separators in \(P_4\)-sparse graphs
- \(2K_{2}\) vertex-set partition into nonempty parts
This page was built for publication: A tree representation for \(P_ 4\)-sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1183332)