scientific article; zbMATH DE number 15355
[For the entire collection see Zbl 0698.00017.] It has turned out that almost all natural decision problems on graphs are NP-complete. So it was an obvious question whether the structural properties of special graph classes help to design efficient algorithms when the problems are restricted to these classes. This paper gives a uniform description (so-called FOSG-characterizations) of such well-known graph classes which are usually defined by very different principles (intersection graphs, graphs related to posets, partitions of the vertex set, chordality properties, forbidden subgraphs, etc.).
- Distances in cocomparability graphs and their powers
- Forbidden induced partial orders
- Proper and unit bitolerance orders and graphs
- Forbidden subgraph decomposition
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- Maximum induced matching algorithms via vertex ordering characterizations
- Describing hereditary properties by forbidden circular orderings
- Oriented expressions of graph properties
- On grounded -graphs and their relatives
- On characterizations by nice forbidding sets
- The complexity of minor-ancestral graph properties with forbidden pairs
- scientific article; zbMATH DE number 4101231 (Why is no real title available?)
- Circularly compatible ones, D-circularity, and proper circular-arc bigraphs
- Interval-like graphs and digraphs
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Min-orderable digraphs
- Strict chordal and strict split digraphs
- Graph classes and forbidden patterns on three vertices
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Recognizing interval bigraphs by forbidden patterns
- On the kernel and related problems in interval digraphs
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
- Forbidden tournaments and the orientation completion problem
- Tree-layout based graph classes: proper chordal graphs
- Forbidden patterns in temporal graphs resulting from encounters in a corridor
- Interval k-graphs : recognition and forbidden obstructions
- Word-representable co-bipartite graphs: representation number, speed, and entropy
- Recognizing graphs without asteroidal triples
- On forbidden subdivision characterizations of graph classes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3971999)
