Critical hereditary graph classes: a survey

DOI10.1007/s11590-015-0985-1zbMath1364.90333MaRDI QIDQ518125

Panos M. Pardalos, Dmitriy S. Malyshev

Publication date: 28 March 2017

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-015-0985-1

zbMATH Keywords

computational complexity; polynomial-time algorithm; dominating set problem; coloring problem; independent set problem; hereditary graph class; list edge-ranking problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

Related Items

Unnamed Item, Critical properties of bipartite permutation graphs, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, The width and integer optimization on simplices with bounded minors of the constraint matrices, On lattice point counting in \(\varDelta\)-modular polyhedra, FPT-algorithm for computing the width of a simplex given by a convex hull, Boundary classes for graph problems involving non-local properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex coloring of graphs with few obstructions
• Boundary properties of well-quasi-ordered sets of graphs
• The coloring problem for classes with two small obstructions
• Boundary properties of graphs for algorithmic graph problems
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• The strong perfect graph theorem
• The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
• Computing independent sets in graphs with large girth
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• 4-coloring \(H\)-free graphs when \(H\) is small
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Boundary classes of graphs for the dominating set problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the maximum independent set problem in subclasses of subcubic graphs
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Boundary properties of the satisfiability problems
• NP-hard graph problems and boundary classes of graphs
• Edge ranking of weighted trees
• List coloring in the absence of two subgraphs
• A Dichotomy for Upper Domination in Monogenic Classes
• Towards an Isomorphism Dichotomy for Hereditary Graph Classes
• The Maximum Independent Set Problem in Planar Graphs
• The NP-Completeness of Edge-Coloring
• On the complexity of domination number determination in monogenic classes of graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• The Traveling Salesman Problem with Distances One and Two
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Boundary Properties of Factorial Classes of Graphs
• A study of the boundary graph classes for colorability problems
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Classes of graphs critical for the edge list-ranking problem
• Independent Set in P₅-Free Graphs in Polynomial Time
• Two cases of polynomial-time solvability for the coloring problem