% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.14}{23(1)}{2016} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf The chromatic number of a signed graph} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Edita M\'a\v cajov\'a\\ \small Department of Computer Science\\[-0.8ex] \small Comenius University\\[-0.8ex] \small Mlynsk\'a dolina, 842 48 Bratislava, Slovakia\\ \small\tt macajova@dcs.fmph.uniba.sk\\ \and Andr\'e Raspaud\\ \small LaBRI\\[-0.8ex] \small Universit\'e de Bordeaux\\[-0.8ex] \small 33405 Talence Cedex, France\\ \small\tt raspud@labri.fr\\ \and Martin \v Skoviera\\ \small Department of Computer Science\\[-0.8ex] \small Comenius University\\[-0.8ex] \small Mlynsk\'a dolina, 842 48 Bratislava, Slovakia\\ \small\tt skoviera@dcs.fmph.uniba.sk } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Dec 24, 2014}{Jan 11, 2016}{Jan 22, 2016}\\ \small Mathematics Subject Classifications: 05C15, 05C22} \begin{document} \maketitle \begin{abstract} In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $\phi\colon V(G)\to \mathbb{Z}$ such that for any two adjacent vertices $u$ and $v$ the colour $\phi(u)$ is different from the colour $\sigma(uv)\phi(v)$, where is $\sigma(uv)$ is the sign of the edge $uv$. The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks' theorem to signed graphs. % keywords are optional % \bigskip\noindent \textbf{Keywords:} graph reconstruction % conjecture; Broglington manifold; Pipletti's classification \end{abstract} \section{Introduction} This paper continues the study of vertex colourings of signed graphs initiated by Zaslavsky in three seminal papers \cite{Zas-coloring, Zas-invariants, Zas-colorful} from early 1980's. A signed graph is a graph in which each edge is labelled with $+1$ or $-1$. The idea of how to colour such a graph is fairly straightforward: (1) use signed colours so as to enable vertex-switching, and (2) do so in such a way that the usual rule to colour adjacent vertices with different colours is respected as long as the edge that joins them is positive. The following definition, taken from \cite{Zas-coloring}, incorporates this idea: Given a signed graph $G$, a \emph{proper vertex colouring} of~$G$, or simply a \textit{colouring}, is a mapping $\phi\colon V(G)\to\mathbb{Z}$ such that for each edge $e=uv$ of $G$ the colour $\phi(u)$ is distinct from the colour $\sigma(e)\phi(v)$, where $\sigma(e)$ denotes the sign of~$e$. In other words, the colours of vertices joined by a positive edge must not coincide while those joined by a negative edge must not be opposite. This definition is natural for several reasons extensively discussed in \cite{Zas-coloring, Zas-invariants, Zas-colorful}. In particular, colourings defined in this manner are well behaved under switching. Recall that \textit{switching} of a signed graph at a vertex $v$ reverses the sign of each non-loop edge incident with $v$. The switching operation does not essentially change the signed graph, because it preserves the sign product on each circuit. If we switch a properly coloured signed graph at some vertex, the colouring has to be switched together with the signature, that is to say, the colour at the vertex must be replaced with its negative. It is easy to see that the result of a vertex switching is again a proper colouring. Furthermore, a colouring of a \textit{balanced} signed graph, one where the sign product on each simple circuit is positive, exactly corresponds to the usual vertex colouring of the underlying unsigned graph. Our paper focuses on measuring the complexity of a signed graph colouring by means of a chromatic number. One possible approach to introducing the chromatic number of a signed graphs was proposed by Zaslavsky in \cite[p.~218]{Zas-coloring} where a \textit{signed colouring} of a signed graph $G$ \textit{in $k$ colours}, or \textit{in $2k+1$ signed colours}, is defined to be a mapping $V(G)\to \{-k, -(k-1), \ldots, 0. \ldots, k-1, k\}$; a colouring is \textit{zero-free} if it never assumes the value $0$. The necessity of treating zero-free colourings separately derives from a different behaviour of switching with respect to vertices coloured zero. This led Zaslavsky \cite[p.~219]{Zas-coloring} to define the \textit{chromatic polynomial} $\chi_G(\lambda)$ of a signed graph $G$ to be the function defined for odd positive arguments $\lambda=2k+1$ whose value equals the number of proper signed colourings of $G$ in $k$ colours. The \textit{balanced chromatic polynomial} $\chi_G^{\mathrm{b}}(\lambda)$, defined for even positive arguments $\lambda =2k$, is the function which counts the zero-free proper signed colourings in $k$ colours. Finally, the \textit{chromatic number} $\gamma (G)$ of $G$, according to Zaslavsky \cite[p.~290]{Zas-invariants}, is the smallest nonnegative integer $k$ for which $\chi_G(2k+1)>0$, and the \textit{strict chromatic number} $\gamma^*(G)$ of $G$ is the smallest nonnegative integer $k$ such that $\chi_G^{\mathrm{b}}(2k)>0$. The disadvantage of Zaslavsky's definitions is that neither of these two varieties of chromatic number is a direct extension of the usual chromatic number of an unsigned graph. This is because, roughly speaking, the chromatic numbers $\gamma$ and $\gamma^*$ only count the absolute values of colours. However, it seems natural to require a signed version of any graph invariant to agree with its original unsigned version on balanced signed graphs. We therefore diverge from the definitions adopted by Zaslavsky in \cite{Zas-coloring, Zas-invariants, Zas-colorful} and propose the following. First, we define, for each $n\ge 1$, a set $M_n\subseteq\mathbb{Z}$ by setting $M_n=\{\pm1, \pm2,\ldots, \pm k\}$ if $n=2k$, and $M_n=\{0,\pm1, \pm2,\ldots, \pm k\}$ if $n=2k+1$. A proper colouring of a signed graph $G$ that uses colours from $M_n$ will be called an \textit{$n$-colouring}. Thus, an $n$-colouring of a signed graph uses at most $n$ distinct colours. Note that if $G$ admits an $n$-colouring, then it also admits an $m$-colouring for each $m\ge n$. The smallest $n$ such that $G$ admits an $n$-colouring will be called the \textit{chromatic number} of $G$ and will be denoted by $\chi(G)$. It is easy to see that the chromatic number of a balanced signed graph coincides with the chromatic number of its underlying unsigned graph. Moreover, $$\chi(G)=\gamma(G)+\gamma^*(G).$$ The aim of this paper is to prove several basic results concerning the chromatic number of a signed graph. Our results are divided into three sections. In Section~\ref{sec:basic} we investigate relationships between the chromatic number of a signed graph and various graph invariants. Among other things, we present bounds on the chromatic number of a signed graph by means of the chromatic number, the acyclic chromatic number, and the arboricity of the underlying unsigned graph. Our main result is a Brooks-type theorem for signed graphs, which will be proved in Section~\ref{sec:Brooks}. The theorem states that the chromatic number of every simple signed graph $G$ is bounded by $\Delta(G)$, the maximum degree of $G$, unless $G$ is a balanced complete graph, a balanced odd circuit, or an unbalanced even circuit. Finally, in Section~\ref{sec:planar}, we deal with the chromatic number of planar signed graphs. We prove that the chromatic number of every simple signed planar graph is at most $5$ and make a conjecture that this bound can be improved to $4$. \section{Basic properties of signed chromatic number} \label{sec:basic} We assume that the reader is familiar with the basic concepts of signed graph theory such as balance, switching, switching equivalence, etc. For more information about signed graphs we refer the reader to \cite{Zas-signed} or to \cite{Zas-coloring, Zas-invariants, Zas-colorful}. Recall that a colouring of a signed graph $G$ is a function $\phi\colon V(G)\to\mathbb{Z}$ such that for each edge $e=uv$ of $G$ the colour $\phi(u)$ is distinct from the colour $\sigma(e)\phi(v)$, where $\sigma(e)$ is the sign of~$e$. It follows that in order for $G$ to admit a proper colouring, $G$ cannot have a positive loop. Throughout the rest of this paper we therefore forbid positive loops in all our signed graphs. Negative loops and parallel edges are not excluded, nevertheless, a negative loop at a vertex $v$ forbids $\phi(v)=0$, and a pair of differently signed parallel edges between vertices $u$ and $v$ forbids $|\phi(u)|=|\phi(v)|$. In general, colour $0$ has a different behaviour from other colours because $-0=0$. Somewhat surprisingly, however, colourings of simple signed graphs behave in a very much similar way as colourings of unsigned graphs. Before proceeding further we would like to remark that throughout the paper the following argument will be used without mention: if a signed graph resulting from a series of switchings is $n$-colourable, then so is the original signed graph. We start our investigation by comparing the chromatic number of a signed graph to the chromatic number of its underlying graph. In order to make a clear distinction between a signed graph and its underlying graph, we will use $\underline{G}$ to denote the underlying graph of a signed graph $G$. \begin{theorem} For every loopless signed graph $G$ we have $$\chi(G)\le 2\chi(\underline{G})-1.$$ Furthermore, this bound is sharp. \end{theorem} \begin{proof} Every colouring of $\underline{G}$ with colours in the set $\{0, 1,\ldots, n-1\}$ is also a signed colouring of $G$ irrespectively of the signature. For $n=\chi(\underline{G})$ we get a signed colouring of $G$ with $2\chi(\underline{G})-1$ colours from the set $\{0,\pm 1, \ldots, \pm (n-1)\}=M_{2n-1}$, implying the required inequality. For the second part, we display an infinite sequence $(G_n)_{n\ge 1}$ of signed graphs such that $\chi(G)= 2\chi(\underline{G})-1$. To construct $G_n$, we take one all-positive copy $H_1$ of $K_n$ and $n-1$ all-negative copies $H_2, H_3, \ldots, H_n$ of $K_n$. For $1\le i\le n$ we denote the vertices of $H_i$ by $v_{i,1},v_{i,2},\ldots,v_{i,n}$ and call any two vertices $v_{i,k}$ and $v_{j,k}$ from different subgraphs $H_i$ and $H_j$ \emph{corresponding}. To finish the construction, we insert a positive edge between any pair of non-corresponding vertices from different copies of $K_n$. Observe that the assignment $\phi(v_{i,j})=j$ for each $i,j\in\{1,2,\ldots, n\}$ defines a proper colouring of $\underline{G_n}$. This colouring is optimal since $\underline{G_n}$ contains a copy of~$K_n$. Hence $\chi(\underline{G_n})=n$, and by the first part of the proof, $\chi(G_n)\le 2n-1$. We now show that the chromatic number of $G_n$ is $2n-1$. Assume, to the contrary, that $G_n$ has a colouring with colours from the set $M_{2n-2}$. Since $H_1$ is a balanced complete graph on $n$ vertices, $n$ different colours $c_1, c_2, \ldots, c_n$ have to be used for the vertices of $H_1$. We may assume that the vertex $v_{1,i}$ has colour~$c_i$. Let $D=\{d_1,d_2,\ldots,d_{n-2}\}$ be the set of all remaining colours, so that $M_{2n-2}=\{c_1,c_2,\ldots,c_n,\penalty0 d_1,d_2,\ldots,d_{n-2}\}$. There are $n$ vertices in each $H_i$ with $i\ge 2$ but only $n-1$ distinct absolute values in $M_{2n-2}$, so there must be two vertices in each such $H_i$ that receive colours with the same absolute value. Since the edges within each $H_i$ with $i\ge 2$ are all negative, such a pair of vertices must receive the same colour. Further, any vertex $v_{i,j}$ of $H_i$ with $i\ge 2$ receives a colour from the set $\{c_j\}\cup D$. It follows that the repeated colour in each $H_i$ is contained in $D$. If a colour $d\in D$ is repeated in some $H_i$, then it does not occur at all in any other subgraph $H_j$ with $j\ge 2$: indeed, a vertex $v$ in $H_j$ with colour $d$ would be joined to at least one of the vertices coloured $d$ in $H_i$ by a positive edge, which is impossible. Thus each $H_i$ with $i\ge 2$ has a different repeated colour from $D$. However, there are $n-1$ all-negative subgraphs $H_i$ in $G_n$ while there are only $n-2$ elements in $D$, proving that a colouring of $G_n$ with colours from $M_{2n-2}$ is not feasible. \end{proof} A signed graph is \textit{antibalanced} if the sign product on every even circuit is $+1$ and the sign product on every odd circuit is $-1$. The signature of an antibalanced signed graph is easily seen to be switching equivalent to the all-negative signature. Furthermore, it is well known \cite{Harary} that a signed graph is antibalanced if and only if its vertex set can be partitioned into two sets (either of which may be empty) such that each edge between the sets is positive and each edge within a set is negative. A balanced antibalanced signed graph is necessarily bipartite, so antibalanced signed graphs are a natural generalisation of bipartite graphs. The next result is an obvious extension of the familiar characterisation of bipartite graphs. \begin{proposition}\label{prop:antibal} A signed graph is $2$-colourable (that is, $\chi(G)\le2$) if and only if it is antibalanced. \end{proposition} \begin{proof} Let $G$ be a signed graph. If $G$ is antibalanced, we can switch the signature of $G$ to make it all-negative and assign $1$ to all the vertices. This produces a $2$-colouring of $G$, so $\chi(G)\le2$. For the converse assume that $G$ admits a $2$-colouring. The colour classes form a partition into sets $V_1$ and $V_{-1}$ which has the property that each edge within the sets is negative and each edge between the sets is positive. By the result of \cite{Harary} mentioned above, $G$ is antibalanced. \end{proof} A graph $H$ is called \textit{$k$-degenerate} if every subgraph of $H$ has a vertex of degree at most~$k$. It is well known and easy to see that a graph is $k$-degenerate if and only if there is an ordering $v_1, v_2,\ldots, v_n$ of its vertices such that for every $1 \Delta-2$. This is only possible when $\deg_{G_j}(v)=\Delta-1$, $s=2$, and $v$ is incident with a bridge $vw$. Let $G_v$ and $G_w$ be the components of $G-vw$ containing $v$ and~$w$, respectively. Clearly, each of $G_v$ and $G_w$ has a $\Delta$-colouring. If one of the bridge-ends, say $w$, had a non-zero colour, we could easily permute the colours within $G_w$ and then combine the colourings of $G_v$ and $G_w$ into a $\Delta$-colouring of the entire $G$. Thus for every $\Delta$-colouring $\phi$ of $G_v$ and every $\Delta$-colouring $\psi$ of $G_v$ we have $\phi(v)=\psi(w)=0$. This clearly forces $\deg(v)=\deg(w)=\Delta$ (and $\Delta$ odd), and establishes (*). \medskip To finish the proof, let us choose the cut-vertex $v$ of $G$ and the bridge $vw$ in such a way that $G_v$ is bridgeless. Take any neighbour $u$ of $v$ in~$G_v$. If $u$ was a cut-vertex, then by (*) it would be incident with a bridge of $G$, which is impossible because $G_v$ was chosen bridgeless. Therefore $G_v-u$ is connected. Lemma~\ref{lemma:order} now ensures that the vertices of $G_v-u$ can be ordered into a sequence $x_2,x_3,\ldots,x_m$ with $x_m=v$ in such a way that for $2\le i