English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

An $(r, \ell)$-partition of a graph $G$ is a partition of its vertex set into$r$ independent sets and $\ell$ cliques. A graph is $(r, \ell)$ if it admits an$(r, \ell)$-partition. A graph is well-covered if every maximal independent setis also maximum. A graph is $(r,\ell)$-well-covered if it is both $(r,\ell)$and well-covered. In this paper we consider two different decision problems. Inthe $(r,\ell)$-Well-Covered Graph problem ($(r,\ell)$WCG for short), we aregiven a graph $G$, and the question is whether $G$ is an$(r,\ell)$-well-covered graph. In the Well-Covered $(r,\ell)$-Graph problem(WC$(r,\ell)$G for short), we are given an $(r,\ell)$-graph $G$ together withan $(r,\ell)$-partition of $V(G)$ into $r$ independent sets and $\ell$ cliques,and the question is whether $G$ is well-covered. We classify most of theseproblems into P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only thecases WC$(r,0)$G for $r\geq 3$ remain open. In addition, we consider theparameterized complexity of these problems for several choices of parameters,such as the size $\alpha$ of a maximum independent set of the input graph, itsneighborhood diversity, its clique-width, or the number $\ell$ of cliques in an$(r, \ell)$-partition. In particular, we show that the parameterized problem ofdeciding whether a general graph is well-covered parameterized by $\alpha$ canbe reduced to the WC$(0,\ell)$G problem parameterized by $\ell$. In addition,we prove that both problems are coW[2]-hard but can be solved in XP-time.

On the (parameterized) complexity of recognizing well-covered (r,l)-graphs