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

We study the problem of partitioning the vertex set of a given graph so thateach part induces a graph with components of bounded order; we are alsointerested in restricting these components to be paths. In particular, we say agraph $G$ admits an $({\cal I}, {\cal O}_k)$-partition if its vertex set can bepartitioned into an independent set and a set that induces a graph withcomponents of order at most $k$. We prove that every graph $G$ with$\operatorname{mad}(G)<\frac 52$ admits an $({\cal I}, {\cal O}_3)$-partition.This implies that every planar graph with girth at least $10$ can bepartitioned into an independent set and a set that induces a graph whosecomponents are paths of order at most 3. We also prove that every graph $G$with $\operatorname{mad}(G) < \frac{8k}{3k+1} = \frac{8}{3}\left( 1 -\frac{1}{3k+1} \right)$ admits an $({\cal I}, {\cal O}_k)$-partition. Thisimplies that every planar graph with girth at least $9$ can be partitioned intoan independent set and a set that induces a graph whose components are paths oforder at most 9.

Partitioning sparse graphs into an independent set and a graph with bounded size components