Graph Classes: A Survey

DOI10.1137/1.9780898719796zbMATH Open0919.05001OpenAlexW1579049696MaRDI QIDQ4243764FDOQ4243764

Authors: Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad 

Publication date: 24 May 1999

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

Recommendations

• Graph theory
• A textbook of graph theory
• Classes of directed graphs
• scientific article; zbMATH DE number 854567

zbMATH Keywords

distanceNP-completenessforbidden subgraphsperfect graphsalgorithmic complexitygraph class

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Structural characterization of families of graphs (05C75) Graph theory (05Cxx)

Cited In (only showing first 100 items - show all)

• Toll convexity
• Toughness in graphs -- a survey
• Representation characterizations of chordal bipartite graphs
• The minimum vulnerability problem on graphs
• Reconfiguration of vertex covers in a graph
• Detecting fixed patterns in chordal graphs in polynomial time
• Pursuing a fast robber on a graph
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• Jump number of two-directional orthogonal ray graphs
• On opposition graphs, coalition graphs, and bipartite permutation graphs
• NP-completeness results for edge modification problems
• Chordal bipartite completion of colored graphs
• On cliques of Helly Circular-arc Graphs
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Complexity of approximating the oriented diameter of chordal graphs
• On algorithms for (\(P_5\), gem)-free graphs
• A unified approach to recognize squares of split graphs
• On the OBDD representation of some graph classes
• New results on word-representable graphs
• Characterization of \(P_{6}\)-free graphs
• Weighted independent sets in a subclass of \(P_6\)-free graphs
• Characterising \((k,\ell )\)-leaf powers
• A new characterization of \(P_{6}\)-free graphs
• Efficient total domination in digraphs
• The stable set polytope for some extensions of \(P_4\)-free graphs
• On containment graphs of paths in a tree
• Star chromatic bounds
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Largest chordal and interval subgraphs faster than \(2^n\)
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• Treewidth computations. I: Upper bounds
• Locally identifying colourings for graphs with given maximum degree
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• A survey of the algorithmic aspects of modular decomposition
• Structure of squares and efficient domination in graph classes
• A note on path domination
• Partial characterizations of circle graphs
• Improved algorithms and complexity results for power domination in graphs
• The 0-1 inverse maximum stable set problem
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Title not available (Why is that?)
• Partition-distance: A problem and class of perfect graphs arising in clustering
• A new LBFS-based algorithm for cocomparability graph recognition
• Characterizing width two for variants of treewidth
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Ferrers dimension of grid intersection graphs
• Characterization and recognition of some opposition and coalition graph classes
• Minimal dominating sets in interval graphs and trees
• On neighborhood-Helly graphs
• Threshold-coloring and unit-cube contact representation of planar graphs
• Thin strip graphs
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• The complexity of clique graph recognition
• Permutation bigraphs and interval containments
• Weighted efficient domination problem on some perfect graphs
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Simplicial Powers of Graphs
• The minimum vulnerability problem on specific graph classes
• Graph modification problem for some classes of graphs
• Weighted efficient domination in two subclasses of \(P_6\)-free graphs
• Perfect edge domination and efficient edge domination in graphs
• The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
• The complexity of dominating set reconfiguration
• Partitioning graphs into complete and empty graphs
• Mixed unit interval graphs
• On distance-3 matchings and induced matchings
• A Gröbner basis characterization for chordal comparability graphs
• Covering planar graphs with forests
• Alternation graphs
• Structure and linear time recognition of 3-leaf powers
• Approximability results for the maximum and minimum maximal induced matching problems
• Rooted directed path graphs are leaf powers
• Interval graph limits
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
• The clique operator on circular-arc graphs
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• Witness (Delaunay) graphs
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Enumeration of minimal dominating sets and variants
• Series parallel digraphs with loops
• Union closed tree convex sets
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Efficient algorithms for the double traveling salesman problem with multiple stacks
• Stability number of bull- and chair-free graphs revisited
• Computing the metric dimension for chain graphs
• On stable cutsets in graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• A matrix characterization of interval and proper interval graphs
• Efficient domination for classes of \(P_6\)-free graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Finitely forcible graphons
• Distance-hereditary comparability graphs
• Computing maximum stable sets for distance-hereditary graphs
• Finding a maximum induced matching in weakly chordal graphs
• Recognition of some perfectly orderable graph classes
• Integral mixed unit interval graphs
• Characterization and recognition of generalized clique-Helly graphs

This page was built for publication: Graph Classes: A Survey

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