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 a new problem for cubic graphs: bipartization of a cubic graph $Q$by deleting sufficiently large independent set $I$. It can be expressed asfollows: \emph{Given a connected $n$-vertex tripartite cubic graph $Q=(V,E)$with independence number $\alpha(Q)$, does $Q$ contain an independent set $I$of size $k$ such that $Q-I$ is bipartite?} We are interested for which value of$k$ the answer to this question is affirmative. We prove constructively that if$\alpha(Q) \geq 4n/10$, then the answer is positive for each $k$ fulfilling$\lfloor (n-\alpha(Q))/2 \rfloor \leq k \leq \alpha(Q)$. It remains an openquestion if a similar construction is possible for cubic graphs with$\alpha(Q)<4n/10$.  Next, we show that this problem with $\alpha(Q)\geq 4n/10$ and $k$ fulfillinginequalities $\lfloor n/3 \rfloor \leq k \leq \alpha(Q)$ can be related tosemi-equitable graph 3-coloring, where one color class is of size $k$, and thesubgraph induced by the remaining vertices is equitably 2-colored. This meansthat $Q$ has a coloring of type $(k, \lceil(n-k)/2\rceil, \lfloor (n-k)/2\rfloor)$.

On bipartization of cubic graphs by removal of an independent set