Graph Classes: A Survey
In the past years, hundreds of graph classes have been invented and studied, both with respect to their structural properties as to their algorithmic complexity. In this book, many important graph classes are reviewed and discussed, with respect to these properties. The book discusses over 200 graph classes, their relations (which graph class is properly contained in which graph class), and key theorems. Both structural results are given (e.g., equivalent characterization of a graph property) and algorithmic behaviour is discussed, e.g., what is the complexity of deciding if a given graph belongs to the class, or polynomial time solvability or NP-completeness of important problems restricted to the class. The material is organized with respect to types of properties: there are fourteen chapters on subjects like perfect graphs (and generalizations and related concepts), forbidden subgraphs, distance properties, and more. Theorems are given without a proof, but with a reference to the literature where the result can be found. There are 1098 references. In this way, the book provides an encyclopedic overview of very many results that are important for researchers on graph classes, and is very useful as a work of reference for those working in the field.
- A clique-difference encoding scheme for labelled \(k\)-path graphs
- Closest 4-leaf power is fixed-parameter tractable
- Efficient algorithms for Roman domination on some classes of graphs
- Mutual exclusion scheduling with interval graphs or related classes. I
- Disjoint paths in symmetric digraphs
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- Cover-incomparability graphs of posets
- Laplacian spectrum of weakly quasi-threshold graphs
- Universal augmentation schemes for network navigability
- The complexity of clique graph recognition
- Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two
- Cage-amalgamation graphs, a common generalization of chordal and median graphs
- On a property of minimal triangulations
- Cubicity of threshold graphs
- Finding Hamiltonian cycles in \(\{\)quasi-claw, \(K_{1,5},K_{1,5} + e\}\)-free graphs with bounded Dilworth numbers
- Localized and compact data-structure for comparability graphs
- Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
- The graph sandwich problem for P₄-sparse graphs
- On star and caterpillar arboricity
- Cube intersection concepts in median graphs
- A witness version of the cops and robber game
- Algorithmic aspects of a general modular decomposition theory
- Dynamically maintaining split graphs
- Labeling bipartite permutation graphs with a condition at distance two
- Treelike comparability graphs
- The clique-separator graph for chordal graphs
- Integration of topological measures for eliminating non-specific interactions in protein interaction networks
- Laminar structure of ptolemaic graphs with applications
- The NLC-width and clique-width for powers of graphs of bounded tree-width
- Some optimization problems on weak-bisplit graphs
- Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
- Simplicial powers of graphs
- A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
- Tree-length equals branch-length
- Ordered interval routing schemes
- Bandwidth of bipartite permutation graphs in polynomial time
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Brambles and independent packings in chordal graphs
- Steiner intervals, geodesic intervals, and betweenness
- On 3-Steiner simplicial orderings
- Partitioning graphs into complete and empty graphs
- Weighted efficient domination problem on some perfect graphs
- Efficient minus and signed domination in graphs
- On the \(k\)-path partition of graphs.
- On universally easy classes for NP-complete problems.
- On linear and circular structure of (claw, net)-free graphs
- On variations of \(P_{4}\)-sparse graphs
- Subgraph trees in graph theory
- Stability number of bull- and chair-free graphs revisited
- The complexity of the locally connected spanning tree problem
- Maximum independent set and maximum clique algorithms for overlap graphs
- An approach to solving \(A^{k}=J-I\)
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Induced matchings in asteroidal triple-free graphs
- Distance labeling scheme and split decomposition
- Algorithms for graphs with small octopus
- A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- On simplicial and co-simplicial vertices in graphs.
- Recognizing quasi-triangulated graphs.
- On stable cutsets in graphs
- Parallel and serial hypercoherences
- Partition-distance: A problem and class of perfect graphs arising in clustering
- Perfect edge domination and efficient edge domination in graphs
- Triangle-free graphs and forbidden subgraphs
- On claw-free asteroidal triple-free graphs
- Computing a clique tree with the algorithm maximal label search
- Strict chordal digraphs viewed as graphs with distinguished edges
- The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
- On maximum common subgraph problems in series-parallel graphs
- Enumeration and maximum number of minimal connected vertex covers in graphs
- The k-hop connected dominating set problem: approximation and hardness
- On the dominating induced matching problem: spectral results and sharp bounds
- Combinatorial problems on \(H\)-graphs
- Polynomial time algorithms for variants of graph matching on partial k-trees
- Requiring that minimal separators induce complete multipartite subgraphs
- Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
- On computing a minimum secure dominating set in block graphs
- Computational aspects of greedy partitioning of graphs
- Colouring of (P₃ P₂)-free graphs
- Star coloring of certain graph classes
- Total coloring of rooted path graphs
- Graphs vertex-partitionable into strong cliques
- Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
- Fully dynamic representations of interval graphs
- Counting minimal transversals of -acyclic hypergraphs
- Strongly unichord-free graphs
- Counting independent sets in cocomparability graphs
- Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Tractabilities and intractabilities on geometric intersection graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- List matrix partitions of graphs representing geometric configurations
- Cost and accuracy aware scientific workflow retrieval based on distance measure
- Convex and isometric domination of (weak) dominating pair graphs
- Progress on the description of identifying code polyhedra for some families of split graphs
- Recent results on containment graphs of paths in a tree
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)