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 graph is $(d_1, ..., d_r)$-colorable if its vertex set can be partitionedinto $r$ sets $V_1, ..., V_r$ so that the maximum degree of the graph inducedby $V_i$ is at most $d_i$ for each $i\in \{1, ..., r\}$. For a given pair $(g,d_1)$, the question of determining the minimum $d_2=d_2(g; d_1)$ such thatplanar graphs with girth at least $g$ are $(d_1, d_2)$-colorable has attractedmuch interest. The finiteness of $d_2(g; d_1)$ was known for all cases exceptwhen $(g, d_1)=(5, 1)$. Montassier and Ochem explicitly asked if $d_2(5; 1)$ isfinite. We answer this question in the affirmative with $d_2(5; 1)\leq 10$;namely, we prove that all planar graphs with girth at least $5$ are $(1,10)$-colorable. Moreover, our proof extends to the statement that for anysurface $S$ of Euler genus $\gamma$, there exists a $K=K(\gamma)$ where graphswith girth at least $5$ that are embeddable on $S$ are $(1, K)$-colorable. Onthe other hand, there is no finite $k$ where planar graphs (and thus embeddableon any surface) with girth at least $5$ are $(0, k)$-colorable.

$(1, k)$-coloring of graphs with girth at least $5$ on a surface