Chromatic number of signed graphs with bounded maximum degree

Abstract

A signed graph $(G,\Sigma )$ is a graph positive and negative ($\Sigma$ denotes the set of negative edges). To re-sign a vertex $v$ of a signed graph $(G,\Sigma )$ is to switch the signs of the edges incident to $v$. If one can obtain $(G,{\Sigma }^{\prime })$ by re-signing some vertices of $(G,\Sigma )$, then $(G,\Sigma )\equiv (G,{\Sigma }^{\prime })$. A signed graphs $(G,\Sigma )$ admits an homomorphism to $(H,\Lambda )$ if there is a sign preserving vertex mapping from $(G,{\Sigma }^{\prime })$ to $(H,\Lambda )$ for some $(G,\Sigma )\equiv (G,{\Sigma }^{\prime })$. The signed chromatic number ${\chi }_s((G,\Sigma ))$ of the signed graph $(G,\Sigma )$ is the minimum order (number of vertices) of a signed graph $(H,\Lambda )$ such that $(G,\Sigma )$ admits a homomorphism to $(H,\Lambda )$. For a family $\mathcal{F}$ of signed graphs ${\chi }_s(\mathcal{F})={\text{max}}_{(G,\Sigma )\in \mathcal{F}}{\chi }_s((G,\Sigma ))$. We prove $2^{\Delta /2-1}\le {\chi }_s({\mathcal{G}}_{\Delta })\le (\Delta -1{)}^2.2^{(\Delta -1)}+2$ for all $\Delta \ge 3$ where ${\mathcal{G}}_{\Delta }$ is the family of connected signed graphs with maximum degree $\Delta$. \end{abstract}