Partitions and well-coveredness: the graph sandwich problem
From MaRDI portal
(Redirected from Publication:2111912)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
- Covering the complete graph by partitions
- On \((k,\ell )\)-graph sandwich problems
- NP-completeness of some problems of partitioning and covering in graphs
- The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
- Algorithms and complexity of sandwich problems in graphs (extended abstract)
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- scientific article; zbMATH DE number 1953085
- scientific article; zbMATH DE number 3908486
- An overview of graph covering and partitioning
Cites work
- scientific article; zbMATH DE number 434906 (Why is no real title available?)
- scientific article; zbMATH DE number 3873377 (Why is no real title available?)
- scientific article; zbMATH DE number 4202288 (Why is no real title available?)
- scientific article; zbMATH DE number 5348111 (Why is no real title available?)
- scientific article; zbMATH DE number 3614795 (Why is no real title available?)
- scientific article; zbMATH DE number 6987353 (Why is no real title available?)
- A characterization of well covered graphs of girth 5 or greater
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- A generalization of Villarreal's result for unmixed tripartite graphs
- Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
- Complexity results for well‐covered graphs
- Extending Berge's and Favaron's results about well-covered graphs
- FPT algorithms to recognize well covered graphs
- Graph Sandwich Problems
- Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
- List Partitions
- List matrix partitions of chordal graphs
- On decision and optimization (\(k\),\(l\))-graph sandwich problems
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
- On the probe problem for \((r,\ell )\)-well-coveredness
- On the well-coveredness of Cartesian products of graphs
- Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
- Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
- Partitioning cographs into cliques and stable sets
- Partitions of graphs into one or two independent sets and cliques
- Some covering concepts in graphs
- Strongly well-covered graphs
- The complexity of satisfiability problems
- The structure of well-covered graphs with no cycles of length 4
- The well-covered dimension of random graphs
- Unmixed r-partite graphs
- Very well covered graphs
- Weighted well-covered claw-free graphs
- Well covered simplicial, chordal, and circular arc graphs
- Well-covered circulant graphs
- Well-covered claw-free graphs
- Well-covered graphs and extendability
Cited in
(4)
This page was built for publication: Partitions and well-coveredness: the graph sandwich problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111912)
