Partitions and well-coveredness: the graph sandwich problem
DOI10.1016/J.DISC.2022.113253zbMATH Open1506.05166OpenAlexW4280546337MaRDI QIDQ2111912FDOQ2111912
Authors: Sancrey Rodrigues Alves, F. Couto, Sylvain Gravier, Sulamita Klein, Uéverton S. Souza, Luerbio Faria 
Publication date: 17 January 2023
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2022.113253
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
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)
Cites Work
- A characterization of well covered graphs of girth 5 or greater
- Graph Sandwich Problems
- Some covering concepts in graphs
- The complexity of satisfiability problems
- A generalization of Villarreal's result for unmixed tripartite graphs
- Well-covered claw-free graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Partitions of graphs into one or two independent sets and cliques
- List Partitions
- Very well covered graphs
- Complexity results for well‐covered graphs
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- Title not available (Why is that?)
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- List matrix partitions of chordal graphs
- Title not available (Why is that?)
- Extending Berge's and Favaron's results about well-covered graphs
- Well covered simplicial, chordal, and circular arc graphs
- Well-covered circulant graphs
- Well-covered graphs and extendability
- Partitioning cographs into cliques and stable sets
- The structure of well-covered graphs with no cycles of length 4
- On the well-coveredness of Cartesian products of graphs
- Weighted well-covered claw-free graphs
- On decision and optimization (\(k\),\(l\))-graph sandwich problems
- Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- The well-covered dimension of random graphs
- Strongly well-covered graphs
- On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
- Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
- Unmixed r-partite graphs
- Title not available (Why is that?)
- Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
- Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
- On the probe problem for \((r,\ell )\)-well-coveredness
- Title not available (Why is that?)
Cited In (2)
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)
