A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
From MaRDI portal
Publication:260042
DOI10.1016/j.dam.2015.09.019zbMath1332.05108OpenAlexW1865895387MaRDI QIDQ260042
Publication date: 18 March 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.09.019
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex coloring of graphs with few obstructions
- 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 complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
- 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
- Independent domination in finitely defined classes of graphs: polynomial algorithms
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- Boundary graph classes for some maximum induced subgraph problems
- Boundary properties of the satisfiability problems
- NP-hard graph problems and boundary classes of graphs
- List coloring in the absence of two subgraphs
- On the complexity of domination number determination in monogenic classes of graphs
- Independent Set in P5-Free Graphs in Polynomial Time
