Chromatic number of signed graphs with bounded maximum degree

MaRDI QIDQ6272050zbMATH OpenFDO

Authors Sandip Das, Soumen Nandi, Soumyajit Paul, Sagnik Sen

Publication date 31 March 2016

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,Sigm{a}^{\prime })$ by re-signing some vertices of $(G,Sigma)$, then $(G,Sigma)equiv(G,Sigm{a}^{\prime })$. A signed graphs $(G,Sigma)$ admits an homomorphism to $(H,Lambda)$ if there is a sign preserving vertex mapping from $(G,Sigm{a}^{\prime })$ to $(H,Lambda)$ for some $(G,Sigma)equiv(G,Sigm{a}^{\prime })$. The signed chromatic number $ch{i}_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 $mathcalF$ of signed graphs $ch{i}_s(mathcalF)=ext{max}_{(G,Sigma)inmathcalF}ch{i}_s((G,Sigma))$. We prove $2^{Delta/2-1}leqch{i}_s(mathcal{G}_{Delta})leq(Delta-1{)}^2.2^{(Delta-1)}+2$ for all $Deltageq3$ where $mathcal{G}_{Delta}$ is the family of connected signed graphs with maximum degree $Delta$. end{abstract}

This page was built for publication: Chromatic number of signed graphs with bounded maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6272050)