Graph Classes: A Survey (Q4243764)

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.