A note on the vertex arboricity of signed graphs

Abstract

A signed tree-coloring of a signed graph $(G,\sigma )$ is a vertex coloring $c$ so that $G^c(i,\pm )$ is a forest for every $i\in c(u)$ and $u\in V(G)$, where $G^c(i,\pm )$ is the subgraph of $(G,\sigma )$ whose vertex set is the set of vertices colored by $i$ or $-i$ and edge set is the set of positive edges with two end-vertices colored both by $i$ or both by $-i$, along with the set of negative edges with one end-vertex colored by $i$ and the other colored by $-i$. If $c$ is a function from $V(G)$ to $M_n$, where $M_n$ is $\{\pm 1,\pm 2,\dots ,\pm k\}$ if $n=2k$, and $\{0,\pm 1,\pm 2,\dots ,\pm k\}$ if $n=2k+1$, then $c$ a signed tree-$n$-coloring of $(G,\sigma )$. The minimum integer $n$ such that $(G,\sigma )$ admits a signed tree-$n$-coloring is the signed vertex arboricity of $(G,\sigma )$, denoted by $va(G,\sigma )$. In this paper, we first show that two switching equivalent signed graphs have the same signed vertex arboricity, and then prove that $va(G,\sigma )\le 3$ for every balanced signed triangulation and for every edge-maximal $K_5$-minor-free graph with balanced signature. This generalizes the well-known result that the vertex arboricity of every planar graph is at most 3.

8 pages, 1 figure, will be published in Utilitas Mathematica