On the signed chromatic number of some classes of graphs

Julien Bensmail Sandip Das Soumen Nandi
Théo Pierron Sagnik Sen Éric Sopena Université Côte d’Azur, CNRS, Inria, I3S, France Indian Statistical Institute, Kolkata, India Institute of Engineering & Management, Kolkata, India Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France Indian Institute of Technology Dharwad, India Faculty of Informatics, Masaryk University, Botanická 68A, 602 00 Brno, Czech Republic Université Lyon 1, LIRIS, UMR CNRS 5205, F-69621 Lyon, France

Abstract

A signed graph $(G,\sigma)$ is a graph $G$ along with a function $\sigma:E(G)\to\{+,-\}$ . A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The signed chromatic number of a signed graph $(G,\sigma)$ is the minimum number of vertices $|V(H)|$ of a signed graph $(H,\pi)$ to which $(G,\sigma)$ admits a homomorphism.

Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the signed chromatic number. In this work, we provide new results and bounds on the signed chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_{n}$ -minor-free graphs, and bounded-degree graphs).

Keywords: signed chromatic number; homomorphism of signed graphs; planar graph; triangle-free planar graph; $K_{n}$ -minor-free graph; bounded-degree graph.

^†^†journal: …

1 Introduction

Naserasr, Rollová and Sopena introduced and initiated in [15] the study of homomorphisms of signed graphs, based on the works of Zaslavsky [20] and Guenin [9]. Over the passed few years, their work has generated increasing attention to the topic, see e.g. [2, 6, 8, 14, 16, 19]. One reason behind this interest lies in the fact that homomorphisms of signed graphs stand as a natural way for generalizing a number of classical results and conjectures from graph theory, including, especially, ones related to graph minor theory (such as the Four-Color Theorem and Hadwiger’s Conjecture). More generally, signed graphs are objects that arise in many contexts. Quite recently, for instance, Huang solved the Sensitivity Conjecture in [10], through the use, in particular, of signed graphs. His result was later improved by Laplante, Naserasr and Sunny in [11]. These interesting works and results brought yet more attention to the topic.

In the recent years, works on homomorphisms of signed graphs have developed following two main branches. The first branch of research deals with attempts to generalize existing results and to solve standing conjectures (regarding mainly undirected graphs). The second branch of research aims at understanding the very nature of signed graphs and their homomorphisms, thereby developing its own theory. Since our investigations in this paper are not related to all those concerns, there would be no point giving an exhaustive survey of the whole field. Instead, we focus on the definitions, notions, and previous investigations that connect to our work. Still, we need to cover a lot of material to make our motivations and investigations understandable. To ease the reading, we have consequently split this section into smaller subsections with different contents.

1.1 Signed graphs and homomorphisms

Throughout this work, we restrict ourselves to graphs that are simple, i.e., loopless graphs in which every two vertices are joined by at most one edge. For modified types of graphs, such as signed graphs, the notion of simplicity is understood with respect to their underlying graph. Given a graph $G$ , as per usual, $V(G)$ and $E(G)$ denote the set of vertices and the set of edges, respectively, of $G$ .

A signed graph $(G,\sigma)$ is a graph $G$ along with a function $\sigma:E(G)\rightarrow\{+,-\}$ called its signature. For every edge $e\in E(G)$ , we call $\sigma(e)$ the sign of $e$ . The edges of $(G,\sigma)$ in $\sigma^{-1}(+)$ are positive, while the edges in $\sigma^{-1}(-)$ are negative. In certain circumstances, it will be more convenient to deal with $(G,\sigma)$ in such a way that its set of negative edges is emphasized, in which case we will write $(G,\Sigma)$ instead, where $\Sigma=\sigma^{-1}(-)$ denotes the set of negative edges. Note that the notations $(G,\sigma)$ and $(G,\Sigma)$ are equivalent anyway, since $\sigma$ can be deduced from $\Sigma$ , and vice versa.

Signed graphs come with a particular switching operation that can be performed on sets of vertices. For a vertex $v\in V(G)$ of a signed graph $(G,\sigma)$ , switching $v$ means changing the sign of all the edges incident to $v$ . This definition extends to sets of vertices: for a set $S\subseteq V(G)$ of vertices of $(G,\sigma)$ , switching $S$ means changing the sign of the edges in the cut $(S,V(G)\setminus S)$ . For $S\subseteq V(G)$ , we denote by $(G,\sigma^{(S)})$ the signed graph obtained from $(G,\sigma)$ when switching $S$ . Two signed graphs $(G,\sigma_{1})$ and $(G,\sigma_{2})$ are switching-equivalent if $(G,\sigma_{2})$ can be obtained from $(G,\sigma_{1})$ by switching a set of vertices, which we write $(G,\sigma_{1})\sim(G,\sigma_{2})$ . Note that $\sim$ is indeed an equivalence relation.

An important notion in the study of signed graphs is the sign of its closed walks. Recall that, in a graph, a walk is a path in which vertices and edges can be repeated. A closed walk is a walk starting and ending at the same vertex. A closed walk $C$ of a signed graph is positive if it has an even number of negative edges (counting with multiplicity), and negative otherwise. Observe that the sign of closed walks is invariant under the switching operation. In fact, the two notions are even more related, as revealed by Zaslavsky’s Lemma.

Lemma 1.1 (Zaslavsky [20]).

Let $(G,\sigma_{1})$ and $(G,\sigma_{2})$ be two signed graphs having the same underlying graph $G$ . Then $(G,\sigma_{1})\sim(G,\sigma_{2})$ if and only if the sign of every closed walk is the same in both $(G,\sigma_{1})$ and $(G,\sigma_{2})$ .

Before moving on to all the definitions and notions related to signed graph homomorphisms, let us point out to the reader that the main difference between signed graphs and $2$ -edge-colored graphs lies in the switching operation. Recall that a $2$ -edge-colored graph $(G,c)$ is a graph $G$ along with a function $c:E(G)\rightarrow\{1,2\}$ that assigns one of two possible colors to the edges, but with no switching operation. Thus, in some sense, $2$ -edge-colored graphs stand as a static version (sign-wise) of signed graphs. It was noticed in [7, 15, 19] that homomorphisms of $2$ -edge-colored graphs are closely related to homomorphisms of signed graphs. For the sake of uniformity and convenience, we below refer to such homomorphisms as sign-preserving homomorphisms of signed graphs. The study of such homomorphisms was initiated in [1] independently from the notion of homomorphisms of signed graphs.

A sign-preserving homomorphism (or sp-homomorphism for short) of a signed graph $(G,\sigma)$ to a signed graph $(H,\pi)$ is a vertex-mapping $f:V(G)\rightarrow V(H)$ that preserves adjacencies and signs of edges, i.e., for every $uv\in E(G)$ we have $f(u)f(v)\in E(H)$ and $\sigma(uv)=\pi(f(u)f(v))$ . When such an sp-homomorphism exists, we write $(G,\sigma)\xrightarrow{sp}(H,\pi)$ . The sign-preserving chromatic number $\chi_{sp}((G,\sigma))$ of a signed graph $(G,\sigma)$ is the minimum order $|V(H)|$ of a signed graph $(H,\pi)$ such that $(G,\sigma)\xrightarrow{sp}(H,\pi)$ . For a family $\mathcal{F}$ of graphs, the sign-preserving chromatic number is generalized as

\chi_{sp}(\mathcal{F})=\max\left\{\chi_{sp}((G,\sigma)):G\in\mathcal{F}\right\}.

A signed graph $(H,\pi)$ is said to be a sign-preserving bound (or sp-bound for short) of $\mathcal{F}$ if $(G,\sigma)\xrightarrow{sp}(H,\pi)$ for all $G\in\mathcal{F}$ . Furthermore, $(H,\pi)$ is minimal if no proper subgraph of $(H,\pi)$ is an sp-bound of $\mathcal{F}$ .

We are now ready to define homomorphisms of signed graphs. It is worth mentioning that the upcoming definition is a restricted simpler version of a more general one [17]. A homomorphism of a signed graph $(G,\sigma)$ to a signed graph $(H,\pi)$ is a vertex-mapping $f:V(G)\rightarrow V(H)$ that preserves adjacencies and signs of closed walks. We write $(G,\sigma)\rightarrow(H,\pi)$ whenever $(G,\sigma)$ admits a homomorphism to $(H,\pi)$ .

The next proposition highlights the underlying connection between sp-homomorphisms and homomorphisms of signed graphs. This proposition actually provides an alternative definition of homomorphisms of signed graph.

Proposition 1.2 (Naserasr, Sopena, Zaslavsky [17]).

A mapping $f$ is a homomorphism of $(G,\sigma)$ to $(H,\pi)$ if and only if there exists $(G,\sigma^{\prime})\sim(G,\sigma)$ such that $f$ is an sp-homomorphism of $(G,\sigma^{\prime})$ to $(H,\pi)$ .

Just as for sp-homomorphisms, the signed chromatic number $\chi_{s}((G,\sigma))$ of a signed graph $(G,\sigma)$ is the minimum order $|V(H)|$ of a signed graph $(H,\pi)$ such that $(G,\sigma)\rightarrow(H,\pi)$ . For a family $\mathcal{F}$ of graphs, the signed chromatic number is given by

\chi_{s}(\mathcal{F})=\max\left\{\chi_{s}((G,\sigma)):G\in\mathcal{F}\right\}.

Moreover, a bound of $\mathcal{F}$ is a signed graph $(H,\pi)$ such that $(G,\sigma)\rightarrow(H,\pi)$ for all $G\in\mathcal{F}$ . A bound of $\mathcal{F}$ is minimal if none of its proper subgraphs is a bound of $\mathcal{F}$ .

1.2 Sign-preserving homomorphisms vs. homomorphisms of signed graphs

One can observe that if $(G,\sigma)$ is a signed graph having positive edges (resp., negative edges) only, then $(G,\sigma)\rightarrow(K_{\chi(G)},\pi)$ , where $\chi(G)$ denotes the usual chromatic number of the graph $G$ and $(K_{\chi(G)},\pi)$ is the signed complete graph of order $\chi(G)$ having positive edges (resp., negative edges) only, and thus $\chi_{sp}((G,\sigma))=\chi_{s}((G,\sigma))=\chi(G)$ . Hence, the notions of sign-preserving chromatic number and signed chromatic number are indeed generalizations of the usual notion of chromatic number.

For undirected graphs, homomorphism bounds of minimum order are nothing but complete graphs. The study of sp-bounds and bounds for signed graphs is thus much richer from that point of view, as one of the most challenging aspects behind determining $\chi_{sp}(\mathcal{F})$ or $\chi_{s}(\mathcal{F})$ for a given family $\mathcal{F}$ can actually be narrowed to finding (sp-)bounds of minimum order.

One hint on the general connection between the sign-preserving chromatic number and the signed chromatic number is provided by the following results.

Lemma 1.3 (Naserasr, Rollová, Sopena [15]).

Let $(G,\sigma)$ and $(H,\pi)$ be two signed graphs. If $(G,\sigma)\rightarrow(H,\pi)$ , then, for every $(H,\pi^{\prime})\sim(H,\pi)$ , there exists $(G,\sigma^{\prime})\sim(G,\sigma)$ such that $(G,\sigma^{\prime})\xrightarrow{sp}(H,\pi^{\prime})$ .

The connection between the sign-preserving chromatic number and the signed chromatic number was shown to be actually even deeper, through the concept of double switching graphs. Given a signed graph $(G,\sigma)$ , the double switching graph $(\hat{G},\hat{\sigma})$ of $(G,\sigma)$ is obtained from $(G,\sigma)$ by adding an anti-twin vertex $\hat{v}$ for every vertex $v\in V(G)$ , which means that for every $uv\in E(G)$ , the graph $\hat{G}$ contains the edges $uv,u\hat{v},\hat{u}v,\hat{u}\hat{v}$ and their signs satisfy $\sigma(uv)=\hat{\sigma}(uv)=\hat{\sigma}(\hat{u}\hat{v})\neq\hat{\sigma}(u\hat{v})=\hat{\sigma}(\hat{u}v)$ . One connection between $(G,\sigma)$ and $(\hat{G},\hat{\sigma})$ is the following.

Theorem 1.4 (Ochem, Pinlou, Sen [19]).

For every two signed graphs $(G,\sigma)$ and $(H,\pi)$ , we have $(G,\sigma)\rightarrow(H,\pi)$ if and only if $(G,\sigma)\xrightarrow{sp}(\hat{H},\hat{\pi})$ .

In particular, this result implies the following relations between the two chromatic numbers.

Proposition 1.5 (Naserasr, Rollová, Sopena [15]).

For every signed graph $(G,\sigma)$ , we have $\chi_{s}((G,\sigma))\leq\chi_{sp}((G,\sigma))\leq 2\chi_{s}((G,\sigma))$ .

An even deeper connection, based on (sp-)isomorphisms of signed graphs, was established by Brewster and Graves [7]. A bijective (sp-)homomorphism whose inverse is also an (sp-)homomorphism is an (sp-)isomorphism. Two signed graphs are (sp-)isomorphic if there exists an (sp-)isomorphism between the two.

Theorem 1.6 (Brewster, Graves [7]).

Two signed graphs $(G,\sigma)$ and $(H,\pi)$ are isomorphic if and only if $(\hat{G},\hat{\sigma})$ and $(\hat{H},\hat{\pi})$ are sp-isomorphic.

1.3 Our contribution

In this paper, we establish bounds and results related to the sign-preserving chromatic number and the signed chromatic number of various families of graphs. More precisely, we focus on planar graphs with given girth, $K_{n}$ -minor-free graphs, and graphs with bounded maximum degree. Each of our results is proved in a dedicated section.

Planar graphs

Recall that the girth of a graph refers to the length of its shortest cycles. We denote by $\mathcal{P}_{g}$ the family of planar graphs having girth at least $g$ . Then, note that $\mathcal{P}_{3}$ is nothing but the whole family of planar graphs, while $\mathcal{P}_{4}$ is the family of triangle-free planar graphs.

Towards establishing analogues of the Four-Color Theorem and of Grötzsch’s Theorem for signed graphs, several works have been dedicated to studying the parameters $\chi_{sp}(\mathcal{P}_{g})$ and $\chi_{s}(\mathcal{P}_{g})$ . Note that it is worthwhile investigating such aspects, since, for all values of $g\geq 3$ , these two chromatic parameters are known to be finite, due to the existence of an (sp-)bound of $\mathcal{P}_{g}$ (see [19]).

Let us now discuss the best known bounds on $\chi_{sp}(\mathcal{P}_{g})$ and $\chi_{s}(\mathcal{P}_{g})$ for small values of $g$ . Regarding the whole family $\mathcal{P}_{3}$ of planar graphs, it is known that $20\leq\chi_{sp}(\mathcal{P}_{3})\leq 80$ and $10\leq\chi_{s}(\mathcal{P}_{3})\leq 40$ hold, as proved in [1] and [19], respectively. In particular, it is worth mentioning that if $\chi_{s}(\mathcal{P}_{3})=10$ , then there even exists a bound of $\mathcal{P}_{3}$ of order $10$ . Ochem, Pinlou and Sen have actually shown in [19] that if such a bound exists, it must be isomorphic to $(SP_{9}^{+},\square^{+})$ , a signed graph we describe in upcoming Section 2. Due to Theorems 1.4 and 1.6, one may equivalently express this result in the following fashion.

Theorem 1.7 (Ochem, Pinlou, Sen [19]).

If there is a double switching sp-bound of $\mathcal{P}_{3}$ of order $20$ , then it is sp-isomorphic to $(\hat{SP}_{9}^{+},\hat{\square}^{+})$ .

Our first main result in this work (proved in Section 3) is that Theorem 1.7 can be strengthened, in the sense that it also holds when dropping the double switching requirement from the statement. That is, we show that the only possible minimal sp-bound of $\mathcal{P}_{3}$ of order $20$ has to be $(\hat{SP}_{9}^{+},\hat{\square}^{+})$ .

Theorem 1.8.

If there is a minimal sp-bound of $\mathcal{P}_{3}$ of order $20$ , then it is sp-isomorphic to $(\hat{SP}_{9}^{+},\hat{\square}^{+})$ .

It is worth mentioning that, supported by computer experimentations and theoretical evidences, it is conjectured that $(SP_{9}^{+},\square^{+})$ is indeed a bound of $\mathcal{P}_{3}$ (see [5]).

Triangle-free planar graphs

For the family $\mathcal{P}_{4}$ of triangle-free planar graphs, it is known that $12\leq\chi_{sp}(\mathcal{P}_{4})\leq 50$ and $6\leq\chi_{s}(\mathcal{P}_{4})\leq 25$ hold, as proved in [19]. A natural intuition is that if $\chi_{s}(\mathcal{P}_{3})=10$ indeed held, then it would not be too surprising to have $\chi_{s}(\mathcal{P}_{4})=6$ . In practice, however, making that step would not be that easy, as, in general, bounds are seemingly difficult to prove. From that point of view, it would be interesting to have an analogous version of Theorem 1.8 in this context. Our second main result in this paper (proved in Section 4) lies in that spirit, and reads as follows (where, again, the description of $(SP_{5}^{+},\square^{+})$ , a signed graphs of order $6$ , is postponed to Section 2).

Theorem 1.9.

If there is a bound of $\mathcal{P}_{4}$ of order $6$ , then it is isomorphic to $(SP_{5}^{+},\square^{+})$ .

$K_{n}$ -minor-free graphs

Let $\mathcal{F}_{n}$ denote the family of $K_{n}$ -minor-free graphs. It is known that $\chi_{sp}(\mathcal{F}_{n})=1,4,9$ [1] and $\chi_{s}(\mathcal{F}_{n})=1,2,5$ for $n=2,3,4$ , respectively [15]. In [5], it was shown that if $\chi_{s}(\mathcal{P}_{3})=10$ (which would imply $\chi_{sp}(\mathcal{P}_{3})=20$ ) held, then it would imply $\chi_{s}(\mathcal{F}_{5})=10$ (and thus $\chi_{sp}(\mathcal{F}_{5})=20$ as well). However, prior to studying (sp-)bounds of $\mathcal{F}_{n}$ , a first significant step could be to first investigate analogues of Hadwiger’s Conjecture. To progress towards such analogues, it is first important to investigate what types of lower and upper bounds of $\chi_{sp}(\mathcal{F}_{n})$ and $\chi_{s}(\mathcal{F}_{n})$ one can expect. In particular, are $\chi_{sp}(\mathcal{F}_{n})$ and $\chi_{s}(\mathcal{F}_{n})$ upper bounded at all? In this work, our third main result (proved in Section 5) is the following series of results towards those concerns.

Theorem 1.10.

The following inequalities hold:

(i)

For all $n\geq 3$ ,

\chi_{s}(\mathcal{F}_{n})\leq 5{n-1\choose 2}2^{5{n-1\choose 2}-2}\text{ \leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\ }\chi_{sp}(\mathcal{F}_{n})\leq 5{n-1\choose 2}2^{5{n-1\choose 2}-1}.

(ii)

For all $n\geq 2$ ,

\chi_{sp}(\mathcal{F}_{n})\geq\begin{cases}\frac{2^{n+1}-5}{3},&\text{ when $n$ is even},\\ \frac{2^{n+1}-4}{3},&\text{ when $n$ is odd}.\end{cases}

(iii)

For all $n\geq 2$ ,

\chi_{s}(\mathcal{F}_{n})\geq\begin{cases}\frac{2^{n}-1}{3},&\text{ when $n$ is even},\\ \frac{2^{n}-2}{3},&\text{ when $n$ is odd}.\end{cases}

Graphs with given maximum degree

Let $\mathcal{G}^{\rm c}_{\Delta}$ denote the family of connected graphs with maximum degree at most $\Delta$ . For large values of $\Delta$ , it is possible to mimic an existing proof from [3] (related to the pushable chromatic number of oriented graphs¹¹1Without entering too much into the details, the reader should be aware of a parallel line of research dedicated to the so-called oriented chromatic number and pushable chromatic number of oriented graphs, which are, roughly speaking, a counterpart of the sign-preserving chromatic number and the signed chromatic number of signed graphs in which edges are oriented instead of signed. Although the studies of the signed chromatic number and of the oriented chromatic number are sometimes quite comparable, there exist contexts in which they actually differ significantly. For instance, there exist undirected graphs with oriented chromatic number arbitrarily larger than their signed chromatic number, as well as undirected graphs with signed chromatic number arbitrarily larger than their oriented chromatic number [4].) to show the following result.

Theorem 1.11.

For all $\Delta\geq 29$ , we have

2^{\frac{\Delta}{2}-1}\leq\chi_{s}(\mathcal{G}^{\rm c}_{\Delta})\leq(\Delta-3)\cdot(\Delta-1)\cdot 2^{\Delta-1}+2.

Since this result can be established by following the exact same lines as the proof from [3], there would be no point giving a proof, and we instead refer the reader to that reference.

For smaller values of $\Delta$ , one natural question is whether one can come up with the exact value of $\chi_{s}(\mathcal{G}^{\rm c}_{\Delta})$ . It is worth mentioning that the oriented analogue of this very question remains unanswered, even for the smallest values of $\Delta$ (see [3]). In the case of signed graphs, we answer that question for the case $\Delta=3$ , which stands as our fourth main result (proved in Section 6) in this paper.

Theorem 1.12.

We have $\chi_{s}(\mathcal{G}^{\rm c}_{3})=6$ .

In fact, we will prove the following stronger result that implies Theorem 1.12 as a corollary. In the statement, recall that $(SP_{5}^{+},\square^{+})$ refers to a signed graph that will be defined in Section 2; the only important thing to know, at this point, is that it has order $6$ .

Theorem 1.13.

Every signed subcubic graph with no connected component isomorphic to $(K_{4},\emptyset)$ or $(K_{4},E(K_{4}))$ admits a homomorphism to $(SP_{5}^{+},\square^{+})$ .

2 Definitions, terminology, and preliminary results on Paley graphs

Perhaps one of the most challenging aspects of studying (sp-)homomorphisms of signed graphs is to exhibit (sp-)bounds. In what follows, we introduce a few popular such bounds that appeared in the literature, which are related to so-called Paley graphs.

Let $q\equiv 1\bmod 4$ be a prime power, and $\mathbb{F}_{q}$ be the finite field of order $q$ . The signed Paley graph $(SP_{q},\square)$ of order $q$ is the signed graph with set of vertices $V(SP_{q})=\mathbb{F}_{q}$ , set of positive edges $\square^{-1}(+)=\{uv:u-v\text{ is a square in }\mathbb{F}_{q}\}$ , and set of negative edges $\square^{-1}(-)=\{uv:u-v\text{ is not a square in }\mathbb{F}_{q}\}$ . The signed Paley plus graph $(SP_{q}^{+},\square^{+})$ of order $q+1$ is the signed graph obtained from $(SP_{q},\square)$ by adding a vertex $\infty$ and making it adjacent to every other vertex through a positive edge. To avoid ambiguities, we will refer to a vertex $i\neq\infty$ of $SP_{q}$ or $SP_{q}^{+}$ by writing $\overline{i}$ . See Figure 1 for an illustration.

(a)

(b)

(c)

Figure 1: The signed graph

(SP_{5}^{+},\square^{+})

(a), the signed graph

(SP_{5}^{+},\boxdot^{+})

obtained by switching the vertices

\infty

and

\overline{1}

(SP_{5}^{+},\square^{+})

(b), and the signed graph

(SP_{9},\square)

(c). In (a), (b) and (c), solid edges are positive edges. In (a) and (b), dashed edges are negative edges. In (c), non-edges are negative edges.

Signed Paley graphs, signed Paley plus graphs, and their respective double switching graphs are, in the literature, regularly used as (sp-)bounds. One reason for that is that these graphs have a very symmetric structure, resulting in properties that are very useful when it comes to designing homomorphisms. Such useful properties deal, in particular, with some particular notions of transitivity. More precisely, a signed graph $(G,\sigma)$ is sign-preserving vertex-transitive (or sp-vertex-transitive for short) if, for every two vertices $u,v\in V(G)$ , there exists an sp-isomorphism $f$ of $(G,\sigma)$ to itself such that $f(u)=v$ . Furthermore, $(G,\sigma)$ is sign-preserving edge-transitive (or sp-edge-transitive for short) if, for every two edges $uv,u^{\prime}v^{\prime}\in E(G)$ with the same sign, there exists an sp-isomorphism $f$ of $(G,\sigma)$ to itself such that $f(u)=u^{\prime}$ and $f(v)=v^{\prime}$ . Similarly, $(G,\sigma)$ is vertex-transitive if, for every two vertices $u,v\in V(G)$ , there exists an isomorphism $f$ of $(G,\sigma)$ to itself such that $f(u)=v$ ; while $(G,\sigma)$ is edge-transitive if, for every two edges $uv,u^{\prime}v^{\prime}\in E(G)$ , there exists an isomorphism $f$ of $(G,\sigma)$ to itself such that $f(u)=u^{\prime}$ and $f(v)=v^{\prime}$ .

Proposition 2.1 (Ochem, Pinlou, Sen [19]).

Let $q\equiv 1\bmod 4$ be a prime power. Then:

(i)

$(SP_{q},\square)$ is sp-vertex-transitive and sp-edge-transitive;
(ii)

$(SP_{q}^{+},\square^{+})$ is vertex-transitive and edge-transitive.

Given a positive edge $uv$ of a signed graph $(G,\sigma)$ , we call $u$ a positive neighbor of $v$ . Analogously, $u$ is a negative neighbor of $v$ if $uv$ is a negative edge. We denote by $N(v)$ , $N^{+}(v)$ and $N^{-}(v)$ the sets of neighbors, positive neighbors, and negative neighbors, respectively, of $v$ in $(G,\sigma)$ . Analogously, we define the degree $d(v)$ , positive degree $d^{+}(v)$ , and negative degree $d^{-}(v)$ of $v$ as $|N(v)|$ , $|N^{+}(v)|$ and $|N^{-}(v)|$ , respectively. Assuming $u$ and $v$ are two distinct vertices having a common neighbor $w$ , we say that $u$ and $v$ agree on $w$ if $w\in N^{\alpha}(u)\cap N^{\alpha}(v)$ for some $\alpha\in\{-,+\}$ . Conversely, we say that $u$ and $v$ disagree on $w$ if they do not agree on $w$ .

Let $\vec{v}=(v_{1},\dots,v_{k})$ be a $k$ -tuple of distinct vertices of $(G,\sigma)$ and let $\vec{\alpha}=(\alpha_{1},\dots,\alpha_{k})\in\{+,-\}^{k}$ be a $k$ -vector with each of its elements being $+$ or $-$ . We define the $\vec{\alpha}$ -neighborhood of $\vec{v}$ as

N^{\vec{\alpha}}(\vec{v})=\cap_{i=1}^{k}N^{\alpha_{i}}(v_{i}).

Moreover, we say that $(G,\sigma)$ has property $P_{k,\ell}$ if, for every $k$ -tuple $\vec{v}$ and every $k$ -vector $\vec{\alpha}$ , we have $|N^{\vec{\alpha}}(\vec{v})|\geq\ell$ . We also define the negation $-\vec{\alpha}$ of a $k$ -vector $\vec{\alpha}=(\alpha_{1},\dots,\alpha_{k})$ as $-\vec{\alpha}=(-\alpha_{1},\dots,-\alpha_{k})$ where $-\alpha_{i}=-$ if $\alpha_{i}=+$ , and $-\alpha_{i}=+$ otherwise. The switched $\vec{\alpha}$ -neighborhood of $\vec{v}$ is then

\hat{N}^{\vec{\alpha}}(\vec{v})=N^{\vec{\alpha}}(\vec{v})\cup N^{-\vec{\alpha}}(\vec{v}).

Lastly, we say that $(G,\sigma)$ has property $\hat{P}_{k,\ell}$ if, for every $k$ -tuple $\vec{v}$ and every $k$ -vector $\vec{\alpha}$ , we have $|\hat{N}^{\vec{\alpha}}(\vec{v})|\geq\ell$ . Notice that this property is invariant under the switching operation.

It turns out that signed Paley graphs and signed Paley plus graphs also have the following interesting properties, which are very convenient ones for designing homomorphisms.

Proposition 2.2 (Ochem, Pinlou, Sen [19]).

Let $q\equiv 1\bmod 4$ be a prime power. Then:

(i)

$(SP_{q},\square)$ has property $P_{1,\frac{q-1}{2}}$ and $P_{2,\frac{q-5}{4}}$ ;
(ii)

$(SP_{q}^{+},\square^{+})$ has property $\hat{P}_{1,q}$ , $\hat{P}_{2,\frac{q-1}{2}}$ and $\hat{P}_{3,\frac{q-5}{4}}$ .

3 Proof of Theorem 1.8

Let $(T,\lambda)$ be a minimal sp-bound of $\mathcal{P}_{3}$ of order $20$ , assuming that such a signed graph exists. In this section, our goal is to show that $(T,\lambda)$ must be sp-isomorphic to $(\hat{SP}_{9}^{+},\hat{\square}^{+})$ . To this end, we first use the following lemma to show that $\Delta(T)\in\{18,19\}$ . We then deal with each of the two possible values of $\Delta(T)$ separately.

Lemma 3.1.

For every vertex $v$ of $(T,\lambda)$ , we have $d^{+}(v),d^{-}(v)\geq 9$ . Moreover, if $d^{\alpha}(v)=9$ for an $\alpha\in\{+,-\}$ , then the induced subgraph $(T,\lambda)[N^{\alpha}(v)]$ is sp-isomorphic to $(SP_{9},\square)$ .

Proof.

It is known (see [12]) that, for the family $\mathcal{O}_{3}$ of outerplanar graphs, we have $\chi_{sp}(\mathcal{O}_{3})=9$ and the only sp-bound of $\mathcal{O}_{3}$ of order $9$ is $(SP_{9},\square)$ . Thus, there exists an outerplanar signed graph $(O,\varphi)$ with $\chi_{sp}((O,\varphi))=9$ , and such that the only signed graph of order $9$ to which $(O,\varphi)$ admits an sp-homomorphism is $(SP_{9},\square)$ . Also, it is known from [1] that there exists a planar signed graph $(P,\pi)$ with $\chi_{sp}((P,\pi))=20$ .

Let us now consider the planar signed graph $(P^{\prime},\pi^{\prime})$ obtained as follows: start from $(P,\pi)$ , and, for every $v\in V(P)$ , add a copy of $(O,\varphi)$ to the $+$ -neighborhood of $v$ and another copy to the $-$ -neighborhood of $v$ (see Figure 2).

Figure 2: Construction of

(P^{\prime},\pi^{\prime})

in Lemma 3.1. Solid edges are positive edges, dashed ones are negative.

Observe that the so-obtained signed graph $(P^{\prime},\pi^{\prime})$ is planar. Also, according to our assumption, $(P^{\prime},\pi^{\prime})\xrightarrow{sp}(T,\lambda)$ . Therefore, for each $\alpha\in\{+,-\}$ , we obtain

d_{T}^{\alpha}(v)\geqslant\chi_{sp}((P^{\prime}[N^{\alpha}(v)],\pi^{\prime}))=\chi_{sp}((O,\varphi))=9.

The last part of the statement follows from the fact that $(SP_{9},\square)$ is the only signed graph of order $9$ to which $(O,\varphi)$ admits an sp-homomorphism. ∎

From the previous result, we deduce that the maximum degree $\Delta(T)$ of $T$ is $18$ or $19$ . We first consider the case $\Delta(T)=18$ , and show that $(T,\lambda)$ is sp-isomorphic to $(\hat{SP}_{9}^{+},\square^{+})$ . Note that, by Theorem 1.7, we just have to show that $(T,\lambda)$ is a double switching graph.

Lemma 3.2.

If $\Delta(T)=18$ , then $(T,\lambda)$ is a double switching graph.

Proof.

Observe that Lemma 3.1 ensures that $\delta(T)=18$ . Therefore, if $\Delta(T)=18$ , then $T$ is $18$ -regular and thus has an anti-matching. Let now $v$ and $v^{\prime}$ be two non-adjacent vertices of $T$ , and assume that $v$ and $v^{\prime}$ are not anti-twins. Then there exists a vertex $w\in N^{\alpha}(v)\cap N^{\alpha}(v^{\prime})$ for some $\alpha\in\{+,-\}$ . Observe now that $N^{\alpha}(w)$ contains both $v$ and $v^{\prime}$ , and hence induces a non-complete graph. This is a contradiction with Lemma 3.1 since $N^{\alpha}(w)$ induces $(SP_{9},\square)$ whose underlying graph is complete. Therefore, every pair of non-adjacent vertices of $(T,\lambda)$ are anti-twins, implying that $(T,\lambda)$ is a double switching graph. ∎

This concludes the proof of Theorem 1.8 in the case $\Delta(T)=18$ . The rest of this section is devoted to the case $\Delta(T)=19$ , in which we aim for a contradiction. To obtain this contradiction, we investigate how the neighborhoods of adjacent vertices interact in $(T,\lambda)$ .

Lemma 3.3.

For every edge $uv$ of $(T,\lambda)$ and $\alpha,\beta\in\{+,-\}$ , we have $|N^{\alpha}(u)\cap N^{\beta}(v)|\geq 4$ .

Proof.

As mentioned earlier, there exist planar signed graphs $(P,\pi)$ with $\chi_{sp}((P,\pi))=20$ , and, because $(T,\lambda)$ is minimal, that have the following property: for every edge $uv\in E(T)$ and for any sp-homomorphism $f:(P,\pi)\xrightarrow{sp}(T,\lambda)$ , there exists an edge $xy\in E(P)$ such that $f(x)=u$ and $f(y)=v$ .

Let $(P_{5},M)$ denote the signed path on five edges whose three negative edges induce a maximum matching $M$ . Observe that $\chi_{sp}((P_{5},M))=4$ .

Let us now consider the planar signed graph $(P^{\prime},\pi^{\prime})$ obtained as follows (see Figure 3): start from $(P,\pi)$ , and, for every $xy\in E(P)$ and all $(\alpha,\beta)\in\{+,-\}^{2}$ , include a copy of $(P_{5},M)$ inside $N^{\alpha}(x)\cap N^{\beta}(y)$ .

Figure 3: Construction of

(P^{\prime},\pi^{\prime})

in Lemma 3.3. Solid edges are positive edges, dashed ones are negative.

Observe that the so-obtained signed graph $(P^{\prime},\pi^{\prime})$ is planar. Furthermore, according to our assumption, $(P^{\prime},\pi^{\prime})\xrightarrow{sp}(T,\lambda)$ . Therefore, for every $uv\in E(T)$ and for all $\alpha,\beta\in\{+,-\}$ , every copy of $(P_{5},M)$ must admit a homomorphism to the subgraph of $(T,\lambda)$ induced by $N^{\alpha}(u)\cap N^{\beta}(v)$ . Hence, the fact that $\chi_{sp}((P_{5},M))=4$ implies that $|N^{\alpha}(u)\cap N^{\beta}(v)|\geq 4$ . ∎

In view of Lemmas 3.1 and 3.3, every intersection $N^{\alpha}(u)\cap N^{\beta}(v)$ induces a complete subgraph of $(SP_{9},\square)$ of order at least $4$ . Before completing the proof, we investigate the possible signatures of the $K_{4}$ ’s that are subgraphs of $(SP_{9},\square)$ , and state some of their properties. Since these properties are easy to verify due to the vertex-transitivity and edge-transitivity of $(SP_{9},\square)$ , some formal proofs are omitted.

Let $(K_{4},M^{-})$ be the signed graph having the complete graph $K_{4}$ as its underlying graph and a perfect matching as its set of negative edges. Similarly, let $(K_{4},M^{+})$ be the signed graph having $K_{4}$ as its underlying graph and the edges of a $4$ -cycle (that is, the complement of a perfect matching) as its set of negative edges.

Observation 3.4.

For every vertex $v$ of $(SP_{9},\square)$ , the set $N^{+}(v)$ induces $(K_{4},M^{+})$ in $(SP_{9},\square)$ , while the set $N^{-}(v)$ induces $(K_{4},M^{-})$ .

Observation 3.5.

For every induced $(K_{4},M^{+})$ (resp., $(K_{4},M^{-})$ ) of $(SP_{9},\square)$ , there exists a $v\in V(SP_{9})$ such that $N^{+}(v)$ (resp., $N^{-}(v)$ ) induces that $(K_{4},M^{+})$ (resp., $(K_{4},M^{-})$ ).

We are now ready to derive the desired contradiction in the case $\Delta(T)=19$ . We first need to show that there are two vertices $u$ and $v$ of “large” degree.

Lemma 3.6.

For some $\{\alpha,\overline{\alpha}\}=\{+,-\}$ , there exists an $\alpha$ -edge $uv$ of $(T,\lambda)$ such that $d^{\alpha}(u)=d^{\overline{\alpha}}(v)=10$ and $d^{\alpha}(v)=9$ .

Proof.

Since $\Delta(T)=19$ , there is a vertex $v\in V(T)$ with $d(v)=19$ . By Lemma 3.1, we have $d^{\alpha}(v)=9$ and $d^{\overline{\alpha}}(v)=10$ for some $\{\alpha,\overline{\alpha}\}=\{+,-\}$ . By Lemma 3.3, each vertex in $N^{\overline{\alpha}}(v)$ has at least four $\alpha$ -neighbors in $N^{\alpha}(v)$ . Hence there are at least 40 $\alpha$ -edges between $N^{\alpha}(v)$ and $N^{\overline{\alpha}}(v)$ in $(T,\lambda)$ . Since $d^{\alpha}(v)=9$ , there exists $u\in N^{\alpha}(v)$ incident to at least $\lceil 40/9\rceil=5$ such $\alpha$ -edges. Moreover, since $d^{\alpha}(v)=9$ , Lemma 3.1 ensures that $N^{\alpha}(v)$ induces $(SP_{9},\square)$ , and hence $u$ has four $\alpha$ -neighbors in $N^{\alpha}(v)$ . Observe also that $v$ is an $\alpha$ -neighbor of $u$ . Thus, we deduce that $d^{\alpha}(u)\geq 5+4+1=10$ as desired. ∎

Let $uv$ be an $\alpha$ -edge of $(T,\lambda)$ that is as described in Lemma 3.6. We now exhibit properties of the neighborhoods of $u$ and $v$ in $(T,\lambda)$ .

Lemma 3.7.

Let $A=N^{\alpha}(v)\cap N^{\overline{\alpha}}(u)$ . We have $|A|=4$ . Moreover, there exists $x\in N^{\overline{\alpha}}(u)$ such that $A=N^{\overline{\alpha}}(u)\cap N^{\overline{\alpha}}(x)$ .

Proof.

Recall that the signed subgraphs induced by $N^{\alpha}(v)$ and $N^{\overline{\alpha}}(u)$ are both isomorphic to $(SP_{9},\square)$ , due to Lemma 3.1. Observe that $A$ coincides with the $\overline{\alpha}$ -neighborhood of $u$ in $N^{\alpha}(v)$ . In particular, since $u\in N^{\alpha}(v)$ , $A$ contains exactly four vertices inducing $(K_{4},M^{\overline{\alpha}})$ according to Observation 3.4. Furthermore, by Observation 3.5, because $A$ induces $(K_{4},M^{\overline{\alpha}})$ inside $N^{\overline{\alpha}}(u)$ (which is also sp-isomorphic to $(SP_{9},\square)$ ), there exists $x\in N^{\overline{\alpha}}(u)$ such that $A\subseteq N^{\overline{\alpha}}(x)$ . Observe that $A$ is precisely the $\overline{\alpha}$ -neighborhood of $x$ in the subgraph induced by $N^{\overline{\alpha}}(u)$ . Hence, $A=N^{\overline{\alpha}}(x)\cap N^{\overline{\alpha}}(u)$ . ∎

We now reach a contradiction by showing that $N^{\alpha}(x)$ has size 9 (and thus induces $(SP_{9},\square)$ ) and contains two disjoint copies of $(K_{4},M^{\alpha})$ , which is impossible. These statements are summarized in the following lemmas.

Lemma 3.8.

The sets $B=N^{\overline{\alpha}}(u)\setminus(A\cup\{x\})$ and $C=N^{\alpha}(v)\cap N^{\alpha}(u)$ are disjoint and they both induce $(K_{4},M^{\alpha})$ in $(T,\lambda)$ . Moreover, we have $B=N^{\alpha}(x)\cap N^{\overline{\alpha}}(u)$ .

Proof.

Since $N^{\overline{\alpha}}(u)$ induces the signed complete graph $SP_{9}$ , $B$ is the set of all neighbors of $x$ in $N^{\overline{\alpha}}(u)$ that are not in $A$ , i.e., all the $\alpha$ -neighbors of $x$ . Hence, $B=N^{\alpha}(x)\cap N^{\overline{\alpha}}(u)$ . Observation 3.4 thus yields that $B$ induces $(K_{4},M^{\alpha})$ .

The same argument, applied to the copy of $SP_{9}$ induced by $N^{\alpha}(v)$ , ensures that $C$ also induces $(K_{4},M^{\alpha})$ . Moreover, since $B\subset N^{\overline{\alpha}}(u)$ and $C\subset N^{\alpha}(u)$ , these sets are disjoint. ∎

Lemma 3.9.

$N^{\alpha}(x)$ contains $B\cup C$ and has size 9.

Proof.

First observe that, by Lemma 3.8, the vertices of $B$ are $\alpha$ -neighbors of $x$ . Hence, $B\subset N^{\alpha}(x)$ . Now, since $v$ has degree 19, $v$ and $x$ are adjacent and Lemma 3.3 ensures that $N^{\alpha}(v)$ contains at least four $\alpha$ -neighbors of $x$ . Observe now that $N^{\alpha}(v)=A\cup C\cup\{u\}$ and that $A\cup\{u\}$ are $\overline{\alpha}$ -neighbors of $x$ (by Lemma 3.7). Therefore, the four $\alpha$ -neighbors of $x$ in $N^{\alpha}(v)$ are precisely the vertices of $C$ , i.e. $C=N^{\alpha}(v)\cap N^{\alpha}(x)\subset N^{\alpha}(x)$ .

We now exhibit 10 $\overline{\alpha}$ -neighbors of $x$ , which will ensure that $|N^{\alpha}(x)|=9$ . By Lemma 3.7, we already know five such neighbors, namely $u$ and the vertices in $A$ . Moreover, since $N^{\alpha}(v)=A\cup C\cup\{u\}$ and $C\subset N^{\alpha}(x)$ , we get that $x\notin N^{\alpha}(v)$ , and, hence, $v$ is another $\overline{\alpha}$ -neighbor of $x$ . Now, by Lemma 3.3, there are at least four $\overline{\alpha}$ -neighbors of $x$ in $N^{\overline{\alpha}}(v)$ . Thus, because $x$ has four more $\overline{\alpha}$ -neighbors in $A$ and two more in $\{u,v\}$ , $x$ has a total of 10 $\overline{\alpha}$ -neighbors. So, we finally deduce that $|N^{\overline{\alpha}}(x)|=10$ , and, thus, that $|N^{\alpha}(x)|=9$ . ∎

4 Proof of Theorem 1.9

Let $(T,\lambda)$ be a minimal bound of $\mathcal{P}_{4}$ of order $6$ . We will show that $(T,\lambda)$ must be isomorphic to $(SP_{5}^{+},\square^{+})$ by essentially proving that $(T,\lambda)$ must have very specific properties, converging towards the precise ones that $(SP_{5}^{+},\square^{+})$ has. To do so, we will construct some signed graphs $(H_{0},\pi_{0})$ , $(H_{1},\pi_{1})$ , $\dots$ , all being triangle-free and planar, and, thus, admitting homomorphisms to $(T,\lambda)$ . These $(H_{i},\pi_{i})$ ’s will be constructed gradually, so that each of the $(H_{i},\pi_{i})$ ’s allows to deduce more properties of $(T,\lambda)$ .

To construct these $(H_{i},\pi_{i})$ ’s, we will mainly use the triangle-free planar signed graph $(H,\pi)$ depicted in Figure 4 as a building block. In what follows, it is important to keep in mind that we deal with the vertices and edges of $(H,\pi)$ using the notation introduced in Figure 4.

Figure 4: The main gadget

(H,\pi)

used to prove Theorem 1.9. Solid edges are positive edges. Dashed edges are negative edges. Vertices

x

and

y

agree on

a_{1}^{x,y}

a_{2}^{x,y}

and disagree on

d_{1}^{x,y}

d_{2}^{x,y}

Given a signed graph $(G,\Sigma)$ and one of its vertices $v$ , by pinning $(H,\pi)$ on $v$ we mean starting from $(G,\Sigma)$ , adding a copy of $(H,\pi)$ , and identifying the vertex $x$ of $(H,\pi)$ with the vertex $v$ of $(G,\Sigma)$ . Similarly, for two distinct vertices $u$ and $v$ of $(G,\Sigma)$ , by pinning $(H,\pi)$ on $(u,v)$ we mean starting from $(G,\Sigma)$ , adding a copy of $(H,\pi)$ , identifying the vertex $x$ of $(H,\pi)$ with the vertex $u$ of $(G,\Sigma)$ , and similarly identifying $y$ with $v$ . Observe that if $(G,\Sigma)$ is a triangle-free planar signed graph, and $u$ and $v$ are two non-adjacent vertices of $(G,\Sigma)$ belonging to a same face, then the signed graph obtained from $(G,\Sigma)$ by pinning $(H,\pi)$ on $(u,v)$ is also a triangle-free planar signed graph.

Note that the vertices of $(H,\pi)$ are named as functions of $x$ and $y$ . This will allow us to refer to vertices of a copy of $(H,\pi)$ after pinning it to, say, $(u,v)$ of $(G,\Sigma)$ , as functions of $u$ and $v$ . Since we will deal with larger and larger signed graphs containing multiple copies of $(H,\pi)$ , this terminology will allow us to refer to particular vertices in an unambiguous way.

We first show that $(T,\lambda)$ must be a signed complete graph. This is done by making use of the following observation. Recall that a negative cycle in a signed graph is a cycle having an odd number of negative edges, while a positive cycle has an even number of negative edges.

Observation 4.1 (see e.g. [15], Lemma 3.10).

Two vertices of a signed graph have distinct images under every homomorphism if and only if they are adjacent or they are part of a negative $4$ -cycle.

In the next result, we construct some first triangle-free planar signed graphs, from which we get that $(T,\lambda)$ must indeed be complete. We start from $(H_{0},\pi_{0})$ being the signed graph $(H,\pi)$ itself, in which we slightly modify the names of the vertices. That is, we refer to the vertices of $(H_{0},\pi_{0})$ as in $(H,\pi)$ , except that we omit the superscripts (if any). Thus, the vertices $x,y$ retain their name, while the vertices $a_{1}^{x,y}$ , $a^{x,y}$ , $a_{2}^{x,y}$ , $d_{1}^{x,y}$ , $d^{x,y}$ and $d_{2}^{x,y}$ are now, in $(H_{0},\pi_{0})$ , named $a_{1}$ , $a$ , $a_{2}$ , $d_{1}$ , $d$ and $d_{2}$ , respectively.

Lemma 4.2.

$(T,\lambda)$ is a signed complete graph.

Proof.

Let $(H_{1},\pi_{1})$ be the signed graph obtained from $(H_{0},\pi_{0})$ by pinning $(H,\pi)$ on $(x,a)$ . Note that $(H_{1},\pi_{1})$ is a triangle-free planar signed graph, and, thus, according to our assumption there exists a homomorphism $g:(H_{1},\pi_{1})\rightarrow(T,\lambda)$ . By Observation 4.1, the vertices $x$ , $y$ , $a_{1}$ , $a_{2}$ , $d_{1}$ and $d_{2}$ of $(H_{1},\pi_{1})$ have distinct images in $(T,\lambda)$ under every homomorphism $(H_{1},\pi_{1})\rightarrow(T,\lambda)$ . Furthermore, observe that the images of the vertices $x$ , $a$ , $a_{1}^{x,a}$ , $a_{2}^{x,a}$ , $d_{1}^{x,a}$ and $d_{2}^{x,a}$ are also distinct. Therefore, since $x$ , $y$ and $a$ must have distinct images and $(T,\lambda)$ has exactly six vertices, the images of $a_{1}^{x,a}$ , $a_{2}^{x,a}$ , $d_{1}^{x,a}$ and $d_{2}^{x,a}$ must contain the image of $y$ . In other words, we must have $g(y)\in\{g(a_{1}^{x,a}),g(a_{2}^{x,a}),g(d_{1}^{x,a}),g(d_{2}^{x,a})\}$ . Therefore, $g(x)$ must be adjacent to $\{g(a_{1}),g(a_{2}),g(d_{1}),g(d_{2}),g(y)\}$ in $(T,\lambda)$ , hence has degree 5.

Next, let $(H_{2},\pi_{2})$ be the signed graph obtained in the following manner: for each vertex $v$ of $(H_{0},\pi_{0})$ , we glue a copy of $(H_{1},\pi_{1})$ by identifying the vertex $x$ of $(H_{1},\pi_{1})$ with the vertex $v$ of $(H_{0},\pi_{0})$ . Note that $(H_{2},\pi_{2})$ is also a triangle-free planar signed graph. Therefore, it admits a homomorphism to $(T,\lambda)$ . By a previous remark, the vertices $x$ , $y$ , $a_{1}$ , $a_{2}$ , $d_{1}$ and $d_{2}$ must have distinct images by every homomorphism $(H_{2},\pi_{2})\rightarrow(T,\lambda)$ . Hence, there must be six distinct vertices of degree $5$ in $(T,\lambda)$ , which thus must be complete. ∎

Let now $(H_{3},\pi_{3})$ be the signed graph obtained from $(H_{0},\pi_{0})$ by pinning four $(H,\pi)$ ’s on $(x,a)$ , $(x,d)$ , $(y,a)$ and $(y,d)$ , respectively. Note that $(H_{3},\pi_{3})$ is a triangle-free planar signed graph, and thus it admits a homomorphism to $(T,\lambda)$ . In what follows, we need to understand better the different types of homomorphisms of $(H_{3},\pi_{3})$ to $(T,\lambda)$ .

Let $f$ be a homomorphism of $(H_{3},\pi_{3})$ to $(T,\lambda)$ . For convenience, suppose that $V(T)=\{1,2,3,4,5,6\}$ . By Observation 4.1, we know that, in $(H_{3},\pi_{3})$ , the vertices $x$ , $y$ , $a_{1}$ , $a_{2}$ , $d_{1}$ and $d_{2}$ have distinct images by $f$ . Without loss of generality, we may assume that these images by $f$ are as displayed in the following table:

$f(x)$	$f(y)$	$f(a_{1})$	$f(a_{2})$	$f(d_{1})$	$f(d_{2})$
$1$	$2$	$3$	$4$	$5$	$6$

Furthermore, by Observation 4.1 we know that $f(a)\in\{5,6\}$ and $f(d)\in\{3,4\}$ . Thus, without loss of generality, we may also assume $f(a)=5$ , which implies $f(d)=3$ :

$f(a)$	$f(d)$
$5$	$3$

Note that this may require to switch some vertices among $a$ and $d$ , but in that case we can relabel some vertices of the four pinned copies of $(H,\pi)$ in $(H_{3},\pi_{3})$ and keep the original signature of $(H_{3},\pi_{3})$ .

Now, let us focus on the copy of $(H,\pi)$ in $(H_{3},\pi_{3})$ that was pinned on $(x,a)$ . Notice, by Observation 4.1, that $f(x),f(a)$ , $f(a_{1}^{x,a})$ , $f(a_{2}^{x,a})$ , $f(d_{1}^{x,a})$ and $f(d_{2}^{x,a})$ are pairwise distinct, that $f(a_{1}^{x,a}),f(a_{2}^{x,a})\in\{2,3,6\}$ (since they agree on vertices $1$ and $5$ ), and that $f(d_{1}^{x,a}),f(d_{2}^{x,a})\in\{2,4,6\}$ (since they disagree on vertices $1$ and $5$ ). Therefore, either $f(a_{1}^{x,a})=3$ or $f(a_{2}^{x,a})=3$ and, similarly, either $f(d_{1}^{x,a})=4$ or $f(d_{2}^{x,a})=4$ . As we have not assumed that $(H_{3},\pi_{3})$ is embedded in the plane in a specific way, due to the symmetric structure of the graph, we may assume without loss of generality $f(a_{1}^{x,a})=3$ and $f(d_{2}^{x,a})=4$ . Reasoning similarly on the other copies of $(H,\pi)$ , we may suppose that we have the following images by $f$ :

$f(a_{1}^{x,a})$	$f(d_{2}^{x,a})$	$f(a_{1}^{x,d})$	$f(d_{2}^{x,d})$
$3$	$4$	$5$	$6$
$f(a_{1}^{y,a})$	$f(d_{2}^{y,a})$	$f(a_{1}^{y,d})$	$f(d_{2}^{y,d})$
$3$	$4$	$6$	$5$

We now analyze the possible images by $f$ for some of the remaining vertices of $(H_{3},\pi_{3})$ . First, note that, by Observation 4.1, we have the following:

Observation 4.3.

By Observation 4.1, we have:

1.

$\{f(a_{2}^{y,a}),f(d_{1}^{y,a})\}=\{1,6\}$ ,
2.

$\{f(a_{2}^{x,d}),f(d_{1}^{x,d})\}=\{2,4\}$ ,
3.

$\{f(a_{2}^{y,d}),f(d_{1}^{y,d})\}=\{1,4\}$ ,
4.

$\{f(a_{2}^{x,a}),f(d_{1}^{x,a})\}=\{2,6\}$ .

Regarding the first item in Observation 4.3, there are two possibilities for $f$ , namely either $(f(a_{2}^{y,a}),f(d_{1}^{y,a}))=(1,6)$ , or conversely $(f(a_{2}^{y,a}),f(d_{1}^{y,a}))=(6,1)$ . In the next two lemmas, we analyze the consequences on $f$ of being in one case or the other.

Lemma 4.4.

If $f(a_{2}^{y,a})=1$ and $f(d_{1}^{y,a})=6$ , then we have the following images by $f$ :

$f(a_{2}^{x,a})$	$f(d_{1}^{x,a})$	$f(a_{2}^{x,d})$	$f(d_{1}^{x,d})$
$6$	$2$	$2$	$4$
$f(a_{2}^{y,a})$	$f(d_{1}^{y,a})$	$f(a_{2}^{y,d})$	$f(d_{1}^{y,d})$
$1$	$6$	$1$	$4$

Proof.

If $f(d_{1}^{x,d})=2$ , then the positive cycle $a_{2}^{y,a}ya_{1}^{y,a}aa_{2}^{y,a}$ and the negative cycle $xd_{1}^{x,d}da_{1}^{x,d}x$ of $(H_{3},\pi_{3})$ have the same image $12351$ by $f$ , which is a contradiction. Therefore, $f(a_{2}^{x,d})=2$ and $f(d_{1}^{x,d})=4$ . Also, if $f(a_{2}^{y,d})=4$ , then the negative cycle $xd_{1}^{x,d}da_{2}^{y,d}ya_{2}x$ has image $1434241$ by $f$ , which is a positive closed walk in $(T,\lambda)$ , a contradiction. From this, we deduce that $f(a_{2}^{y,d})=1$ and $f(d_{1}^{y,d})=4$ . Finally, if $f(a_{2}^{x,a})=2$ , then the positive cycle $xa_{2}^{x,a}aa_{1}^{x,a}x$ and the negative cycle $a_{2}^{y,d}yd_{2}^{y,d}da_{2}^{y,d}$ have the same image $12531$ by $f$ , a contradiction. Therefore, $f(a_{2}^{x,a})=6$ and $f(d_{1}^{x,a})=2$ . ∎

Lemma 4.5.

If $f(a_{2}^{y,a})=6$ and $f(d_{1}^{y,a})=1$ , then we have the following images by $f$ :

$f(a_{2}^{x,a})$	$f(d_{1}^{x,a})$	$f(a_{2}^{x,d})$	$f(d_{1}^{x,d})$
$2$	$6$	$4$	$2$
$f(a_{2}^{y,a})$	$f(d_{1}^{y,a})$	$f(a_{2}^{y,d})$	$f(d_{1}^{y,d})$
$6$	$1$	$4$	$1$

Proof.

If $f(a_{2}^{x,d})=2$ , then the positive cycle $xa_{2}^{x,d}da_{1}^{x,d}x$ and the negative cycle $d_{1}^{y,a}ya_{1}^{y,a}ad_{1}^{y,a}$ of $(H_{3},\pi_{3})$ have the same image $12351$ by $f$ , which is not possible. Therefore, $f(a_{2}^{x,d})=4$ and $f(d_{1}^{x,d})=2$ . Now, if $f(d_{1}^{y,d})=4$ , then the negative cycle $xa_{2}^{x,d}dd_{1}^{y,d}ya_{2}x$ has image $1434241$ by $f$ , which is a positive closed walk in $(T,\lambda)$ , a contradiction from which we deduce $f(a_{2}^{y,d})=4$ and $f(d_{1}^{y,d})=1$ . Similarly, if $f(a_{2}^{x,a})=6$ , then the negative cycle $xd_{2}ya_{2}^{y,a}aa_{2}^{x,a}x$ has image $1626561$ by $f$ , which is a positive closed walk in $(T,\lambda)$ , a contradiction. Then we deduce that $f(a_{2}^{x,a})=2$ and $f(d_{1}^{x,a})=6$ . ∎

From Lemmas 4.4 and 4.5, we get that there are, thus far, two possible partial extensions for $f$ . We denote by $f_{1}$ the one described in the statement of Lemma 4.4, and by $f_{2}$ the one described in the statement of Lemma 4.5.

Let $\{i_{1},\dots,i_{6}\}=\{1,\dots,6\}$ . In the signed graph $(T,\lambda)$ , if two vertices $i_{1},i_{2}$ agree on two vertices $i_{3},i_{4}$ and disagree on $i_{5},i_{6}$ , then we say that $\{i_{1},i_{2}\}$ is a splitter that yields two teams $\{i_{3},i_{4}\}$ and $\{i_{5},i_{6}\}$ . Naturally, in this case, $i_{3}$ is in the same team as $i_{4}$ , that is opposite to the team of $i_{5}$ and $i_{6}$ . Observe that no matter how we switch vertices in $(T,\lambda)$ , the pair $\{i_{1},i_{2}\}$ remains a splitter yielding the same two teams. Upon switching vertices, it may happen that $i_{1},i_{2}$ get to disagree on $i_{3},i_{4}$ and to agree on $i_{5},i_{6}$ – but the fact that $\{i_{1},i_{2}\}$ yields teams $\{i_{3},i_{4}\}$ and $\{i_{5},i_{6}\}$ cannot be lost.

Having a closer look, in $(H_{3},\pi_{3})$ , at the images by $f$ , observe that $x$ and $y$ must agree on $a_{1}$ and $a_{2}$ and disagree on $d_{1}$ and $d_{2}$ . The images by $f$ of $x$ and $y$ thus imply that, in $(T,\lambda)$ , the pair $\{1,2\}$ is a splitter yielding teams $\{3,4\}$ and $\{5,6\}$ . Moreover, because $f(a)=5$ and there is a copy of $(H,\pi)$ pinned to $(x,a)$ , then, in $(T,\lambda)$ , the pair $\{1,5\}$ must be a splitter. Similarly, because $f(d)=3$ , the pair $\{1,3\}$ must also be a splitter. Thus, vertex $1$ is part of at least three distinct splitters. We actually need to show something stronger.

Lemma 4.6.

Every vertex of $(T,\lambda)$ is part of at least four distinct splitters.

Proof.

Let $(H_{4},\pi_{4})$ be the triangle-free planar signed graph obtained by pinning one copy of $(H,\pi)$ to each of the eight pairs $(a_{1}^{x,a},a_{2}^{x,a})$ , $(d_{1}^{x,a},d_{2}^{x,a})$ , $(a_{1}^{x,d},a_{2}^{x,d})$ , $(d_{1}^{x,d},d_{2}^{x,d})$ , $(a_{1}^{y,a},a_{2}^{y,a})$ , $(d_{1}^{y,a},d_{2}^{y,a})$ , $(a_{1}^{y,d},a_{2}^{y,d})$ and $(d_{1}^{y,d},d_{2}^{y,d})$ of vertices of $(H_{3},\pi_{3})$ . Consider an extension of $f$ to $(H_{4},\pi_{4})$ . Note that if $f$ is extended so that it matches $f_{1}$ , then the copy of $(H,\pi)$ pinned on $(a_{1}^{y,d},a_{2}^{y,d})$ implies that $\{1,6\}$ is a splitter. If $f$ is extended so that it matches $f_{2}$ , then the copy of $(H,\pi)$ pinned on $(d_{1}^{y,a},d_{2}^{y,a})$ implies that $\{1,4\}$ is a splitter. Earlier, we have already pointed out that $\{1,2\},\{1,3\}$ and $\{1,5\}$ are splitters. Therefore, because $(H_{4},\pi_{4})$ verifies $f(x)=1$ , we get that vertex $1$ must be part of at least four splitters.

Let now $(H_{5},\pi_{5})$ be the triangle-free planar signed graph obtained by starting from $(H_{0},\pi_{0})$ and, for each of its vertices $u$ , adding a copy of $(H_{4},\pi_{4})$ and identifying $u$ and the vertex $x$ of that copy. Then, for every homomorphism $(H_{5},\pi_{5})\rightarrow(T,\lambda)$ and for every $i\in V(T)$ , there is a copy of $(H_{4},\pi_{4})$ in $(H_{5},\pi_{5})$ for which the image of $x$ is $i$ . This completes the proof. ∎

In what follows, we prove that if some vertex of $(T,\lambda)$ is part of five distinct splitters, then $(T,\lambda)$ must be isomorphic to $(SP_{5}^{+},\square^{+})$ , in which case we are done.

Lemma 4.7.

If a vertex of $(T,\lambda)$ is part of five distinct splitters, then $(T,\lambda)$ is isomorphic to $(SP_{5}^{+},\square^{+})$ .

Proof.

Without loss of generality, assume that, in $(T,\lambda)$ , vertex $6$ is part of five distinct splitters. Switch the $-$ -neighbors of vertex $6$ so that all its incident edges get positive. Because the set $\{i,6\}$ is a splitter for every $i\in\{1,2,3,4,5\}$ , we deduce that every vertex $i$ must be incident to exactly two positive edges and two negative edges in $(T-6,\lambda)$ , the signed graph obtained from $(T,\lambda)$ by deleting vertex $6$ . Then, the vertices in $\{1,2,3,4,5\}$ and their incident positive edges must induce a $2$ -regular graph. Since the only $2$ -regular (simple) graph of order $5$ is the $5$ -cycle, we get the desired conclusion. ∎

Now assume that no vertex of $(T,\lambda)$ is part of five distinct splitters. We prove that, under that assumption, $(T,\lambda)$ must be one of two possible signed graphs, $(K_{6},M)$ and $(K_{6},\overline{M})$ , defined as follows. Let $M$ be a perfect matching of $K_{6}$ , the complete graph of order $6$ . The signed graph $(K_{6},M)$ is the signed $K_{6}$ in which the set of negative edges is precisely $M$ . The signed graph $(K_{6},\overline{M})$ is the signed $K_{6}$ in which the set of negative edges is the set $\overline{M}=E(K_{6})\setminus M$ of the edges that are not in $M$ .

Lemma 4.8.

If no vertex of $(T,\lambda)$ is part of five distinct splitters, then $(T,\lambda)$ is isomorphic to $(K_{6},M)$ or $(K_{6},\overline{M})$ .

Proof.

In this case, each vertex of $(T,\lambda)$ is part of exactly four distinct splitters. Let us switch the $-$ -neighbors of vertex $6$ to make all its incident edges positive. Let $(T-6,\lambda)$ be the signed graph obtained from $(T,\lambda)$ by deleting vertex $6$ . Note that the subgraph $T^{+}$ induced by the positive edges of $(T-6,\lambda)$ must have exactly four vertices of degree $2$ . By the Handshaking Lemma, the fifth vertex $j$ must then have even degree, hence has degree $0$ or $4$ . If $j$ has degree $0$ , then $T^{+}$ is the disjoint union of a singleton vertex and a $4$ -cycle. In this case, by switching $j$ in $(T,\lambda)$ we get the signed graph $(K_{6},M)$ . Now, if $j$ has degree $4$ , then $T^{+}$ is the $1$ -clique-sum of two $3$ -cycles. In this case, by switching vertex $6$ and $j$ in $(T,\lambda)$ , we obtain the signed graph $(K_{6},\overline{M})$ . ∎

We complete the proof by showing that it is actually not possible for $(T,\lambda)$ to be isomorphic to $(K_{6},M)$ or to $(K_{6},\overline{M})$ , a contradiction with the previous lemma.

Lemma 4.9.

$(T,\lambda)$ cannot be isomorphic to $(K_{6},M)$ or $(K_{6},\overline{M})$ .

Proof.

Note that if $(T,\lambda)$ is isomorphic to $(K_{6},M)$ or $(K_{6},\overline{M})$ , then, for every vertex $i$ of $(T,\lambda)$ , there exists exactly one other vertex $j$ such that $\{i,j\}$ is not a splitter. Let us consider the two possibilities, $f_{1}$ and $f_{2}$ , for $f$ to be extended in $(H_{3},\pi_{3})$ .

First, assume that $f$ is partially extended as $f_{1}$ . The three sets (of cardinality $2$ ) of vertices of $(T,\lambda)$ that are not splitters are $\{1,4\}$ , $\{2,6\}$ and $\{3,5\}$ . Therefore, if $(T,\lambda)$ is isomorphic to $(K_{6},M)$ , then its three negative edges are $14$ , $26$ and $35$ . Analogously, if $(T,\lambda)$ is isomorphic to $(K_{6},\overline{M})$ , then its three positive edges are $14$ , $26$ and $35$ . Now, looking at the structure of $(K_{6},M)$ or $(K_{6},\overline{M})$ , the splitter $\{1,3\}$ yields the two teams $\{2,6\}$ and $\{4,5\}$ . Let us now look further at the images of the vertices of $(H_{3},\pi_{3})$ by $f_{1}$ . We know that $f_{1}(x)=1$ and $f_{1}(d)=3$ . Moreover, we know that $x$ and $d$ agree on $a_{1}^{x,d}$ and $a_{2}^{x,d}$ and disagree on $d_{1}^{x,d}$ and $d_{2}^{x,d}$ . Because $f_{1}(a_{1}^{x,d})=5$ , $f_{1}(a_{2}^{x,d})=2$ , $f_{1}(d_{1}^{x,d})=4$ and $f_{1}(d_{2}^{x,d})=6$ , we can conclude that the splitter $\{1,3\}$ yields the two teams $\{2,5\}$ and $\{4,6\}$ , which is a contradiction. Thus if $f$ is extended as $f_{1}$ , then $(T,\lambda)$ must be isomorphic to $(SP_{5}^{+},\square^{+})$ .

Second, assume that $f$ is partially extended as $f_{2}$ . In this case, the three sets (of cardinality $2$ ) of vertices of $(T,\lambda)$ that are not splitters are $\{1,6\}$ , $\{2,4\}$ and $\{3,5\}$ . This implies that the splitter $\{1,3\}$ yields the two teams $\{2,4\}$ and $\{5,6\}$ . However, in $(H_{3},\pi_{3})$ , we have $f_{2}(x)=1$ , $f_{2}(d)=3$ , $f_{2}(a_{1}^{x,d})=5$ , $f_{2}(a_{2}^{x,d})=4$ , $f_{2}(d_{1}^{x,d})=2$ and $f_{2}(d_{2}^{x,d})=6$ . From these images, we conclude that the splitter $\{1,3\}$ yields the two teams $\{4,5\}$ and $\{2,6\}$ , which is a contradiction. Thus if $f$ is extended as $f_{2}$ , then, again, $(T,\lambda)$ must be isomorphic to $(SP_{5}^{+},\square^{+})$ . ∎

5 Proof of Theorem 1.10

We start by proving the upper bounds, which we do by exploiting existing connections between signed graphs and acyclic colorings. Recall that an acyclic coloring of an undirected graph $G$ is a proper vertex-coloring such that the subgraph induced by any two distinct colors is acyclic, i.e., is a forest. The acyclic chromatic number $\chi_{a}(G)$ of $G$ is the minimum $k$ such that $G$ admits an acyclic $k$ -coloring.

Proof of Theorem 1.10(i)..

It was proved in [18] that $\chi_{a}(G)\leq 5{n-1\choose 2}$ holds for every graph $G\in\mathcal{F}_{n}$ . Furthermore, given a signed graph $(G,\sigma)$ , it is also known that if $\chi_{a}(G)\leq k$ , then $\chi_{s}((G,\sigma))\leq k2^{k-2}$ (see [19]) and $\chi_{sp}((G,\sigma))\leq k2^{k-1}$ (see [1]). Combining these bounds yields the desired upper bounds. ∎

We say that a family $\mathcal{F}$ of graphs is complete if for every finite collection $\mathcal{C}=\{G_{1},\dots,G_{t}\}$ of graphs from $\mathcal{F}$ , the graph obtained by taking the disjoint union of all graphs of $\mathcal{C}$ also belongs to $\mathcal{F}$ .

Lemma 5.1.

Every complete family $\mathcal{F}$ of graphs has an sp-bound of order $\chi_{sp}(\mathcal{F})$ and a bound of order $\chi_{s}(\mathcal{F})$ .

Proof.

Suppose $\mathcal{F}$ does not have an sp-bound of order $n=\chi_{sp}(\mathcal{F})$ . Let $\mathcal{S}$ be the set of all signatures of $K_{n}$ . Since $\mathcal{F}$ does not have any sp-bound of order $n$ , for each $\pi\in\mathcal{S}$ there exists a $(G_{\pi},\sigma_{\pi})$ that does not admit an sp-homomorphism to $(K_{n},\pi)$ . Let $(G,\sigma)$ be the signed graph containing $(G_{\pi},\sigma_{\pi})$ as a subgraph for all $\pi\in\mathcal{S}$ . That is, $(G,\sigma)$ is the disjoint union of all possible $(G_{\pi},\sigma_{\pi})$ ’s, where $\pi$ runs across $\mathcal{S}$ . Observe that $G\in\mathcal{F}$ . Furthermore, note that $(G,\sigma)$ does not admit an sp-homomorphism to $(K_{n},\pi)$ for any $\pi\in\mathcal{S}$ . Thus $\chi_{sp}((G,\pi))>n$ , a contradiction.

The proof for the existence of a bound of order $\chi_{s}(\mathcal{F})$ is similar. ∎

With Lemma 5.1 on hand, we can now prove the second part of Theorem 1.10.

Proof of Theorem 1.10(ii)..

We know from [13, 19] that the result holds for $n=1,2,3,4,5$ . We prove the result for larger values of $n$ by induction. Suppose that the result holds for all $n\leq t$ where $t\geq 5$ is odd. We show that the result holds for $n=t+1$ and $n=t+2$ .

We first prove the result for $n=t+1$ . Consider the following construction. Given a signed graph $(G,\sigma)$ , take two disjoint copies $(G_{1},\sigma_{1})$ and $(G_{2},\sigma_{2})$ of $(G,\sigma)$ , add a new vertex $\infty$ , and make every vertex of $(G_{1},\sigma_{1})$ adjacent to $\infty$ via a positive edge and every vertex of $(G_{2},\sigma_{2})$ adjacent to $\infty$ via a negative edge. We denote the so-obtained signed graph by $(G^{*},\sigma^{*})$ . Observe that

\chi_{sp}((G^{*},\sigma^{*}))=2\chi_{sp}((G,\sigma))+1.

(1)

Indeed, if $(G,\sigma)\xrightarrow{sp}(H,\pi)$ with $|V(H)|=\chi_{sp}((G,\sigma))$ , then $(G^{*},\sigma^{*})\xrightarrow{sp}(H^{*},\pi^{*})$ , which ensures that $\chi_{sp}((G^{*},\sigma^{*}))\leq|V(H^{*})|=2\chi_{sp}((G,\sigma))+1$ . For the reverse inequality, assume that there is an sp-homomorphism $f:(G^{*},\sigma^{*})\xrightarrow{sp}(H,\pi)$ . Then one of the copies of $(G,\sigma)$ in $(G^{*},\sigma^{*})$ is mapped by $f$ in $H[N^{+}(f(\infty))]$ , and the other in $H[N^{-}(f(\infty))]$ . The inequality then follows from the fact that at least one of these subgraphs has order at most $\frac{|V(H)\setminus\{\infty\}|}{2}=\frac{\chi_{sp}((G^{*},\sigma^{*}))-1}{2}$ .

Let $(H_{t},\pi_{t})$ be a signed graph with $\chi_{sp}((H_{t},\pi_{t}))\geq\frac{2^{t+1}-4}{3}$ , where $H_{t}\in\mathcal{F}_{t}$ . Let us set $(H_{t+1},\pi_{t+1})=(H_{t}^{*},\pi_{t}^{*})$ . Note that $H_{t+1}\in\mathcal{F}_{t+1}$ ; therefore, by Equation (1), we have

	$\displaystyle\chi_{sp}((H_{t+1},\pi_{t+1}))$	$\displaystyle=2\chi_{sp}((H_{t},\pi_{t}))+1$
		$\displaystyle\geq 2\cdot\frac{2^{t+1}-4}{3}+1$
		$\displaystyle=\frac{2^{t+2}-8+3}{3}=\frac{2^{(t+1)+1}-5}{3}.$

This example implies the lower bound for the case $n=t+1$ .

We now prove the result for $n=t+2$ . First of all, consider the signed graph $(H_{t+2},\pi_{t+2})=(H_{t+1}^{*},\pi_{t+1}^{*})$ . By Equation (1) we have

	$\displaystyle\chi_{sp}((H_{t+2},\pi_{t+2}))$	$\displaystyle=2\chi_{sp}((H_{t+1},\pi_{t+1}))+1$
		$\displaystyle\geq 2\cdot\frac{2^{(t+1)+1}-5}{3}+1$
		$\displaystyle=\frac{2^{t+3}-10+3}{3}=\frac{2^{(t+2)+1}-4}{3}-1.$

Since $H_{t+2}\in\mathcal{F}_{t+2}$ , the result will hold if we can prove that we cannot have equality in the second line of the equation above. Thus, assume the contrary, i.e.,

\chi_{sp}((H_{t+1},\pi_{t+1}))=\frac{2^{(t+1)+1}-5}{3}\text{ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ }\chi_{sp}((H_{t},\pi_{t}))=\frac{2^{t+1}-4}{3}.

Now consider the following construction, similar to the ones depicted on Figures 2 and 3. Take $(H_{t+2},\pi_{t+2})$ and $|V(H_{t+2})|$ copies of $(H_{t+1}^{*},\pi_{t+1}^{*})$ . After that, for every vertex $v\in V(H_{t+2})$ , take a copy of $(H_{t+1}^{*},\pi_{t+1}^{*})$ and identify $v$ with the vertex $\infty$ . We call the resulting graph $(H^{\prime}_{t+2},\pi^{\prime}_{t+2})$ . We further enhance this construction as follows. Take the disjoint union of $(H^{\prime}_{t+2},\pi^{\prime}_{t+2})$ and of $4|E(H^{\prime}_{t+2})|$ copies of $(H_{t},\pi_{t})$ . Then, for every edge $e=uv\in E(H^{\prime}_{t+2})$ and every pair $(\alpha,\beta)\in\{+,-\}^{2}$ , take a copy of $(H_{t},\pi_{t})$ , make its vertices adjacent to $u$ through $\alpha$ -edges and to $v$ through $\beta$ -edges. We denote the resulting graph by $(H^{\prime\prime}_{t+2},\pi^{\prime\prime}_{t+2})$ .

If $\chi_{sp}(\mathcal{F}_{t+2})<\frac{2^{(t+2)+1}-4}{3}$ (contradicting the statement of the result we want to prove), then we must have

\frac{2^{(t+2)+1}-4}{3}-1>\chi_{sp}(\mathcal{F}_{t+2})\geqslant\chi_{sp}((H^{\prime\prime}_{t+2},\pi^{\prime\prime}_{t+2}))\geqslant\chi_{sp}((H_{t+2},\pi_{t+2}))=\frac{2^{(t+2)+1}-4}{3}-1.

This implies that there exists a signed graph $(T,\lambda)$ of order $\frac{2^{(t+2)+1}-4}{3}-1$ such that $(H^{\prime\prime}_{t+2},\pi^{\prime\prime}_{t+2})\xrightarrow{sp}(T,\lambda)$ . Let $f:(H^{\prime\prime}_{t+2},\pi^{\prime\prime}_{t+2})\xrightarrow{sp}(T,\lambda)$ be an sp-homomorphism. Note that $f$ is surjective, since $\chi_{sp}((H^{\prime\prime}_{t+2},\pi^{\prime\prime}_{t+2}))=\frac{2^{(t+2)+1}-4}{3}-1$ . As we also have $\chi_{sp}((H_{t+2},\pi_{t+2}))=\frac{2^{(t+2)+1}-4}{3}-1$ , we get that the vertices of the original $(H_{t+2},\pi_{t+2})$ contained in $(H^{\prime\prime}_{t+2},\pi^{\prime\prime}_{t+2})$ as a subgraph also map onto the vertices of $(T,\lambda)$ . From this, we may infer that every vertex $x$ of $(T,\lambda)$ has a copy of $(H_{t+1},\pi_{t+1})$ mapped to its $\alpha$ -neighborhood by $f$ for every $\alpha\in\{+,-\}$ . Thus every vertex $x$ of $(T,\lambda)$ must have at least $\chi_{sp}((H_{t+1},\pi_{t+1}))=\frac{2^{(t+1)+1}-5}{3}$ $\alpha$ -neighbors for every $\alpha\in\{+,-\}$ . Since $T$ has exactly

\frac{2^{(t+2)+1}-4}{3}-1=2\cdot\frac{2^{(t+1)+1}-5}{3}+1

vertices, every vertex of $(T,\lambda)$ must thus have exactly $\frac{2^{(t+1)+1}-5}{3}$ $\alpha$ -neighbors for every $\alpha\in\{+,-\}$ . Hence, $(T,\lambda)$ is a complete signed graph. Furthermore, for every edge $e=uv\in E(H_{t+2})$ of the original copy contained in $(H^{\prime\prime}_{t+2},\pi^{\prime\prime}_{t+2})$ as a subgraph and for every pair $(\alpha,\beta)\in\{+,-\}^{2}$ , there is a copy of $(H_{t},\pi_{t})$ contained in the subgraph induced by $N^{\alpha}(u)\cap N^{\beta}(v)$ . Thus, in particular, for any distinct pair of vertices $x,y$ of $(T,\lambda)$ , $N^{\alpha}(x)\cap N^{\beta}(y)$ contains at least $\chi_{sp}((H_{t},\pi_{t}))=\frac{2^{t+1}-4}{3}$ vertices for every $(\alpha,\beta)\in\{+,-\}^{2}$ .

To reach a contradiction, we count in two ways the number of $+$ -edges between $A$ and $B$ . Let $x$ be a vertex of $(T,\lambda)$ . We already know that the $+$ -neighborhood $A$ of $x$ in $(T,\lambda)$ contains exactly $\frac{2^{(t+1)+1}-5}{3}$ vertices and the $-$ -neighborhood $B$ of $x$ in $(T,\lambda)$ contains exactly $\frac{2^{(t+1)+1}-5}{3}$ vertices. Moreover, every vertex $y$ in $A$ has exactly $\frac{2^{t+1}-4}{3}$ $\alpha$ -neighbors in $A$ for every $\alpha\in\{+,-\}$ . Note that $y$ already has one $+$ -neighbor, $x$ , and $\frac{2^{t+1}-4}{3}$ $+$ -neighbors in $A$ . Hence, $y$ must have exactly

\frac{2^{(t+1)+1}-5}{3}-\frac{2^{t+1}-4}{3}-1=\frac{2^{t+1}-4}{3}

$+$ -neighbors in $B$ . Thus, there are exactly $\frac{(2^{(t+1)+1}-5)(2^{t+1}-4)}{9}$ $+$ -edges between the sets $A$ and $B$ . Similarly, every vertex $z$ in $B$ has exactly $\frac{2^{t+1}-4}{3}$ $\alpha$ -neighbors in $A$ for every $\alpha\in\{+,-\}$ . Note that $z$ already has $\frac{2^{t+1}-4}{3}$ $+$ -neighbors in $B$ . Hence, it must have exactly

\frac{2^{(t+1)+1}-5}{3}-\frac{2^{t+1}-4}{3}=\frac{2^{t+1}-1}{3}

$+$ -neighbors in $B$ . Thus, there are exactly $\frac{(2^{(t+1)+1}-5)(2^{t+1}-1)}{9}$ $+$ -edges between the sets $A$ and $B$ . This is a contradiction with the previous counting, which implies that $(T,\lambda)$ cannot exist. This concludes the proof. ∎

This leaves us with proving the very last part of Theorem 1.10.

Proof of Theorem 1.10(iii)..

If $n$ is even, Theorems 1.5 and 1.10(ii) give that

2\chi_{s}((G,\sigma))\geq\chi_{sp}((G,\sigma))\geq\frac{2^{n+1}-5}{3}.

Hence, because $\chi_{s}((G,\sigma))$ is an integer, we get

\chi_{s}((G,\sigma))\geq\left\lceil\frac{2^{n+1}-5}{6}\right\rceil=\left\lceil\frac{2^{n}-1}{3}-\frac{1}{2}\right\rceil=\frac{2^{n}-1}{3}

since $n$ is even. The case when $n$ is odd is similar. ∎

6 Proof of Theorem 1.13

Throughout this section, we say that each of the two signed graphs $(K_{4},\emptyset)$ (having positive edges only) and $(K_{4},E(K_{4}))$ (having negative edges only) is a bad $K_{4}$ , while every other signature of $K_{4}$ gives a good $K_{4}$ .

We first observe that $(SP_{5}^{+},\square^{+})$ contains a copy of each good $K_{4}$ .

Observation 6.1.

If $(K_{4},\Sigma)$ is not bad, then $(K_{4},\Sigma)\rightarrow(SP_{5}^{+},\square^{+})$ .

Proof.

Given a signature $\Sigma$ of $K_{4}$ , one can switch some vertices to obtain an equivalent signature $\Sigma^{\prime}$ in which some vertex $v$ has its three incident edges being positive. If $(K_{4},\Sigma)$ is not bad, then the signed graph obtained by deleting $v$ from $(K_{4},\Sigma^{\prime})$ does not have only positive edges or only negative edges and hence can be found in $(SP_{5},\square)$ . Therefore $(SP_{5}^{+},\square^{+})$ contains $(K_{4},\Sigma^{\prime})$ as a subgraph, where $v$ is mapped to $\infty$ . ∎

In this section, we want to show that the family of all signed subcubic graphs with no bad $K_{4}$ as a connected component, admits a homomorphism to $(SP_{5}^{+},\square^{+})$ . The proof is by contradiction. Suppose there exists a signed subcubic graph with no bad $K_{4}$ as a connected component, that does not admit a homomorphism to $(SP_{5}^{+},\square^{+})$ . We focus on $(G,\sigma)$ , a counterexample that is minimal in terms of order. That is, every signed subcubic graph with fewer vertices than $(G,\sigma)$ admits a homomorphism to $(SP_{5}^{+},\square^{+})$ . Our goal is to show that $(G,\sigma)$ cannot exist, a contradiction. This is done by investigating properties of $(G,\sigma)$ , and considering homomorphisms to $(SP_{5}^{+},\square^{+})$ (depicted in Figure 1(a)).

By minimality, we observe that $(G,\sigma)$ is connected. Also, $G\neq K_{4}$ (by Observation 6.1). We start off by showing that $(G,\sigma)$ cannot have cut-vertices.

Lemma 6.2.

$(G,\sigma)$ is $2$ -connected.

Proof.

Assume that $(G,\sigma)$ has a cut-vertex $v$ . Then, removing $v$ from $(G,\sigma)$ results in at least two connected components. Assume that $(G_{1},\sigma_{1})$ is one such connected component, and $(G_{2},\sigma_{2})$ is the disjoint union of all the other connected components. Let $(G_{1}^{\prime},\sigma_{1}^{\prime})$ be the signed graph obtained by putting the vertex $v$ back in $(G_{1},\sigma_{1})$ , and let $(G_{2}^{\prime},\sigma_{2}^{\prime})$ be the signed graph obtained by putting the vertex $v$ back in $(G_{2},\sigma_{2})$ . Note that none of these two signed graphs is cubic, and, thus, none of them can be a bad $K_{4}$ . By minimality of $(G,\sigma)$ , there are $f_{1}:(G_{1}^{\prime},\sigma_{1}^{\prime})\rightarrow(SP_{5}^{+},\square^{+})$ and $f_{2}:(G_{2}^{\prime},\sigma_{2}^{\prime})\rightarrow(SP_{5}^{+},\square^{+})$ . Due to the vertex-transitivity of $(SP_{5}^{+},\square^{+})$ , we may assume $f_{1}(v)=f_{2}(v)$ . Now, combining $f_{1}$ and $f_{2}$ yields a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ , a contradiction. ∎

Through the next result, we aim at reducing $(G,\sigma)$ to a cubic graph. Note that $(G,\sigma)$ has no vertex of degree 1 since it is 2-connected.

Lemma 6.3.

$(G,\sigma)$ does not contain a vertex of degree $2$ .

Proof.

Suppose the contrary, i.e., assume that $(G,\sigma)$ contains a degree- $2$ vertex $u$ with neighbors $v$ and $w$ . Let $(G^{\prime},\sigma^{\prime})$ be the signed graph obtained from $(G,\sigma)$ by deleting $u$ and adding the edge $vw$ (if it was not already present).

Observe that if $vw$ was already present in $(G,\sigma)$ , then it is not possible for $(G^{\prime},\sigma^{\prime})$ to be isomorphic to a bad $K_{4}$ since $v$ and $w$ have now degree 2 in $G^{\prime}$ . In case we do add the edge $vw$ , we choose its sign in such a way we do not create any bad $K_{4}$ . This means that if $G^{\prime}$ is isomorphic to $K_{4}$ , then we choose the sign of $vw$ so that one of the $4$ -cycles of $(G^{\prime},\sigma^{\prime})$ becomes negative. Otherwise, we assign any sign to $vw$ in $(G^{\prime},\sigma^{\prime})$ .

In all cases, $(G^{\prime},\sigma^{\prime})$ cannot be a bad $K_{4}$ , and, hence, by minimality of $(G,\sigma)$ , there exists $f:(G^{\prime},\sigma^{\prime})\rightarrow(SP_{5}^{+},\square^{+})$ . Because $vw$ is an edge, we know that $f(v)\neq f(w)$ . Note that this $f$ also stands as a homomorphism of $(G-u,\sigma)$ to $(SP_{5}^{+},\square^{+})$ . Now, since $(SP_{5}^{+},\square^{+})$ has property $\hat{P}_{2,2}$ according to Proposition 2.2, we can extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ , a contradiction. ∎

(a)

(b)

(c)

(d)

Figure 5: Configurations reduced for proving Theorem 1.13. Black vertices are vertices having their whole neighborhood being part of the configuration. White vertices may have neighbors not depicted in the configuration.

Thus, from now on we can assume that $(G,\sigma)$ is cubic. To finish off the proof, we prove that $G$ cannot contain any of the configurations depicted in Figure 5. Throughout the rest of this section, whenever dealing with one of these configurations, we do so by employing the terminology given in the figure. It is important to emphasize that, in these configurations, white vertices are vertices that can have neighbors outside the configuration, while the whole neighborhood of the black vertices is as displayed in the configuration. In particular, some of the white vertices could be the same vertices, or be adjacent to each other.

We proceed with the configuration depicted in Figure 5(a).

Lemma 6.4.

$(G,\sigma)$ does not contain the configuration depicted in Figure 5(a).

Proof.

Suppose the contrary, i.e., assume that $(G,\sigma)$ contains the configuration depicted in Figure 5(a). Let $(G^{\prime},\sigma^{\prime})$ be the signed graph obtained from $(G,\sigma)$ by deleting the vertices $v_{3}$ , $v_{4}$ , $v_{5}$ and $v_{6}$ and adding the edge $v_{1}v_{2}$ (if it was not already present). In case $v_{1}v_{2}$ does not exist in $(G,\sigma)$ , then, in $(G^{\prime},\sigma^{\prime})$ , just as in the proof of Lemma 6.3, we choose the sign of $v_{1}v_{2}$ so that $(G^{\prime},\sigma^{\prime})$ is not a bad $K_{4}$ . Thus, by minimality there exists a homomorphism $f:(G^{\prime},\sigma)\rightarrow(SP_{5}^{+},\square^{+})$ . Because $(SP_{5}^{+},\square^{+})$ is edge-transitive, without loss of generality we may assume $f(v_{1})=\infty$ and $f(v_{2})=\overline{1}$ . Besides, if needed, we can switch some vertices of $(G,\sigma)$ to ensure

\sigma(v_{1}v_{3})=\sigma(v_{3}v_{5})=\sigma(v_{4}v_{5})=\sigma(v_{5}v_{6})=+.

More precisely, we first switch $v_{3}$ if $\sigma(v_{1}v_{3})=-$ , then switch $v_{5}$ if $\sigma(v_{3}v_{5})=-$ , then switch $v_{4}$ if $\sigma(v_{4}v_{5})=-$ , and finally switch $v_{6}$ in case $\sigma(v_{5}v_{6})=-$ .

We first set $f(v_{5})=\infty$ . We now choose $\overline{i},\overline{j},\overline{k}\in V(SP_{5}^{+})\setminus\{\infty\}$ so that $\overline{i}$ is a $\sigma(v_{2}v_{4})$ -neighbor of $f(v_{2})=\overline{1}$ , $\overline{j}$ is a $\sigma(v_{4}v_{6})$ -neighbor of $\overline{i}$ , and $\overline{k}$ is a $\sigma(v_{3}v_{6})$ -neighbor of $\overline{j}$ . Now, setting $f(v_{4})=\overline{i}$ , $f(v_{6})=\overline{j}$ and $f(v_{3})=\overline{k}$ , extends $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ , a contradiction. ∎

Before proceeding with the next configuration, we first need to state a useful observation that deals with signatures $(P_{3},\sigma)$ of the $3$ -path $P_{3}=u_{1}u_{2}u_{3}u_{4}$ .

Observation 6.5.

Let $g$ be a partial function of $V(P_{3})$ to $V(SP_{5})$ where only $u_{1}$ and $u_{4}$ get an image by $g$ . Assume $g(u_{1})=\overline{i}$ and $g(u_{4})=\overline{j}$ for some $\overline{i},\overline{j}\in V(SP_{5})$ . Then, regardless of $\overline{i}$ and $\overline{j}$ , it is possible to extend $g$ to an sp-homomorphism of $(P_{3},\sigma)$ to $(SP_{5},\square)$ unless $\sigma(u_{1}u_{2})=\sigma(u_{2}u_{3})=\sigma(u_{3}u_{4})$ and $\overline{i}=\overline{j}$ .

Proof.

Due to the transitivity properties of $(SP_{5},\square)$ , it is sufficient to focus on the cases where $g(u_{1})=\overline{1}$ and $g(u_{4})\in\{\overline{1},\overline{2},\overline{3}\}$ . Figure 6 illustrates the main cases to consider. The first row displays the cases where $g(u_{4})=\overline{1}$ , the second and third rows display the cases where $g(u_{4})=\overline{2}$ , and the fourth and fifth rows display the cases where $g(u_{4})=\overline{3}$ . ∎

Figure 6: All cases for the proof of Observation 6.5. Solid edges are positive edges. Dashed edges are negative edges.

Lemma 6.6.

$(G,\sigma)$ does not contain the configuration depicted in Figure 5(b).

Proof.

Suppose the contrary, i.e., assume that $(G,\sigma)$ contains the configuration depicted in Figure 5(b). Because $(G,\sigma)$ does not contain the configuration depicted in Figure 5(a) according to Lemma 6.4, note that the vertices $v_{1}$ , $v_{2}$ and $v_{3}$ must be distinct. Let $(G^{\prime},\sigma^{\prime})$ be the signed graph obtained from $(G,\sigma)$ by deleting the vertices $v_{4}$ , $v_{5}$ and $v_{6}$ and adding the edge $v_{1}v_{2}$ (if it was not already present). In case we do add this edge $v_{1}v_{2}$ to $(G^{\prime},\sigma^{\prime})$ , then, as earlier, we choose its sign so that, in case $G^{\prime}=K_{4}$ , the signed graph $(G^{\prime},\sigma^{\prime})$ is not a bad $K_{4}$ . Then, by minimality, there is a homomorphism $f:(G^{\prime},\sigma^{\prime})\rightarrow(SP_{5}^{+},\square^{+})$ . Since $(SP_{5}^{+},\square^{+})$ is transitive, we may assume that $f(v_{3})\neq\infty$ . Moreover, since $(SP_{5}^{+}-\infty,\square^{+})=(SP_{5},\square)$ is sp-edge-transitive and sp-isomorphic to $(SP_{5},V(SP_{5})\setminus\square)$ , we may assume that $f(v_{1})=\overline{1}$ and $f(v_{2})=\overline{2}$ . Finally, we may (if needed) switch some vertices of the configuration so that

\sigma(v_{1}v_{4})=\sigma(v_{4}v_{5})=\sigma(v_{4}v_{6})=+.

By Observation 6.5, we can extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ unless $f(v_{3})=\overline{2}$ and $\sigma(v_{2}v_{5})=\sigma(v_{5}v_{6})=\sigma(v_{3}v_{6})$ . This leads us to the following two cases:

1.

$f(v_{3})=\overline{2}$ and $\sigma(v_{2}v_{5})=\sigma(v_{5}v_{6})=\sigma(v_{3}v_{6})=+$ .

In this case, we set $f(v_{4})=\overline{2}$ in $(G^{\prime},\sigma^{\prime})$ . The homomorphism can then be extended to $(G,\sigma)$ by setting $f(v_{5})=\overline{3}$ and $f(v_{6})=\infty$ .
2.

$f(v_{3})=\overline{2}$ and $\sigma(v_{2}v_{5})=\sigma(v_{5}v_{6})=\sigma(v_{3}v_{6})=-$ .

In this case, in $(G^{\prime},\sigma^{\prime})$ we first switch $v_{4}$ and $v_{6}$ before setting $f(v_{4})=\overline{3}$ . The homomorphism can then be extended to $(G,\sigma)$ by setting $f(v_{5})=\overline{5}$ and $f(v_{6})=\infty$ .

In all cases, it is thus possible to extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ . This is a contradiction. ∎

In order to reduce the next configuration, we need the following:

Observation 6.7.

For every two distinct $\overline{i},\overline{j}$ in $V(SP_{5})$ and $\{\alpha,\beta\}=\{+,-\}$ , we have $N^{\alpha}(\overline{i})\cap N^{\beta}(\overline{j})\neq\emptyset$ .

Proof.

Due to the structure of $SP_{5}$ , it is sufficient to prove the statement for $\overline{i}=\overline{1}$ and $\overline{j}\in\{\overline{2},\overline{3}\}$ . In both cases we have $N^{+}(\overline{1})\cap N^{-}(\overline{j})=\{\overline{5}\}$ and $N^{-}(\overline{1})\cap N^{+}(\overline{j})=\{\overline{j+1}\}$ ∎

Lemma 6.8.

$(G,\sigma)$ does not contain the configuration depicted in Figure 5(c).

Proof.

Suppose the contrary, i.e., assume that $(G,\sigma)$ contains the configuration depicted in Figure 5(c). As $(G,\sigma)$ does not contain the configuration depicted in Figure 5(b) according to Lemma 6.6, the vertices $v_{1}$ and $v_{2}$ must be distinct in $(G,\sigma)$ , and similarly for the vertices $v_{3}$ and $v_{4}$ . Let $(G^{\prime},\sigma^{\prime})$ be the signed graph obtained from $(G,\sigma)$ by deleting the vertices $v_{5}$ , $v_{6}$ , $v_{7}$ and $v_{8}$ and adding the edge $v_{1}v_{2}$ and $v_{3}v_{4}$ (if they were not already present). As before, we choose the sign of each edge we add in such a way that $(G^{\prime},\sigma^{\prime})$ is not a bad $K_{4}$ . This way, by minimality, there is a homomorphism $f:(G^{\prime},\sigma^{\prime})\rightarrow(SP_{5}^{+},\square^{+})$ . We know that $f(v_{1})\neq f(v_{2})$ and $f(v_{3})\neq f(v_{4})$ . This brings us to two cases without loss of generality.

1.

$f(v_{3})\notin\{f(v_{1}),f(v_{2})\}$ .

Without loss of generality, we may assume $f(v_{1})=\overline{1}$ and $f(v_{3})=\infty$ . Assume that $f(v_{2})=\overline{j}$ for some $\overline{j}\not\in\{\infty,\overline{1}\}$ . Start by switching some of $v_{5},v_{6},v_{7},v_{8}$ (if needed) to make sure that

$\sigma(v_{1}v_{5})=\sigma(v_{5}v_{6})=\sigma(v_{3}v_{7})=\sigma(v_{5}v_{8})=+.$

Set $f(v_{5})=\infty$ . Now, choose some $\overline{i}\in N^{\sigma(v_{4}v_{8})}(f(v_{4}))\setminus\{\infty,\overline{j}\}$ and set $f(v_{8})=\overline{i}$ . According to Observation 6.5, there is an sp-homomorphism $g$ of the signed path induced by the vertices $v_{2},v_{6},v_{7},v_{8}$ such that $g(v_{2})=\overline{j}$ and $g(v_{8})=\overline{i}$ . We can now extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ by setting $f(v_{6})=g(v_{6})$ and $f(v_{7})=g(v_{7})$ .
2.

$f(v_{3})\in\{f(v_{1}),f(v_{2})\}$ . Up to the left/right symmetry, we may also assume that $f(v_{4})\in\{f(v_{1}),f(v_{2})\}$ , i.e. $\{f(v_{1}),f(v_{2})\}=\{f(v_{3}),f(v_{4})\}$ .

We here consider two subcases:
1. (a)
  
  $f(v_{1})=f(v_{3})$ and $f(v_{2})=f(v_{4})$ .
  
  Without loss of generality, assume $f(v_{1})=f(v_{3})=\infty$ and $f(v_{2})=f(v_{4})=\overline{1}$ . Start by switching $v_{5},v_{7}$ (if needed) to make sure that
  
  $\sigma(v_{1}v_{5})=\sigma(v_{3}v_{7})=+.$
  - i.
    
    If the cycle $v_{5}v_{6}v_{7}v_{8}v_{5}$ is positive, then switch $v_{6}$ (if needed) to make sure that $\sigma(v_{5}v_{6})\neq\sigma(v_{5}v_{8})$ and $\sigma(v_{6}v_{7})\neq\sigma(v_{7}v_{8})$ . Now choose $\overline{i}\in N^{\sigma(v_{2}v_{6})}(\overline{1})\setminus\{\infty\}$ , $\overline{j}\in N^{\sigma(v_{4}v_{8})}(\overline{1})\setminus\{\infty,\overline{i}\}$ and set $f(v_{6})=\overline{i}$ and $f(v_{8})=\overline{j}$ . According to Observation 6.7, there is a way to extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ by correctly setting $f(v_{5}),f(v_{7})$ .
  - ii.
    
    If the cycle $v_{5}v_{6}v_{7}v_{8}v_{5}$ is negative, then switch some of $v_{6},v_{8}$ (if needed) to make sure that $\sigma(v_{2}v_{6})=+$ and $\sigma(v_{4}v_{8})=-$ . Up to exchanging $(v_{1},v_{5})$ with $(v_{3},v_{7})$ , we may assume that $\sigma(v_{5}v_{6})\neq\sigma(v_{5}v_{8})$ and $\sigma(v_{6}v_{7})=\sigma(v_{7}v_{8})$ . On the one hand, if $\sigma(v_{6}v_{7})=\sigma(v_{7}v_{8})=+$ , then set $f(v_{6})=\overline{2}$ , $f(v_{7})=\overline{3}$ and $f(v_{8})=\overline{4}$ . On the other hand, if $\sigma(v_{6}v_{7})=\sigma(v_{7}v_{8})=-$ , then set $f(v_{6})=\overline{2}$ , $f(v_{7})=\overline{5}$ and $f(v_{8})=\overline{3}$ . Now Observation 6.7 tells us that there is a way to extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ by correctly setting $f(v_{5})$ .
2. (b)
  
  $f(v_{1})=f(v_{4})$ and $f(v_{2})=f(v_{3})$ .
  
  Without loss of generality, assume $f(v_{1})=f(v_{4})=\infty$ and $f(v_{2})=f(v_{3})=\overline{1}$ . Start by switching some of $v_{5},v_{6},v_{7},v_{8}$ (if needed) to make sure that
  
  $\sigma(v_{1}v_{5})=\sigma(v_{2}v_{6})=\sigma(v_{4}v_{8})=+$
  
  and $\sigma(v_{3}v_{7})=-$ . Set $f(v_{6})=\overline{2}$ and $f(v_{7})=\overline{3}$ if $\sigma(v_{6}v_{7})=+$ , and $f(v_{7})=\overline{4}$ otherwise. In both cases, according to Observation 6.5, there is a way to extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ by correctly setting $f(v_{5})$ and $f(v_{8})$ .

Thus, in all cases, it is possible to extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ . This is a contradiction. ∎

We need two more results to deal with the last configuration in Figure 5. The first one deals with two particular signed graphs, $(X,\varphi)$ and $(X,\varphi^{\prime})$ . Let $(X,\varphi)$ be the signed graph of order $4$ consisting of a $3$ -cycle $uvwu$ and of a vertex $x$ adjacent to $w$ , where $\varphi$ is a signature such that $uvwu$ is a positive cycle. Let $(X,\varphi^{\prime})$ be the signed graph obtained from $(X,\varphi)$ by switching the vertex $w$ .

Figure 7: All cases for the proof of Observation 6.9. Solid edges are positive edges. Dashed edges are negative edges.

Observation 6.9.

Let $g$ be a partial sp-homomorphism from $(X,\varphi)$ to $(SP_{5}^{+},\square^{+})$ , where only $u$ and $v$ have an image under $g$ . Then, up to switching the vertex $w$ , it is possible to extend $g$ to an sp-homomorphism from $(X,\varphi)$ to $(SP_{5}^{+},\square^{+})$ satisfying the following:

(a)

if $\{g(u),g(v)\}=\{\infty,\overline{i}\}$ and $\varphi(wx)=\varphi(uw)$ , then $g(x)\notin\{\overline{i-1},\overline{i+1}\}$ ;
(b)

if $\{g(u),g(v)\}=\{\infty,\overline{i}\}$ and $\varphi(wx)\neq\varphi(uw)$ , then $g(x)\notin\{\infty,\overline{i}\}$ ;
(c)

if $\{g(u),g(v)\}=\{\overline{i},\overline{i+1}\}$ and $\varphi(wx)=\varphi(uw)$ , then $g(x)\neq\infty$ ;
(d)

if $\{g(u),g(v)\}=\{\overline{i},\overline{i+1}\}$ and $\varphi(wx)\neq\varphi(uw)$ , then $g(x)\notin\{\overline{i},\overline{i+1},\overline{i+3}\}$ ;
(e)

if $\{g(u),g(v)\}=\{\overline{i},\overline{i+2}\}$ and $\varphi(wx)=\varphi(uw)$ , then $g(x)\notin\{\overline{i+2},\overline{i+4}\}$ ;
(f)

if $\{g(u),g(v)\}=\{\overline{i},\overline{i+2}\}$ and $\varphi(wx)\neq\varphi(uw)$ , then $g(x)\notin\{\overline{i},\overline{i-2}\}$ .

Proof.

Due to the symmetric structure of $(SP_{5}^{+},\square^{+})$ , it is sufficient to consider the cases depicted in Figure 7. For each considered value of $\{g(u),g(v)\}$ and $\varphi(wx),\varphi(uw)$ , we give two signatures on $X$ ( $\varphi$ and $\varphi^{\prime}$ ) and the corresponding possible values of $g(w)$ and $g(x)$ . ∎

The second result we need deals with two additional signed graphs, $(Y,\varphi)$ and $(Y,\varphi^{\prime})$ , obtained from $(X,\varphi)$ and $(X,\varphi^{\prime})$ , respectively, by adding a new vertex $y$ adjacent to $x$ through a positive edge.

Observation 6.10.

Let $g$ be a partial sp-homomorphism of $(Y,\varphi)$ to $(SP_{5}^{+},\square^{+})$ , where only $u$ , $v$ and $y$ have an image under $g$ . Then, it is possible to extend $g$ to an sp-homomorphism of $(Y,\varphi)$ or $(Y,\varphi^{\prime})$ to $(SP_{5}^{+},\square^{+})$ .

Proof.

Observe that, for $\infty$ and any other vertex in $(SP_{5}^{+},\square^{+})$ , the union of their positive neighborhoods is $V(SP_{5}^{+})$ . Moreover, note that, in $(SP_{5}^{+},\square^{+})$ , we have

\forall i\in V(SP_{5}),\quad N^{+}(\overline{i})\cup N^{+}(\overline{i+1})\cup N^{+}(\overline{i+2})=V(SP_{5}^{+}).

The result now follows from Observation 6.9. ∎

We are now ready to reduce the final configuration.

Lemma 6.11.

$(G,\sigma)$ does not contain the configuration depicted in Figure 5(d).

Proof.

Suppose the contrary, i.e., assume that $(G,\sigma)$ contains the configuration depicted in Figure 5(d). Let $(G^{\prime\prime},\sigma^{\prime\prime})$ be the signed graph obtained from $(G,\sigma)$ by adding the edges $v_{1}v_{2}$ , $v_{3}v_{4}$ , $v_{5}v_{6}$ and $v_{7}v_{8}$ . Note that these edges were not already present in $(G,\sigma)$ , since $(G,\sigma)$ cannot have $3$ -cycles according to Lemma 6.6. Also let $(G^{\prime},\sigma^{\prime})$ be the signed graph obtained from $(G^{\prime\prime},\sigma^{\prime\prime})$ by deleting the vertices $v_{9}$ , $v_{10}$ , $v_{11}$ , $v_{12}$ , $v_{13}$ and $v_{14}$ . Observe that if a connected component of $G^{\prime}$ is isomorphic to $K_{4}$ , then $G$ must have a cut-vertex, which is not possible by Lemma 6.2. Thus, we can freely choose the signs of the edges we have just added, without caring of whether a bad $K_{4}$ is created. Precisely, we assign signs to $v_{1}v_{2}$ , $v_{3}v_{4}$ , $v_{5}v_{6}$ , $v_{7}v_{8}$ in such a way that the $3$ -cycle $v_{1}v_{2}v_{9}v_{1}$ is negative, while the $3$ -cycles $v_{3}v_{4}v_{10}v_{3}$ , $v_{5}v_{6}v_{11}v_{5}$ and $v_{7}v_{8}v_{12}v_{7}$ are positive.

By minimality of $(G,\sigma)$ , there is a homomorphism $f:(G^{\prime},\sigma^{\prime})\rightarrow(SP_{5}^{+},\square^{+})$ . Because $(SP_{5}^{+},\square^{+})$ is edge-transitive, without loss of generality we may assume $f(v_{1})=\overline{1}$ and $f(v_{2})=\overline{3}$ . Note also that because the cycle $v_{1}v_{2}v_{9}v_{1}$ is negative and $v_{1}v_{2}$ is a negative edge (due to the images of $v_{1},v_{2}$ in $(SP_{5}^{+},\sigma)$ ), we can, if needed, switch $v_{9}$ to ensure $\sigma(v_{1}v_{9})=\sigma(v_{2}v_{9})=+$ . We can also switch $v_{14}$ and/or $v_{13}$ (if needed) to ensure $\sigma(v_{9}v_{14})=\sigma(v_{13}v_{14})=+$ .

Note that the signed subgraphs induced by $\{v_{3},v_{4},v_{10},v_{13}\}$ and $\{v_{5},v_{6},v_{11},v_{13}\}$ are exactly the signed graphs $(X,\varphi)$ or $(X,\varphi^{\prime})$ described in Observation 6.9. If one of them does not fall into Observation 6.9(d), then at most five values are forbidden at $f(v_{13})$ . Thus it is possible to extend $f$ to $\{v_{10},v_{11},v_{13}\}$ a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ .

Otherwise, both of them satisfy the requirements of Observation 6.9(d), and we can also extend $f$ to $\{v_{10},v_{11},v_{13}\}$ by setting (for example) $f(v_{13})=\infty$ .

Now, observe that $\{v_{7},v_{8},v_{12},v_{14},v_{13}\}$ induces the graph $Y$ . By Observation 6.10, we can extend $f$ to $\{v_{12},v_{14}\}$ regardless of the value of the values of $f(v_{7}),f(v_{8})$ and $f(v_{13})$ .

Finally, we extend $f$ to a homomorphism of $(G,\sigma)$ to $(SP_{5}^{+},\square^{+})$ by assigning $f(v_{9})=\infty$ if $f(v_{14})\neq\infty$ and $f(v_{9})=\overline{2}$ otherwise, which is a contradiction. ∎

The proof of Theorem 1.13 now follows from the fact that every subcubic graph different from $K_{4}$ must have minimum degree $1$ or $2$ , or must contain one of the configurations depicted in Figure 5. Then, the previous lemmas imply that $(G,\sigma)$ cannot exist, a contradiction.

7 Conclusion

In this work, we have investigated the signed chromatic number of particular classes of graphs, namely planar graphs, triangle-free planar graphs, $K_{n}$ -minor-free graphs, and graphs with bounded maximum degree. We have mainly considered general bounds (Theorems 1.10 and 1.13) for some of these classes, and the uniqueness of bounds (Theorems 1.8 and 1.9) for the others. While some of our results are original ones, other ones extend known results from the literature.

Most of our results yield interesting research perspectives for the future, either because they are not tight yet, or because they lead to interesting side questions. In particular, we wonder how the bounds in Theorems 1.10 and 1.11 should be sharpened. Regarding Theorem 1.13, it would be interesting to determine whether $(SP_{5}^{+},\square^{+})$ is the only bound of order $6$ for subcubic graphs. Regarding Theorems 1.8 and 1.9, it would be, more generally speaking, of prime importance to understand better the signed chromatic number of planar graphs, for which the currently best known lower and upper bounds are rather distant. An interesting more general question as well, could be to consider how the signed chromatic of a planar graph relates to its girth. That is, studying $\chi_{s}(\mathcal{P}_{g})$ for any $g\geq 3$ .

Acknowledgement

The authors were partly supported by ANR project HOSIGRA (ANR-17-CE40-0022), by IFCAM project “Applications of graph homomorphisms” (MA/IFCAM/18/39) and by the MUNI Award in Science and Humanities of the Grant Agency of Masaryk university.

References

[1] N. Alon and T. H. Marshall. Homomorphisms of edge-colored graphs and coxeter groups. Journal of Algebraic Combinatorics, 8(1):5–13, 1998.
[2] L. Beaudou, F. Foucaud, and R. Naserasr. Homomorphism bounds and edge-colourings of ${K}_{4}$ -minor-free graphs. Journal of Combinatorial Theory, Series B, 124:128–164, 2017.
[3] J. Bensmail, S. Das, S. Nandi, T. Pierron, S. Paul, S. Sen, and E. Sopena. Pushable chromatic number of graphs with degree constraints. Discrete Mathematics, 2020. arXiv preprint arXiv:1911.09909.
[4] J. Bensmail, C. Duffy, and S. Sen. Analogues of cliques for $(m,n)$ -colored mixed graphs. Graphs and Combinatorics, 33(4):735–750, 2017.
[5] J. Bensmail, S. Nandi, M. Roy, and S. Sen. Classification of edge-critical underlying absolute planar cliques for signed graphs. Australasian Journal of Combinatorics, 77(1):117–135, 2020.
[6] R. C. Brewster, F. Foucaud, P. Hell, and R. Naserasr. The complexity of signed graph and edge-coloured graph homomorphisms. Discrete Mathematics, 340(2):223–235, 2017.
[7] R. C. Brewster and T. Graves. Edge-switching homomorphisms of edge-coloured graphs. Discrete mathematics, 309(18):5540–5546, 2009.
[8] S. Das, P. Ghosh, S. Prabhu, and S. Sen. Relative clique number of planar signed graphs (accepted). Discrete Applied Mathematics.
[9] B. Guenin. Packing odd circuit covers: A conjecture. Manuscript, 2005.
[10] H. Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3):949–955, 2019.
[11] S. Laplante, R. Naserasr, and A. Sunny. Sensitivity lower bounds from linear dependencies. Electronic Colloquium on Computational Complexity (ECCC), 27:2, 2020.
[12] A. Montejano, P. Ochem, A. Pinlou, A. Raspaud, and É. Sopena. Homomorphisms of 2-edge-colored graphs. Electronic Notes in Discrete Mathematics, 30:33–38, 2008.
[13] A. Montejano, P. Ochem, A. Pinlou, A. Raspaud, and É. Sopena. Homomorphisms of 2-edge-colored graphs. Discrete Applied Mathematics, 158(12):1365 – 1379, 2010.
[14] R. Naserasr, E. Rollová, and É. Sopena. Homomorphisms of planar signed graphs to signed projective cubes. Discrete Mathematics & Theoretical Computer Science, 15(3):1–12, 2013.
[15] R. Naserasr, E. Rollová, and É. Sopena. Homomorphisms of signed graphs. Journal of Graph Theory, 79(3):178–212, 2015.
[16] R. Naserasr, S. Sen, and Q. Sun. Walk-powers and homomorphism bounds of planar signed graphs. Graphs and Combinatorics, 32(4):1505–1519, 2016.
[17] R. Naserasr, E. Sopena, and T. Zaslavsky. Homomorphisms of signed graphs: An update. European Journal of Combinatorics, 2020. To appear, arXiv preprint: arXiv:1909.05982.
[18] J. Nešetřil, P. O. de Mendez, and D. R. Wood. Characterisations and examples of graph classes with bounded expansion. European Journal of Combinatorics, 33(3):350–373, 2012.
[19] P. Ochem, A. Pinlou, and S. Sen. Homomorphisms of 2-edge-colored triangle-free planar graphs. Journal of Graph Theory, 85(1):258–277, 2017.
[20] T. Zaslavsky. Signed graphs. Discrete Applied Mathematics, 4(1):47–74, 1982.

On the signed chromatic number of some classes of graphs

Abstract

1 Introduction

1.1 Signed graphs and homomorphisms

Lemma 1.1 (Zaslavsky [20]).

Proposition 1.2 (Naserasr, Sopena, Zaslavsky [17]).

1.2 Sign-preserving homomorphisms vs. homomorphisms of signed graphs

Lemma 1.3 (Naserasr, Rollová, Sopena [15]).

Theorem 1.4 (Ochem, Pinlou, Sen [19]).

Proposition 1.5 (Naserasr, Rollová, Sopena [15]).

Theorem 1.6 (Brewster, Graves [7]).

1.3 Our contribution

Planar graphs

Theorem 1.7 (Ochem, Pinlou, Sen [19]).

Theorem 1.8.

Triangle-free planar graphs

Theorem 1.9.

KnK_{n}-minor-free graphs

Theorem 1.10.

Graphs with given maximum degree

Theorem 1.11.

Theorem 1.12.

Theorem 1.13.

2 Definitions, terminology, and preliminary results on Paley graphs

Proposition 2.1 (Ochem, Pinlou, Sen [19]).

Proposition 2.2 (Ochem, Pinlou, Sen [19]).

3 Proof of Theorem 1.8

Lemma 3.1.

Proof.

Lemma 3.2.

Proof.

Lemma 3.3.

Proof.

Observation 3.4.

Observation 3.5.

Lemma 3.6.

Proof.

Lemma 3.7.

Proof.

Lemma 3.8.

Proof.

Lemma 3.9.

Proof.

4 Proof of Theorem 1.9

Observation 4.1 (see e.g. [15], Lemma 3.10).

Lemma 4.2.

Proof.

Observation 4.3.

Lemma 4.4.

Proof.

Lemma 4.5.

Proof.

Lemma 4.6.

Proof.

Lemma 4.7.

Proof.

Lemma 4.8.

Proof.

Lemma 4.9.

Proof.

5 Proof of Theorem 1.10

Proof of Theorem 1.10(i)..

Lemma 5.1.

Proof.

Proof of Theorem 1.10(ii)..

Proof of Theorem 1.10(iii)..

6 Proof of Theorem 1.13

Observation 6.1.

Proof.

Lemma 6.2.

Proof.

Lemma 6.3.

Proof.

Lemma 6.4.

Proof.

Observation 6.5.

Proof.

Lemma 6.6.

Proof.

Observation 6.7.

$K_{n}$ -minor-free graphs