Critical hereditary graph classes: a survey
From MaRDI portal
Publication:518125
DOI10.1007/s11590-015-0985-1zbMath1364.90333OpenAlexW2289043657MaRDI 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
computational complexitypolynomial-time algorithmdominating set problemcoloring problemindependent set problemhereditary graph classlist edge-ranking problem
Related Items (7)
The width and integer optimization on simplices with bounded minors of the constraint matrices ⋮ On lattice point counting in \(\varDelta\)-modular polyhedra ⋮ Boundary classes for graph problems involving non-local properties ⋮ Critical properties of bipartite permutation graphs ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ Unnamed Item ⋮ FPT-algorithm for computing the width of a simplex given by a convex hull
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 P5-Free Graphs in Polynomial Time
- Two cases of polynomial-time solvability for the coloring problem
This page was built for publication: Critical hereditary graph classes: a survey
