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

A path in an edge-colored graph is rainbow if no two edges of it are coloredthe same, and the graph is rainbow-connected if there is a rainbow path betweeneach pair of its vertices. The minimum number of colors needed torainbow-connect a graph $G$ is the rainbow connection number of $G$, denoted by$\text{rc}(G)$.  A simple way to rainbow-connect a graph $G$ is to color the edges of aspanning tree with distinct colors and then re-use any of these colors to colorthe remaining edges of $G$. This proves that $\text{rc}(G) \le |V(G)|-1$. Weask whether there is a stronger connection between tree-like structures andrainbow coloring than that is implied by the above trivial argument. Forinstance, is it possible to find an upper bound of $t(G) -1$ for$\text{rc}(G)$, where $t(G)$ is the number of vertices in the largest inducedtree of $G$? The answer turns out to be negative, as there are counter-examplesthat show that even $c\cdot t(G)$ is not an upper bound for $\text{rc}(G))$ forany given constant $c$.  In this work we show that if we consider the forest number $f(G)$, the numberof vertices in a maximum induced forest of $G$, instead of $t(G)$, thensurprisingly we do get an upper bound. More specifically, we prove that$\text{rc}(G) \leq f(G) + 2$. Our result indicates a stronger connectionbetween rainbow connection and tree-like structures than that was suggested bythe simple spanning tree based upper bound.

Upper Bounding Rainbow Connection Number by Forest Number