Partitions and well-coveredness: the graph sandwich problem
DOI10.1016/j.disc.2022.113253zbMath1506.05166OpenAlexW4280546337MaRDI QIDQ2111912
Sylvain Gravier, Uéverton S. Souza, Fernanda Couto, Sulamita Klein, Sancrey Rodrigues Alves, Luérbio 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
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) 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 (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A generalization of Villarreal's result for unmixed tripartite graphs
- Extending Berge's and Favaron's results about well-covered graphs
- Weighted well-covered claw-free graphs
- Well-covered circulant graphs
- List matrix partitions of chordal graphs
- The well-covered dimension of random graphs
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- On the well-coveredness of Cartesian products of graphs
- A characterization of well covered graphs of girth 5 or greater
- Well-covered graphs and extendability
- Strongly well-covered graphs
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Very well covered graphs
- On decision and optimization (\(k\),\(l\))-graph sandwich problems
- Partitions of graphs into one or two independent sets and cliques
- Well-covered claw-free graphs
- Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
- On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
- Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
- Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
- Partitioning cographs into cliques and stable sets
- The structure of well-covered graphs with no cycles of length 4
- On the probe problem for \((r,\ell )\)-well-coveredness
- Complexity results for well‐covered graphs
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- List Partitions
- Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs
- Unmixed r-partite graphs
- Graph Sandwich Problems
- Well covered simplicial, chordal, and circular arc graphs
- The complexity of satisfiability problems
- Some covering concepts in graphs
This page was built for publication: Partitions and well-coveredness: the graph sandwich problem
