# An update on $(n,m)$-chromatic numbers

Sandip Das$\,{}^{a}$, Abhiruk Lahiri$\,{}^{b}$, Soumen Nandi$\,{}^{c}$,
Sagnik Sen$\,{}^{d}$, S Taruni$\,{}^{d}$

$(a)$ Indian Statistical Institute Kolkata, India
$(b)$ Charles University, Czech Republic
$(c)$ Institute of Engineering & Management, Kolkata, India
$(d)$ Indian Institute of Technology Dharwad, India

###### Abstract

An $(n,m)$-graph is a graph with $n$ types of arcs and $m$ types of edges. A
homomorphism of an $(n,m)$-graph $G$ to another $(n,m)$-graph $H$ is a vertex
mapping that preserves adjacency, its direction, and its type. The minimum
value of $|V(H)|$ such that $G$ admits a homomorphism to $H$ is the
$(n,m)$-chromatic number of $G$, denoted by
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G)$. This parameter was
introduced by Nešetřil and Raspaud (J. Comb. Theory. Ser. B 2000).

In this article, we show that the arboricity of $G$ is bounded by a function
of $\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G)$, but not the
other way round. We also show that acyclic chromatic number of $G$ is bounded
by a function of $\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G)$,
while the other way round bound was known beforehand. Moreover, we show that
$(n,m)$-chromatic number for the family of graphs having maximum average
degree less than $2+\frac{2}{4(2n+m)-1}$, which contains the family of planar
graphs having girth at least $8(2n+m)$ as a subfamily, is equal to
$2(2n+m)+1$. This improves the previously known result which proved that the
$(n,m)$-chromatic number for the family planar graphs having girth at least
$10(2n+m)-4$ is equal to $2(2n+m)+1$. It is known that the $(n,m)$-chromatic
number for the family of partial $2$-trees bounded below and above by
quadratic functions of $(2n+m)$ and that the lower bound is tight when
$(2n+m)=2$. We show that the lower bound is not tight when $(2n+m)=3$ by
improving the corresponding lower bounds by one. We manage to improve some of
the the upper bounds in these cases as well.

Keywords: colored mixed graph, graph homomorphism, chromatic number, maximum
degree, sparse graphs, arboricity.

##  1 Introduction

In 2000, Nešetřil and Raspaud [19] generalized the notion of graph
homomorphisms by introducing colored homomorphisms of colored mixed
graphs111The same notion is studied in literature under slightly different
names. We choose the one most suitable for this article..

### The $(n,m)$-graphs:

An $(n,m)$-graph is a graph $G$ with set of vertices $V(G)$, set of arcs
$A(G)$, and set of edges $E(G)$. Moreover, each arc is colored with one of the
$n$ colors from $\\{2,4,\cdots,2n\\}$ and each edge is colored with one of the
$m$ colors from $\\{2n+1,2n+2,\cdots,2n+m\\}$. The underlying undirected graph
of $G$ is denoted by $und(G)$. In this article, we restrict ourselves to
$(n,m)$-graphs $G$ where $und(G)$ are simple, unless otherwise stated.

Observe that, for $(n,m)=(0,1),(1,0),(0,2)$, and $(0,m)$, the $(n,m)$-graphs
are the same as undirected graphs, oriented graphs [24], $2$-edge-colored
graphs [13], and $m$-edge-colored graphs [1], respectively. These types of
graphs and their homomorphisms are well-studied. It is worth mentioning that,
a variation of homomorphisms of $(0,2)$-graphs, called homomorphisms of signed
graphs [15], have gained popularity [21, 17, 5, 16] in recent times due to its
strong connection with classical graph theory (especially, coloring and graph
minor theory). It is known that, homomorphisms of signed graphs are in one-to-
one correspondence with a specific restriction of homomorphisms of
$(0,2)$-graphs [21]222In the language of category theory, there is a bijective
covariant functor from the category induced by homomorphisms of signed graphs
to a subcategory of the category induced by homomorphisms of $(0,2)$-graphs..
Thus, the notion of colored homomorphism truly manages to unify a lot of
important theories related to graph homomorphisms.

### Homomorphisms:

A homomorphism of an $(n,m)$-graph $G$ to another $(n,m)$-graph $H$ is a
function

$f:V(G)\rightarrow V(H)$

such that if $uv$ is an arc (resp., edge) of $G$, then $f(u)f(v)$ is also an
arc (resp., edge) of $H$ having the same color as $uv$. The notation
$G\rightarrow H$ is used to denote that $G$ admits a homomorphism to $H$.

Using the notion of homomorphism, one can define the chromatic number of
colored mixed graphs that generalizes [9] the chromatic numbers defined for
simple graphs, oriented graphs, $m$-edge-colored graphs, etc. The
$(n,m)$-chromatic number of an $(n,m)$-graph $G$ is given by

$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G)=\min\\{|V(H)|:G\rightarrow
H\\}.$

For a simple graph $S$, the $(n,m)$-chromatic number is given by

$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(S)=\max\\{\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G):und(G)=S\\}.$

For a family $\mathcal{F}$ of graphs, the $(n,m)$-chromatic number is given by

$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{F})=\max\\{\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G):G\in\mathcal{F}\\}.$

Notice that, the family $\mathcal{F}$ may contain simple or $(n,m)$-graphs.

### State of the art, contributions, and organization of the paper:

The $(n,m)$-chromatic number for $(n,m)=(0,1)$ is simply the ordinary
chromatic number which is, arguably, the most popularly studied topic of graph
theory. However, due to some basic differences in the nature of the
homomorphisms, the general study of the $(n,m)$-chromatic number tends to
address the parameter for all values of $(n,m)\neq(0,1)$. Naturally, the
$(n,m)$-chromatic number has been studied for various graph families in the
past [19, 8, 14] and, in particular, for $(n,m)=(1,0)$ and $(0,2)$, it has
been extensively studied under the names oriented chromatic number [23, 10,
24] and $2$-edge-colored chromatic number [5, 1, 13]. It is noteworthy that
any result proved for general $(n,m)$-chromatic number also, in particular,
imply results for oriented and $2$-edge-colored chromatic numbers.

In the following, we summarize the contributions of this work along with
relevant state of the art. We also enumerate them in a way so that it
indicates the organization of the article.333Section 3 was part of a CALDAM
2017 Conference proceedings in Lecture Notes in Computer Science. Section 4
was part of EuroComb 2021 conference proceedings in Lecture notes in Computer
Science.

  * •

Section 2: We recall some basic results and preliminaries useful for the
proofs in the following sections.

  * •

Section 3: This section is dedicated to establishing relations between the
parameters arboricity, acyclic chromatic number, and $(n,m)$-chromatic number.
To begin with, we show that the $(n,m)$-chromatic number of a graph $G$ is not
bounded above by a function of its arboricity, yet its arboricity is bounded
by $\lceil\log_{p}k+k/2\rceil$, where $k$ is its $(n,m)$-chromatic number. In
contrast to that, Nešetřil and Raspaud [19], generalizing a result due to
Raspaud and Sopena [22], showed that the $(n,m)$-chromatic number of a graph
with acyclic chromatic number $t$ is bounded above by $t(2n+m)^{t-1}$ while
Fabila-Monroy, Flores, Heumer, and Montejano [8], generalizing a result of
Ochem [20], proved the tighness of the bound. We prove that the reverse
statement is also true, that is, the acyclic chromatic number of a graph $G$
is bounded above by $k^{2}+k^{2+\lceil\log_{p}\log_{p}k\rceil}$, where $k$ is
its $(n,m)$-chromatic number. These upper bounds are generalizations of
results due to Kostochka, Sopena and Zhu [10] proved for $(n,m)=(1,0)$. We
managed to slightly improve the second bound while generalizing it.

  * •

Section 4: The $(n,m)$-chromatic number for the family of planar graphs is
bounded above by $5(2n+m)^{4}$ due to Nešetřil and Raspaud [19] while there is
a lower bound of the same which is a cubic function of $(2n+m)$ by Fabila-
Monroy, Flores, Heumer, and Montejano [8]. These two bounds together are the
closest analogue of the Four-Color Theorem for $(n,m)$-graphs. On the other
hand, the best (and the only) known possible analogue of the Grötzsch’s
theorem for $(n,m)$-graphs is a result due to Montejano, Pinlou, Raspaud, and
Sopena [14] which shows that the $(n,m)$-chromatic number for the family of
planar graphs having girth at least $10(2n+m)-4$ is equal to $2(2n+m)+1$. We
improve this result by showing that the $(n,m)$-chromatic number for the
family of graphs having maximum average degree less than
$2+\frac{2}{4(2n+m)-1}$, which contains the family of planar graphs having
girth at least $8(2n+m)$ as a subfamily, is equal to $2(2n+m)+1$.

  * •

Section 5: It is known that the $(n,m)$-chromatic number for the family of
partial $2$-trees bounded below and above by quadratic functions of $(2n+m)$
due to Fabila-Monroy, Flores, Heumer, and Montejano [8] and Nešetřil and
Raspaud [19], respectively. The lower bounds, when restricted to the cases of
$(2n+m)=2$, are known to be tight [13, 23]. The next natural question to ask
is whether the lower bounds are tight for $(2n+m)=3$ as well. Observe that
$(2n+m)=3$ only when $(n,m)=(0,3)$ or $(1,1)$. The best known bounds, in these
two cases tell us that the $(0,3)$-chromatic number [8] of partial $2$-trees
lie in the interval $[13,27]$, and the $(1,1)$-chromatic number [14] of
partial $2$-trees lie in the interval $[13,21]$. We improve both these
intervals to $[14,15]$ and $[14,21]$, respectively. In particular this shows
that the general lower bound of the $(n,m)$-chromatic number for the family of
partial $2$-trees proved in [8] is not tight for $(2n+m)=3$.

  * •

Section 6 : We share our concluding remarks.

##  2 Preliminaries

For standard graph theoretic notation and terminologies we will follow the
book “Introduction to Graph Theory” by West [25] and we will recall all non-
standard definitions here for convenience. Moreover, we will use a slightly
modified article specific notations for improving the readability and
uniformity of this article. Also, the standard notions relevant for simple
graphs, if used for an $(n,m)$-graph $G$, will be understood as a property of
$und(G)$.

If $uv$ is an arc of color $\alpha$, then we say that $v$ is an
$\alpha$-neighbor of $u$, or equivalently, we say that $u$ is an
$(\alpha-1)$-neighbor of $v$. On the other hand, if $uv$ is an edge of color
$\alpha$, then we say that $u$ and $v$ are $\alpha$-neighbors of each other.
Furthermore, the set of all $\alpha$-neighbors of $u$ is denoted by
$N^{\alpha}(u)$. Also, we will use the Greek smaller case letters such as
$\alpha,\beta,\gamma$ etc. as variables belonging to the set
$\\{1,2,\cdots,2n+m\\}$ denoting the color and the direction of an adjacency.

A special $2$-path is $2$-path $uvw$ of $(n,m)$-graph $G$ where $v\in
N^{\alpha}(u)\cap N^{\beta}(w)$ such that $\alpha\neq\beta$. The following
useful property comes in handy in proving some of the results of this paper.

######  Lemma 2.1 ([3]).

Two vertices $u$ and $v$ cannot have the same image under any homomorphism of
$G$ to any $H$, if and only if they are adjacent or connected by a special
$2$-path in $G$.

##  3 Acyclic chromatic number and arboricity

The arboricity arb(G) of a graph $G$ is the minimum $r$ such that the edges of
$G$ can be decomposed into $r$ forests. First we show that an $(n,m)$-graph
having bounded arboricity can have arbitrarily large $(n,m)$-chromatic number.

######  Theorem 3.1.

For every positive integer $k\geq 2$, there exists an $(n,m)$-graph $G_{k}$
having arboricity at most $r$ that satisfies
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G_{k})\geq k$.

###### Proof.

Consider the complete graph $K_{k}$. For all $(n,m)\neq(0,1)$, it is possible
to replace all the edges of $K_{k}$ by a special $2$-path to obtain an
$(n,m)$-colored mixed graph $G_{k}^{\prime}$. We know that, the end points of
the special $2$-path must have different image under any homomorphism of
$G_{k}^{\prime}$ [3], thus $\chi_{(n,m)}(G_{k}^{\prime})\geq k$ whereas, it is
easy to note that $G_{k}^{\prime}$ has arboricity $2$. Thus, for $r=2$ take
$G_{k}=G_{k}^{\prime}$. For $r>2$, simply take the disjoint union of the above
$G_{k}^{\prime}$ with a finite graph $H$ having arboricity $r$. ∎

Next we show that it is possible to bound the arboricity of an $(n,m)$-graph
by a function of $(n,m)$-chromatic number.

######  Theorem 3.2.

Let $G$ be a graph with $\chi_{n,m}(G)=k$ where $p=2n+m\geq 2$. Then
$arb(G)\leq\lceil\log_{p}k+k/2\rceil$.

###### Proof.

Let $G^{\prime}$ be an arbitrary labeled subgraph of $G$ consisting
$v_{G^{\prime}}$ vertices and $e_{G^{\prime}}$ edges. We know from Nash-
Williams’ Theorem [18] that the arboricity $arb(G)$ of any graph $G$ is equal
to the maximum of $\lceil e_{G^{\prime}}/(v_{G^{\prime}}-1)\rceil$ over all
subgraphs $G^{\prime}$ of $G$. It is sufficient to prove that for any subgraph
$G^{\prime}$ of $G$, $e_{G^{\prime}}/(v_{G^{\prime}}-1)\leq\log_{p}k+k/2$. As
$G^{\prime}$ is a labeled graph, so there are $p^{e_{G^{\prime}}}$ different
$(n,m)$-graphs with underlying graph $G^{\prime}$. As $\chi_{n,m}(G)=k$, there
exits a homomorphism from $G^{\prime}$ to a $(n,m)$-colored mixed graph
$G_{k}$ which has the complete graph on $k$ vertices as its underlying graph.
Observe that, even though it is not a necessary condition for $G_{k}$ to have
the complete graph as its underlying graph, we can always add some extra
edges/arcs to make $G_{k}$ have that property. Note that the number of
possible homomorphisms of $G^{\prime}$ to $G_{k}$ is at most
$k^{v_{G^{\prime}}}$. For each such homomorphism of $G^{\prime}$ to $G_{k}$
there are at most $p^{k\choose 2}$ different $(n,m)$-colored mixed graphs with
underlying labeled graph $G^{\prime}$ as there are $p^{k\choose 2}$ choices of
$G_{k}$. Therefore,

$p^{k\choose 2}.k^{v_{G^{\prime}}}\geq p^{e_{G^{\prime}}}$ (1)

which implies

$\log_{p}k\geq(e_{G^{\prime}}/v_{G^{\prime}})-{k\choose 2}/v_{G^{\prime}}.$
(2)

Suppose if $v_{G^{\prime}}\leq k$, then $e_{G^{\prime}}/(v_{G^{\prime}}-1)\leq
v_{G^{\prime}}/2\leq k/2$. Now let $v_{G^{\prime}}>k$. We know that
$\chi_{n,m}(G^{\prime})\leq\chi_{n,m}(G)=k$. So

$\begin{split}\log_{p}k&\geq\frac{e_{G^{\prime}}}{v_{G^{\prime}}}-\frac{k(k-1)}{2v_{G^{\prime}}}\\\
&\geq\frac{e_{G^{\prime}}}{(v_{G^{\prime}}-1)}-\frac{e_{G^{\prime}}}{v_{G^{\prime}}(v_{G^{\prime}}-1)}-\frac{k-1}{2}\\\
&\geq\frac{e_{G^{\prime}}}{(v_{G^{\prime}}-1)}-1/2-k/2+1/2\\\
&\geq\frac{e_{G^{\prime}}}{(v_{G^{\prime}}-1)}-k/2.\end{split}$

Therefore, $\frac{e_{G^{\prime}}}{(v_{G^{\prime}}-1)}\leq\log_{p}k+k/2$. ∎

A graph $G$ is acyclic $t$-colorable if we can color its vertices with $t$
colors such that each color class induces an independent set and any two color
classes induce a forest. The acyclic chromatic number
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{a}(G)$ of a simple graph $G$
is the minimum $t$ such that $G$ is acyclic $t$-colorable.

One of the major results proved for $(n,m)$-chromatic numbers is due to
Nešetřil and Raspaud [19] which shows that

$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{A}_{t})=t(2n+m)^{t-1}$

where $\mathcal{A}_{t}$ denotes the family of graphs having acyclic chromatic
number at most $t$. Moreover, Fabila-Monroy, Flores, Heumer, and Montejano [8]
proved the tighness of the same. In particular, this shows that the
$(n,m)$-chromatic number of a graph is bounded by a function of its acyclic
chromatic number. It is natural to ask whether the converse is also true.

It turns out to be true, however, before presenting its proof, we will show
that the acyclic chromatic number of a graph is finite if its arboricity and
$(n,m)$-chromatic number is finite.

######  Theorem 3.3.

Let $G$ be a graph with $arb(G)=r$ and $\chi_{n,m}(G)=k$ where $p=2n+m\geq 2$.
Then $\chi_{a}(G)\leq k^{\lceil\log_{p}r\rceil+1}$.

###### Proof.

Let $G$ be a graph with $arb(G)=r$ and
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G)=k$ where $2n+m=p$.
Let $v_{1},v_{2},...,v_{t}$ be some ordering of the vertices of $G$. Now
consider the $(n,m)$-colored mixed graph $G_{0}$ with underlying graph $G$
such that for any $i<j$ we have $v_{j}\in N^{1}(v_{i})$ whenever $v_{i}v_{j}$
is an edge of $G$.

Note that the edges of $G$ can be covered by $r$ edge disjoint forests
$F_{1},F_{2},...,F_{r}$ as $arb(G)=r$. Let $s_{i}$ be the number $i$ expressed
in base $p$ for all $i\in\\{1,2,...,r\\}$. Note that $s_{i}$ can have at most
$s=\lceil\log_{p}r\rceil$ digits.

Now we will construct a sequence of $(n,m)$-colored mixed graphs
$G_{1},G_{2},...,G_{s}$ each having underlying graph $G$. For
$l\in\\{1,2,...,s\\}$ we are going to describe the construction of the
$(n,m)$-graph $G_{l}$. Consider any edge $v_{i}v_{j}$ of $G$ where $i<j$. Then
$v_{i}v_{j}$ is an edge of the forest $F_{t}$ for some $t\in\\{1,2,...,r\\}$.
Let the $t^{th}$ digit of $s_{t}$ be $\hat{t}$. Then $G_{l}$ is constructed in
such a way that we have $v_{j}\in N^{\hat{t}+1}(v_{i})$ in $G_{l}$.

Recall that $\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G)\leq k$
and the underlying graph of $G_{l}$ is $G$. Thus, for each
$l\in\\{1,2,\cdots,s\\}$ there exists an $H_{l}$ on $k$ vertices and a
homomorphism $f_{l}:G_{l}\rightarrow H_{l}$. Now we claim that
$f(v)=(f_{0}(v),f_{1}(v),...,f_{s}(v))$ for each $v\in V(G)$ is an acyclic
coloring of $G$.

For adjacent vertices $u,v$ in $G$ clearly we have $f(v)\neq f(u)$ as
$f_{0}(v)\neq f_{0}(u)$. Let $C$ be a cycle in $G$. We have to show that at
least three colors have been used to color this cycle with respect to the
coloring given by $f$. Note that in $C$ there must be two incident edges $uv$
and $vw$ such that they belong to different forests, say, $F_{t}$ and
$F_{t^{\prime}}$, respectively. Now suppose that $C$ received two colors with
respect to $f$, that is, the contrary of what we wish to prove. Then we must
have $f(u)=f(w)\neq f(v)$. In particular we must have $f_{0}(u)=f_{0}(w)\neq
f_{0}(v)$. To have that we must also have $u,w\in N^{\alpha}(v)$ for some
$\alpha\in\\{1,2,...,p\\}$ in $G_{0}$ (even though $\alpha$ can only take the
value $1$ or $2$ in this case). Let $s_{t}$ and $s_{t^{\prime}}$ differ in
their $j^{th}$ digit. Then in $G_{j}$ we have $u\in N^{\alpha}(v)$ and $w\in
N^{\alpha^{\prime}}(v)$ for some $\alpha\neq\alpha^{\prime}$. Then we must
have $f_{j}(u)\neq f_{j}(w)$ as $uvw$ is a special $2$-path in $G_{j}$.
Therefore, we also have $f(u)\neq f(w)$. Thus, the cycle $C$ cannot be colored
with two colors under the coloring $f$. ∎

Thus, combining Theorem 3.2 and 3.3, $\chi_{a}(G)\leq
k^{\lceil\log_{p}\lceil\log_{p}k+k/2\rceil\rceil+1}$ for $\chi_{n,m}(G)=k$
where $p=2n+m\geq 2$. However, we managed to obtain the following bound which
is better in all cases except for some small values of $k,p$.

######  Theorem 3.4.

Let $G$ be an $(n,m)$-colored mixed graph with $\chi_{(n,m)}(G)=k\geq 4$ where
$p=2n+m\geq 2$. Then
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{a}(G)\leq
k^{2}+k^{2+\lceil\log_{p}\log_{p}k\rceil}$.

###### Proof.

Let $t$ be the maximum real number such that there exists a subgraph
$G^{\prime}$ of $G$ with $v_{G^{\prime}}\geq k^{2}$ and $e_{G^{\prime}}\geq
t.v_{G^{\prime}}$. Let $G^{\prime\prime}$ be the biggest subgraph of $G$ with
$e_{G^{\prime\prime}}>t.v_{G^{\prime\prime}}$. Thus, by maximality of $t$,
$v_{G^{\prime\prime}}<k^{2}$.

Let $G_{0}=G-G^{\prime\prime}$. Hence $\chi_{a}(G)\leq\chi_{a}(G_{0})+k^{2}$.
By maximality of $G^{\prime\prime}$, for each subgraph $H$ of $G_{0}$, we have
$e_{H}\leq t.v_{H}$.

If $t\leq\frac{v_{H}-1}{2}$, then $e_{H}\leq(t+1/2)(v_{H}-1)$. If
$t>\frac{v_{H}-1}{2}$, then $\frac{v_{H}}{2}<t+1/2$. So
$e_{H}\leq\frac{(v_{H}-1).v_{H}}{2}\leq(t+1/2)(v_{H}-1)$. Therefore,
$e_{H}\leq(t+1/2)(v_{H}-1)$ for each subgraph $H$ of $G_{0}$.

By Nash-Williams’ Theorem [18], there exists $r=\lceil t+1/2\rceil$ forests
$F_{1},F_{2},\cdots,F_{r}$ which covers all the edges of $G_{0}$. We know from
Theorem 3.3, $\chi_{a}(G_{0})\leq k^{s+1}$ where $s=\lceil\log_{p}r\rceil$.

Using inequality (2) we get $\log_{p}k\geq t-1/2$. Therefore

$s=\lceil\log_{p}(\lceil
t+1/2\rceil)\rceil\leq\lceil\log_{p}(1+\lceil\log_{p}k\rceil)\rceil\leq
1+\lceil\log_{p}\log_{p}k\rceil.$

Hence $\chi_{a}(G)\leq k^{2}+k^{2+\lceil\log_{p}\log_{p}k\rceil}$. ∎

Our bound, when restricted to the case of $(n,m)=(1,0)$, slightly improves the
existing bound due to Kostochka, Sopena and Zhu [10].

##  4 Sparse graphs

The maximum average degree of a graph is given by

$mad(G)=\max\left\\{\frac{2|E(H)|}{|V(H)|}:\text{ $H$ is a subgraph of
$G$}\right\\}.$

We present a tight bound for the $(n,m)$-chromatic number of sparse graphs.

######  Theorem 4.1.

For $mad(G)<2+\frac{2}{4(2n+m)-1}$ and $2n+m\geq 2$, we have

$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(G)\leq 2(2n+m)+1.$

We begin the proof of Theorem 4.1 by describing a complete $(n,m)$-graph on
$(2p+1)$ vertices where $p=2n+m$. We know that there exists a Hamiltonian
decomposition of $K_{2p+1}$ due to Walecki [2] which we are going to describe
in the following. To do so, first we will label the vertices of $K_{2p+1}$ is
a certain way. Let one specific vertex of it be labeled by the symbol $\infty$
while the other vertices are labeled by the elements of the cyclic group
$\mathbb{Z}/2p\mathbb{Z}$. Let $C_{0},C_{1},\cdots,C_{p-1}$ be the edge
disjoint Hamiltonian cycles of the decomposition where $C_{j}$ is the cycle

$\infty(2p+j)(1+j)(2p-1+j)\cdots(p-1+j)(2p-(p-1)+j)(p+j)\infty$

For each $\alpha\in\\{2,4,6\cdots 2n\\}$ convert the cycles $C_{\alpha-2}$ and
$C_{\alpha-1}$ to directed cycles having arcs of color $\alpha$. For each
$\alpha\in\\{2n+1,n+2,\cdots,2n+m\\}$, convert the cycle $C_{\alpha-1}$ into a
cycle having all edges of color $\alpha$. Thus what we obtain is a complete
$(n,m)$-mixed graph on $2p+1$ vertices. We call this so-obtained complete
$(n,m)$-graph as $T$. We now prove a useful property of $T$.

######  Lemma 4.2.

For every $S\subsetneq V(T)$ we have $|S|<|N^{\alpha}(S)|$ for all
$\alpha\in\\{1,2,\cdots 2n+m\\}$.

###### Proof.

We divide the proof into three parts depending on the value of $\alpha$.

Case 1: If $\alpha\in\\{2n+1,2n+2,\cdots 2n+m\\}$, then assume that
$C_{\alpha-1}$ is the cycle $v_{1}v_{2}\cdots v_{2p+1}v_{1}$ and the set $S$
consist of vertices $v_{i_{1}},v_{i_{2}},\cdots,v_{i_{l}}$ where
$i_{1}<i_{2}<\cdots<i_{l}$. Now notice that the set of vertices
$A=\\{v_{i_{1}+1},v_{i_{2}+1},\cdots,v_{i_{l}+1}\\}$ are distinct and are
contained in $N^{\alpha}(S)$. On the other hand, note that the set of vertices
$B=\\{v_{i_{1}-1},v_{i_{2}-1},\cdots,v_{i_{l}-1}\\}$ are distinct and are
contained in $N^{\alpha}(S)$. As $|A|=|B|=|S|$, we are done unless $A=B$.

If $A=B$, then note that $v_{t}\in S$ implies $v_{t+2}\in S$ where the $+$
operation on indices of $v$ is taken modulo $2p+1$. Hence, if there exists
some index $t$ for which we have $v_{t},v_{t+1}\in S$, then $S$ must be the
whole vertex set, which is not possible. Thus, we must have
$v_{i_{j+1}}=v_{i_{j}+2}$ for all $j\in\\{1,2,\cdots,l\\}$ where the $+$
operation on indices of $v$ is taken modulo $2p+1$. However as $C_{\alpha}$ is
an odd cycle on $2p+1$ vertices, it is impossible to satisfy the above
condition. Hence $A\neq B$, and we are done in this case.

Case 2: If $\alpha\in\\{2,4,\cdots,2n\\}$, then observe that $S$ has exactly
$|S|$ many $\alpha$-neighbors in $C_{\alpha-2}$ and exactly $|S|$ many
$\alpha$-neighbors in $C_{\alpha-1}$. Furthermore, assume that $A$ and $B$ are
the sets of $\alpha$-neighbors of $S$ in $C_{\alpha-2}$ and $C_{\alpha-1}$,
respectively. As $|A|=|B|=|S|$ and $A\cup B\subseteq N^{\alpha}(S)$, we are
done unless $A=B$. Due to the structure of the cycles $C_{\alpha-2}$ and
$C_{\alpha-1}$, without loss of generality we may assume that $\alpha=2$.

Thus let us try to obtain a contradiction assuming $A=B$. In such a scenario,
fix a $k\in\mathbb{Z}/2p\mathbb{Z}$. Note that $p\neq k\in S$ if and only if
$x\in A=B$ if and only if $k+2\in S$, where $x=(2p-k)$ (resp., $(2p-k+1)$)
Moreover, $p\in S$ if and only if $\infty\in A=B$ if and only if $(p+1)\in S$.
Also, $0\in S$ if and only if $1\in A=B$ if and only if $\infty\in S$. Hence,
for any non-empty $S$, $A=B$ forces $S=V(T)$, a contradiction.

Case 3: If $\alpha\in\\{1,3,\cdots,2n-1\\}$, then one can handle it in a way
similar to Case 2.

Therefore, $|S|<|N^{\alpha}(S)|$ for all $\alpha\in\\{1,2,\cdots 2n+m\\}$ and
for every $S\subsetneq V(K_{2p+1})$. ∎

Let $T$ be a complete $(n,m)$-graph on $2p+1$ vertices satisfying the
condition of Lemma 4.2. We want to show that $G\to T$ whenever
$mad(G)<2+\frac{2}{4p-1}$. That is, it is enough to prove the following lemma.

######  Lemma 4.3.

If $mad(G)<2+\frac{2}{4p-1}$, then $G\to T$.

We will prove the above lemma by contradiction. Hence we assume a minimal
(with respect to number of vertices) $(n,m)$-graph $M$ having
$mad(M)<2+\frac{2}{4p-1}$ which does not admit a homomorphism to $T$. We now
give some forbidden configurations for $M$ stated as lemmas.

######  Lemma 4.4.

The graph $M$ does not contain a vertex having degree one.

###### Proof.

Suppose $M$ contains a vertex $u$ having degree one. Observe that the graph
$M^{\prime}$, obtained by deleting the vertex $u$ from $M$, admits a
homomorphism to $T$ due to the minimality of $M$. It is possible to extend the
homomorphism $M^{\prime}\to T$ to a homomorphism of $M\to T$ as any vertex of
$T$ has exactly two $\alpha$-neighbors for all $\alpha\in\\{1,2,\cdots
2n+m\\}$. ∎

A path with all internal vertices of degree two is called a chain, and in
particular a $k$-chain is a chain having $k$ internal vertices. The endpoints
(assume them to always have degree at least $3$) of a ($k$-)chain are called
($k$-)chain adjacent.

######  Lemma 4.5.

The graph $M$ does not contain a $k$-chain with $k\geq 2p-1$.

###### Proof.

Suppose $M$ contains a $k$-chain with endpoints $u,v$. Observe that the graph
$M^{\prime}$, obtained by deleting the internal degree two vertices from the
above mentioned chain from $M$, admits a homomorphism to $T$ due to the
minimality of $M$. It is possible to extend the homomorphism $M^{\prime}\to T$
to a homomorphism of $M\to T$ by Lemma 4.2. ∎

Let us describe another configuration. Suppose $v$ is chain adjacent to
exactly $l$ vertices $v_{1},v_{2},\cdots,v_{l}$, each having degree at least
three. Let the chains between $v$ and $v_{i}$ has $k_{i}$ internal vertices.
Let us refer to such a configuration as configuration $C_{l}$ for convenience.

######  Lemma 4.6.

The graph $M$ does not contain the configuration $C_{l}$ as a induced subgraph
if

$\sum_{i=1}^{l}k_{i}>(2p-1)l-2p$

where $p=(2n+m)$.

###### Proof.

Suppose $M$ contains the configuration $C_{l}$. Let $M^{\prime}$ be the graph
obtained by deleting all vertices of the configuration except
$v_{1},v_{2},\cdots,v_{l}$. Thus there exists a homomorphism $f:M^{\prime}\to
T$ due to minimality of $M$. We are going to extend $f$ to a homomorphism
$f_{ext}:M\to T$, which will lead to a contradiction and complete the proof.

As $T$ has exactly two $\alpha$-neighbors for all $\alpha\in\\{1,2,\cdots
2n+m\\}$, Lemma 4.2 implies that it is possible to partially extend $f$ to the
chain between $v$ and $v_{i}$ in such different ways that will allow us to
choose the value of $f_{ext}(v_{i})$ from a set of $k_{i}+2$ vertices of $T$.
In other words, the value of $f(v_{i})$ will forbid at most $2p-k_{i}-1$
values at $v_{i}$.

Thus, considering the effects all the chains incident to $v$, at most

$2lp-\sum_{i=1}^{l}k_{i}-l$

values are forbidden at $v$.

Notice that if this value is less than or equal to $2p$, then it will be
possible to extend $f$ to a homomorphism $f_{ext}:M\to T$. That implies the
relation $\sum_{i=1}^{l}k_{i}\leq(2p-1)l-2p$. ∎

Now we are ready to start the discharging procedure. First we define a charge
function on the vertices of $M$.

$ch(x)=\text{deg}(x)-\left(2+\frac{2}{4p-1}\right),\text{ for all }x\in V(M).$

Observe that, $\sum_{x\in V(M)}ch(x)<0$ as $mad(M)<2+\frac{2}{4p-1}$. Now
after the completion of the discharging procedure, all updated charge will
become non-negative implying a contradiction. The discharging rule is the
following:

$(R1):$ Every vertex having degree three or more donates $\frac{1}{4p-1}$ to
the degree two vertices which are part of its incident chains.

Let $ch^{*}(x)$ be the updated charge. Now we are going to calculate this
values of this updated charge for vertices of different degrees in $M$.

######  Lemma 4.7.

For any degree two vertex $x\in V(M)$, we have $ch^{*}(x)=0$.

###### Proof.

As $M$ does not have any degree one vertex due to Lemma 4.4, every degree two
vertex $x$ must be internal vertex of a chain. Thus, by rule $(R1)$ the vertex
$x$ must receive $\frac{1}{4p-1}$ charge from each side of the chain. Hence
the updated charge is

$ch^{*}(x)=ch(x)+\frac{2}{4p-1}=deg(x)-2-\frac{2}{4p-1}+\frac{2}{4p-1}=0.$

Thus we are done. ∎

######  Lemma 4.8.

For any vertex $x$ having degree three or more, we have $ch^{*}(x)\geq 0$.

###### Proof.

Let $x$ be a degree $d$ vertex of $M$. Thus by Lemma 4.6

$\displaystyle ch^{*}(x)$ $\displaystyle\geq
ch(x)-\frac{(2p-1)d-2p}{4p-1}=d-2-\frac{2}{4p-1}-\frac{2pd-d-2p}{4p-1}$
$\displaystyle=\frac{4pd-8p-d+2-2-2pd+d+2p}{4p-1}=\frac{2p(d-3)}{4p-1}\geq 0$

for $d\geq 3$. ∎

This implies $0>\sum_{x\in V(M)}ch(x)=\sum_{x\in V(M)}ch^{*}(x)\geq 0$, a
contradiction. Thus, the proof of Lemma 4.3 is completed which proves the
Theorem 4.1.

Proof of Theorem 4.1. Observe that, due to the above lemmas, we have
$0>\sum_{x\in V(M)}ch(x)=\sum_{x\in V(M)}ch^{*}(x)\geq 0$, a contradiction.
Thus, the proof of Lemma 4.3 is completed which proves the Theorem 4.1. ∎

As a corollary to this result, we obtain
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{P}_{g})=2(2n+m)+1$
for all $g\geq 8(2n+m)$.

######  Theorem 4.9.

For $g\geq 8(2n+m)$ and $2n+m\geq 2$, we have,

$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{P}_{g})=2(2n+m)+1.$

###### Proof.

From the Theorem 4.1 along with the result by Borodin[4] that shows that a
planar graph $G$ having girth at least $g$ has $mad(G)<\frac{2g}{g-2}$, the
following result is obtained as a corollary of Theorem 4.1. ∎

##  5 Partial $2$-trees

The only solutions of $(2n+m)=2$ are $(n,m)=(1,0)$ and $(0,2)$. Similarly, the
only two solutions of $(2n+m)=3$ are $(n,m)=(1,1)$ and $(0,3)$. Therefore,
studying the $(n,m)$-chromatic number for these values of $(n,m)$ can help
understand the trend for the general values of $(n,m)$.

The best known general bounds of $(n,m)$-chromatic number for the family
$\mathcal{T}^{2}$ of partial $2$-trees, or equivalently, $K_{4}$-minor free
graphs are the following.

######  Theorem 5.1 (Fabila-Monroy, Flores, Heumer, and Montejano 2009 [8];
Nešetřil and Raspaud 2000 [19]).

For all non-negative integers $n$ and $m$ where $(2n+m)\geq 2$, we have

$\displaystyle(2n+m)^{2}+2(2n+m)+1\leq\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{T}^{2})\leq
3(2n+m)^{2},$ for $m>0$ even
$\displaystyle(2n+m)^{2}+(2n+m)+1\leq\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{T}^{2})\leq
3(2n+m)^{2},$ $\displaystyle\text{ otherwise}.$

Recall that, for $(2n+m)=2$ case, it is known that the lower bounds are tight
[13]. The best known bounds when $2n+m=3$ are
$13\leq\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{0,3}(\mathcal{T}^{2})\leq
27$ and
$13\leq\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{1,1}(\mathcal{T}^{2})\leq
21$. So, if the trend of lower bound in Theorem 5.1 being tight were true,
then in particular it would be true for the cases when $2n+m=3$. However, we
show the contrary via the following result where we improve the lower and the
upper bounds for both the instances.

######  Theorem 5.2.

For the family of $\mathcal{T}^{2}$ of partial $2$-trees we have,

  * (i)

$14\leq\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{0,3}(\mathcal{T}^{2})\leq
15$,

  * (ii)

$14\leq\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{1,1}(\mathcal{T}^{2})\leq
21$.

The proof of the theorem is contained in a series of lemmas.

An $(n,m)$-universal bound of $\mathcal{F}$ is an $(n,m)$-graph $T$ such that
$G\to T$ for all $und(G)\in\mathcal{F}$. A minimum $(n,m)$-universal bound of
$\mathcal{F}$ is a universal bound $T$ on minimum number of vertices having
the property that for every proper subgraph $T^{\prime}$ of $T$, there exists
a $G^{\prime}$ with $und(G^{\prime})\in\mathcal{F}$ such that
$G^{\prime}\not\to T^{\prime}$. A complete family $\mathcal{F}$ of graphs is
such that given $G_{1},G_{2}\in\mathcal{F}$, there exists a graph
$G\in\mathcal{F}$ that contains every $G_{i}$ as its subgraph.

######  Lemma 5.3.

Let $\mathcal{F}$ be a complete family of graphs. Then there exists a minimal
$(n,m)$-universal bound on $\mathcal{F}$ on
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{F})$ vertices.

###### Proof.

Suppose not, that is, for every $(n,m)$-graph $T$ on
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{F})$ vertices,
there exists a graph $(n,m)$-graph $G_{T}\in\mathcal{F}$ such that
$G_{T}\not\to T$. Since $\mathcal{F}$ is a complete family of graphs, there
exists a $(n,m)$-graph $G\in\mathcal{F}$ that contains every $G_{T}$ as its
subgraph. As $G\in\mathcal{F}$, there is a homomorphism $f:G\to\hat{T}$ for
some $(n,m)$-graph $\hat{T}$ on
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{F})$ vertices.
Then the restriction

$f|_{V(G_{T})}:G_{T}\to\hat{T}$

for all $(n,m)$-graphs $T$ on
$\raisebox{0.0pt}[4.30554pt][4.30554pt]{$\chi$}_{n,m}(\mathcal{F})$ vertices,
a contradiction. ∎

An $(n,m)$-graph $T$ has property $P_{2,1}$ if for any adjacent pair of
vertices $u,v$ of $T$ the set $N^{\alpha}(u)\cap N^{\beta}(v)$ is not empty
for all $\alpha,\beta\in\\{1,2,\cdots,2n+m\\}$.

######  Lemma 5.4.

Any minimum universal bound $T$ of the family $\mathcal{T}^{2}$ of partial
$2$-trees has property $P_{2,1}$.

###### Proof.

Due to minimality of $T$, there exists an $(n,m)$-graph $G$ with
$und(G)\in\mathcal{T}^{2}$ such that for any homomorphism $f:G\to T$, given
any $xy\in A(T)$ (resp., $E(T))$, there exists $uv\in A(G)$ (resp., $E(G)$)
satisfying $f(u)=x,f(v)=y$.

For any two adjacent vertices $u,v$ in $G$ and for any
$(\alpha,\beta)\in\\{1,2,\cdots,2n+m\\}^{2}$, add a new vertex
$w_{\alpha,\beta}$ adjacent to $u$ and $v$ in such a way that we have
$w_{\alpha,\beta}\in N^{\alpha}(u)\cap N^{\beta}(v)$. Let the so-obtained
$(n,m)$-graph be $G^{*}$. Observe that, $und(G^{*})\in\mathcal{T}^{2}$ by
construction. Therefore, $G^{*}$ admits a homomorphism to $T$.

For any pair $x,y$ of adjacent vertices in $T$ and for any homomorphism
$f^{*}:G^{*}\to T$, there exists $u,v$ in $G$ satisfying $f(u)=x$ and
$f(v)=y$. Note that the newly added common neighbors of $u,v$ are connected by
a special $2$-path via either $u$ or $v$. Thus, the images of $u,v$ and their
newly added common neighbors must have distinct images under $f^{*}$. As
$f^{*}$ is any homomorphism of $G^{*}$ to $T$, and as $x,y$ is any pair of
adjacent vertices in $T$, $T$ must have property $P_{2,1}$. ∎

The above lemma implies a necessary and sufficient condition useful for
computing the $(n,m)$-chromatic number of partial $2$-trees.

######  Corollary 5.5.

We have $\chi_{n,m}(\mathcal{T}_{2})=t$ if and only if there exists an
$(n,m)$-graph $T$ on $t$ vertices with property $P_{2,1}$.

In light of the above corollary, if one can show that there does not exist any
$(n,m)$-graph on $t$ vertices with property $P_{2,1}$, then it will imply that
$\chi_{n,m}(\mathcal{T}_{2})\geq t+1$. We will use this observation to prove
our lower bounds.

######  Lemma 5.6.

If $T$ is a minimal universal $(n,m)$-bound of $\mathcal{T}^{2}$ on
$(2n+m)^{2}+(2n+m)+1$ vertices, then every vertex $v$ in $T$ has exactly
$(2n+m)+1$ many $\alpha$-neighbors for all $\alpha\in\\{1,2,\cdots,2n+m\\}$.

###### Proof.

As $T$ has property $P_{2,1}$ due to Lemma 5.4, each vertex of $T$ has all
$(2n+m)$ types of adjacencies. Let $v$ be an $\alpha$-neighbor of $u$ in $T$.
Notice that, there is at least one vertex which is $\alpha$-neighbor of $u$
and $\beta$-neighbor of $v$. As $\beta$ varies over the set of all $(2n+m)$
types of adjacencies, $u$ has at least $(2n+m)$ $\alpha$-neighbors, which are
also adjacent to $v$. Thus, counting $v$, $u$ has at least $(2n+m)+1$ many
$\alpha$-neighbors.

On the other hand, as $\alpha$ is any of the $(2n+m)$ many adjacencies and
$|N^{\alpha}(u)|\geq 2n+m+1$, we have
$|N(u)|\geq(2n+m)(2n+m+1)=(2n+m)^{2}+(2n+m)$. As $T$ has only
$(2n+m)^{2}+(2n+m)+1$ vertices, the inequalities must be tight. ∎

######  Lemma 5.7.

If $T$ is a minimum universal $(n,m)$-bound of $\mathcal{T}^{2}$ on
$(2n+m)^{2}+(2n+m)+1$ vertices, then it can not have $x,y,z\in N^{\alpha}(u)$
such that $x,z$ are $\gamma$-neighbors of $y$.

###### Proof.

Suppose $x,y,z\in N^{\alpha}(u)$ and $x,z$ are $\gamma$-neighbors of $y$. We
know from the proof of Lemma 5.4 that there is exactly one vertex in the set
$N^{\alpha}(u)\cap N^{\beta}(y)$ for all $\beta$. However, in this case,
$\\{x,z\\}\subseteq N^{\alpha}(u)\cap N^{\beta}(y)$ for $\beta=\gamma$, a
contradiction. ∎

Now we are ready to prove the first lower bound.

######  Lemma 5.8.

The $(n,m)$-graph $T$ has at least $14$ vertices if either of the following
happens.

  1. (i)

$T$ is a minimum universal $(0,3)$-bound of $\mathcal{T}^{2}$.

  2. (ii)

$T$ is a minimum universal $(1,1)$-bound of $\mathcal{T}^{2}$.

###### Proof.

Suppose not, that is, $T$ is a minimum universal $(0,3)$-bound or a minimum
universal $(1,1)$-bound of $\mathcal{T}^{2}$ on $13$ vertices. Note that
$und(T)$ is a complete graph due to Lemma 5.6. Also using Lemma 5.4 and 5.6 we
know that $T$ contains a $K_{3}$ with vertices $u,v,w$ (say) whose all edges
are of color $3$.

Next we will try to count the number of vertices in $T$. For convenience, let
us denote the set $N^{\alpha}(u)\cap N^{\beta}(v)\cap
N^{\gamma}(w)\setminus\\{u,v,w\\}=A_{\alpha,\beta,\gamma}$. Also, let us
denote the set of all common neighbors of $u,v,w$ by $A$. As $T$ has property
$P_{2,1}$, there must exist a $x\in A$ which is a $3$-neighbor of $u$ and a
$2$-neighbor of $v$. Notice that, if $x$ is a $2$-neighbor or a $3$-neighbor
of $w$, then the configuration described in Lemma 5.7 is created. Thus, $x$
must be a $1$-neighbor of $w$. Hence,

$|A_{3,2,1}|\geq 1.$

Similarly, we can show that

$|A_{1,2,3}|=|A_{1,3,2}|=|A_{2,1,3}|=|A_{2,3,1}|=|A_{3,1,2}|=|A_{3,2,1}|\geq
1.$ (3)

Till now, among the vertices we have described, there is none which is a
$2$-neighbor of both $u,v$. However as $T$ has property $P_{2,1}$, there must
exist a vertex $y$ of $T$ which is a $2$-neighbor of both $u,v$. Note that,
$x$ can not be an $3$-neighbor or a $2$-neighbor of $w$ due to Lemma 5.7.
Thus, we are forced to have an edge of color three between $x$ and $w$. So

$|A_{2,2,1}|\geq 1.$

Similarly, we can show that

$|A_{2,2,1}|=|A_{1,1,2}|=|A_{2,1,2}|=|A_{1,2,1}|=|A_{1,2,2}|=|A_{2,1,1}|\geq
1.$ (4)

As the sets of the form $A_{\alpha,\beta,\gamma}$ partitions $A$, we can
combine equations (3) and (4) to conclude that $|A|\geq 12$. This implies that
$T$ has at least $15$ vertices including $u,v,w$, a contradiction. ∎

######  Lemma 5.9.

There exists a $(0,3)$-graph $T_{0,3}$ on $15$ vertices having property
$P_{2,1}$.

###### Proof.

Let $T_{0,3}$ be an $(0,3)$-graph with set of vertices
$\mathbb{Z}/5\mathbb{Z}\times\mathbb{Z}/3\mathbb{Z}$. Let $(i,j)$ and
$(i^{\prime},j^{\prime})$ be two vertices of $T_{0,3}$. The adjacency between
the vertices are as per the following rules.

  * •

If $j\neq j^{\prime}$ and $i=i^{\prime}$, then $(i,j)$ and
$(i^{\prime},j^{\prime})$ are not adjacent.

  * •

If $(i^{\prime}-i)$ is a non-zero square in $\mathbb{Z}/5\mathbb{Z}$, then
there is an edge of color $(1+j+j^{\prime})$ (considered modulo $3$) between
$(i,j)$ and $(i^{\prime},j^{\prime})$.

  * •

If $(i^{\prime}-i)$ is not a non-zero square in $\mathbb{Z}/5\mathbb{Z}$, then
there is an edge of color $(2+j+j^{\prime})$ (considered modulo $3$) between
$(i,j)$ and $(i^{\prime},j^{\prime})$.

Notice that it is enough to show that $T_{0,3}$ has property $P_{2,1}$. Let
$(i,j)$ and $(i^{\prime},j^{\prime})$ be any two adjacent vertices in
$T_{0,3}$. Without loss of generality we may assume that either
$i^{\prime}=i+1$ or $i^{\prime}=i+2$. We can further assume that $i=0$ and
$i^{\prime}=1$ or $2$, still without losing generality. Also, for convenience,
let $A_{\alpha,\beta}=N^{\alpha}((i,j))\cap
N^{\beta}((i^{\prime},j^{\prime}))$. Thus our objective is to show that all
such subsets, which are a total of nine in number, are non-empty.

  1. (i)

If $i^{\prime}=1$, then $(2,j^{\prime\prime})\in
A_{2+j+j^{\prime\prime},1+j^{\prime}+j^{\prime\prime}}$,
$(3,j^{\prime\prime})\in
A_{2+j+j^{\prime\prime},2+j^{\prime}+j^{\prime\prime}}$, and
$(4,j^{\prime\prime})\in
A_{1+j+j^{\prime\prime},2+j^{\prime}+j^{\prime\prime}}$ where
$j^{\prime\prime}$ varies over $\mathbb{Z}/5\mathbb{Z}$. Notice that, as
$j^{\prime\prime}$ varies, we obtain a total of nine non-empty subsets of the
type $A_{\alpha,\beta}$, and we are done by observing that these subsets have
distinct ordered pairs as indices.

  2. (ii)

If $i^{\prime}=2$, then $(1,j^{\prime\prime})\in
A_{1+j+j^{\prime\prime},1+j^{\prime}+j^{\prime\prime}}$,
$(3,j^{\prime\prime})\in
A_{2+j+j^{\prime\prime},1+j^{\prime}+j^{\prime\prime}}$, and
$(4,j^{\prime\prime})\in
A_{1+j+j^{\prime\prime},2+j^{\prime}+j^{\prime\prime}}$ where
$j^{\prime\prime}$ varies over $\mathbb{Z}/5\mathbb{Z}$. Notice that, as
$j^{\prime\prime}$ varies, we obtain a total of nine non-empty subsets of the
type $A_{\alpha,\beta}$, and we are done by observing that these subsets have
distinct ordered pairs as indices.

Hence $T_{0,3}$ has property $P_{2,1}$. ∎

The existence of a $(1,1)$-graph on $21$ vertices having property $P_{2,1}$ is
remarked in the conclusion of [8]. For the sake of completeness, we include an
explicit construction of the same.

######  Lemma 5.10.

There exists a $(1,1)$-graph $T_{1,1}$ on $21$ vertices having property
$P_{2,1}$.

###### Proof.

Let $T_{1,1}$ be an $(1,1)$-graph with set of vertices
$\mathbb{Z}/7\mathbb{Z}\times\mathbb{Z}/3\mathbb{Z}$. Let $(i,j)$ and
$(i^{\prime},j^{\prime})$ be two vertices of $T_{1.1}$. The adjacency between
the vertices are as per the following rules.

  * •

If $j\neq j^{\prime}$ and $i=i^{\prime}$, then, $(i,j)$ and
$(i^{\prime},j^{\prime})$ are not adjacent.

  * •

If $j^{\prime}=j$, and $(i^{\prime}-i)$ is a non-zero square in
$\mathbb{Z}/7\mathbb{Z}$, then there is an arc from $(i,j)$ to
$(i^{\prime},j^{\prime})$.

  * •

If $j^{\prime}=j+1~{}(\bmod~{}3)$ and $(i^{\prime}-i)$ is a non-zero square in
$\mathbb{Z}/7\mathbb{Z}$, then there is an edge between $(i,j)$ and
$(i^{\prime},j^{\prime})$.

  * •

If $j^{\prime}=j+1~{}(\bmod~{}3)$ and $(i^{\prime}-i)$ is not a non-zero
square in $\mathbb{Z}/7\mathbb{Z}$, then there is an arc from
$(i^{\prime},j^{\prime})$ to $(i,j)$.

As exactly one among $(i^{\prime}-i)$ or $(i-i^{\prime})$ is a non-zero square
in $\mathbb{Z}/7\mathbb{Z}$, the above indeed describes the whole
$(1,1)$-graph.

Notice that it is enough to show that $T_{1,1}$ has property $P_{2,1}$. Let
$(i,j)$ and $(i^{\prime},j^{\prime})$ be any two adjacent vertices in
$T_{1,1}$. For convenience, let $A_{\alpha,\beta}=N^{\alpha}((i,j))\cap
N^{\beta}((i^{\prime},j^{\prime}))$. Thus our objective is to show that all
such subsets, which are a total of nine in number, are non-empty.

Let $(i^{\prime}-i)$ a non-zero square (resp., non-square) of
$\mathbb{Z}/7\mathbb{Z}$. Define the mapping

$\phi:\mathbb{Z}/7\mathbb{Z}\to\mathbb{Z}/7\mathbb{Z}$

given by $\phi(x)=(i^{\prime}-i)^{2}(x-i)$. This map is a group automorpism of
$\mathbb{Z}/7\mathbb{Z}$ that maps a non-zero square to a non-zero square and
vice versa. Therefore, the adjacency rules of the graph, even after applying
this automorphism to the three copies of $\mathbb{Z}/7\mathbb{Z}$ used for
describing the graph, remain as it were. Also, notice that the above
automorphism maps $\phi(i)=0$ and $\phi(i^{\prime})=1$. Therefore, instead of
arguing a general case of $i,i^{\prime}$ where $(i^{\prime}-i)$ is a square,
we can argue for the case when $i=0$ and $i^{\prime}=1$ without losing any
generality. This brings us to the following cases.

  1. (i)

If $j^{\prime}=j$ and $(i^{\prime}-i)$ is a non-zero square, then without loss
of generality we may assume that $(i,j)=(0,0)$ and
$(i^{\prime},j^{\prime})=(1,0)$.

  2. (ii)

If $j^{\prime}=j+1$ (considered modulo $3$) and $(i^{\prime}-i)$ is a non-zero
square, then without loss of generality we may assume that $(i,j)=(0,0)$ and
$(i^{\prime},j^{\prime})=(1,1)$.

  3. (iii)

If $j^{\prime}=j+1$ (considered modulo $3$) and $(i^{\prime}-i)$ is not a non-
zero square, that is, $(i-i^{\prime})$ is a non-zero square, then without loss
of generality we may assume that $(i,j)=(1,0)$ and
$(i^{\prime},j^{\prime})=(0,1)$.

$(i,j)$ | $(i^{\prime}j^{\prime})$ | $A_{1,1}$ | $A_{1,2}$ | $A_{1,3}$ | $A_{2,1}$ | $A_{2,2}$ | $A_{2,3}$ | $A_{3,1}$ | $A_{3,2}$ | $A_{3,3}$
---|---|---|---|---|---|---|---|---|---|---
$(0,0)$ | $(1,0)$ | $(6,0)$ | $(5,0)$ | $(4,2)$ | $(4,0)$ | $(2,0)$ | $(5,1)$ | $(5,2)$ | $(4,1)$ | $(2,1)$
$(0,0)$ | $(1,1)$ | $(5,0)$ | $(4,2)$ | $(6,0)$ | $(2,0)$ | $(5,1)$ | $(4,0)$ | $(4,1)$ | $(2,1)$ | $(5,2)$
$(1,0)$ | $(0,1)$ | $(4,0)$ | $(5,2)$ | $(6,0)$ | $(2,0)$ | $(4,1)$ | $(5,0)$ | $(5,1)$ | $(2,1)$ | $(4,2)$

The previously defined nine subsets of the form $A_{\alpha,\beta}$ are non-
empty for each of the above listed cases can be observed from the above table.
Hence $T_{1,1}$ has property $P_{2,1}$. ∎

Proof of Theorem 5.2. Using Corollary 5.5, the lower bound follows from Lemma
5.8 and the upper bounds follow from Lemmas 5.9 and 5.10. ∎

##  6 Conclusions

Following the introduction of the $(n,m)$-graphs, their homomorphisms, and
$(n,m)$-chromatic numbers due to Nešetřil and Raspaud [19] in 2000, a number
of research works were dedicated towards this topic. In fact, the research in
this topic has evolved in different tracks such as, finding out the
$(n,m)$-chromatic number of some graphs families [19, 8, 14], the study of
relative and absolute $(n,m)$-clique numbers (that is, analogue of clique
numbers) [3, 7], study of the complexity dichotomy of homomorphisms of an
input $(n,m)$-graph $G$ to a prefixed $(n,m)$-graph $H$ [11, 12], and studies
related to the algebraic properties of such systems, and their interactions
with certain modifications such a permutation of adjacencies of a vertex (or
several vertices) [11, 12, 6]. Our work clearly pertains to the first of the
research tracks listed above.

In this track, the graph families for which the $(n,m)$-chromatic number is
studied are paths and forests [19], graphs with bounded maximum degree [14],
graphs with bounded acyclic chromatic number [19], partial $2$-trees [8],
planar graphs and planar graphs with high girth [14]. However, the study of
$(n,m)$-chromatic number of graph families is significantly less in volume
compared to the the cases when $(n,m)=(1,0)$ or $(0,2)$.

To the best of our understanding, the reason for this is the lack of knowledge
regarding well-structured $(n,m)$-graphs which can be used as target graphs
for homomorphisms. For $(n,m)=(1,0)$ or $(0,2)$, the Paley tournaments, signed
Paley graphs or the Tromp constructions play this role. The way we constructed
the target graph in Section 4 maybe one of the approaches towards tackling
this issue.

Acknowledgements: This work is partially supported by IFCAM project
“Applications of graph homomorphisms” (MA/IFCAM/18/39), SERB-SRG project
“Graph homomorphisms and its extensions” (SRG/2020/001575), SERB-MATRICS
“Oriented chromatic and clique number of planar graphs” (MTR/2021/000858), and
NBHM project “Graph theoretic model of Channel Assignment Problem (CAP) in
wireless network” (NBHM/RP-8 (2020)/Fresh).

## 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] B. Alspach.  The wonderful Walecki construction.  Bull. Inst. Combin. Appl, 52(52):7–20, 2008.
  * [3] J. Bensmail, C. Duffy, and S. Sen.  Analogues of cliques for (m, n)-colored mixed graphs.  Graphs and Combinatorics, 33(4):735–750, 2017.
  * [4] O. V. Borodin, A. V. Kostochka, J. Nešetřil, A. Raspaud, and É. Sopena.  On the maximum average degree and the oriented chromatic number of a graph.  Discrete Mathematics, 206(1-3):77–89, 1999.
  * [5] 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.
  * [6] R. C. Brewster, A. Kidner, and G. MacGillivray.  $k$-colouring $(m,n)$-mixed graphs with switching.  arXiv preprint arXiv:2203.08070, 2022.
  * [7] D. Chakraborty, S. Das, S. Nandi, D. Roy, and S. Sen.  On clique numbers of colored mixed graphs (accepted).  Discrete Applied Mathematics, 2021.
  * [8] R. Fabila-Monroy, D. Flores, C. Huemer, and A. Montejano.  Lower bounds for the colored mixed chromatic number of some classes of graphs.  Commentationes Mathematicae Universitatis Carolinae, 49(4):637–645, 2008.
  * [9] P. Hell and J. Nesetril.  Graphs and homomorphisms, volume 28.  OUP Oxford, 2004.
  * [10] A. V. Kostochka, É. Sopena, and X. Zhu.  Acyclic and oriented chromatic numbers of graphs.  Journal of Graph Theory, 24(4):331–340, 1997.
  * [11] E. Leclerc, G. MacGillivray, and J. M. Warren.  Switching $(m,n)$-mixed graphs with respect to abelian groups.  arXiv preprint arXiv:2110.01576, 2021.
  * [12] G. MacGillivray, S. Nasserasr, and F. Yang.  Colourings of $(m,n)$-coloured mixed graphs.  arXiv preprint arXiv:2010.09091, 2020.
  * [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] A. Montejano, A. Pinlou, A. Raspaud, and É. Sopena.  Chromatic number of sparse colored mixed planar graphs.  Electronic Notes in Discrete Mathematics, 34:363–367, 2009.
  * [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, 91:103222, 2021.
  * [18] C. S. J. Nash-Williams.  Edge-disjoint spanning trees of finite graphs.  Journal of the London Mathematical Society, 1(1):445–450, 1961\.
  * [19] J. Nešetřil and A. Raspaud.  Colored homomorphisms of colored mixed graphs.  Journal of Combinatorial Theory, Series B, 80(1):147–155, 2000\.
  * [20] P. Ochem.  Negative results on acyclic improper colorings.  In Discrete Mathematics and Theoretical Computer Science, pages 357–362. Discrete Mathematics and Theoretical Computer Science, 2005.
  * [21] P. Ochem, A. Pinlou, and S. Sen.  Homomorphisms of 2-edge-colored triangle-free planar graphs.  J. Graph Theory, 85(1):258–277, 2017.
  * [22] A. Raspaud and E. Sopena.  Good and semi-strong colorings of oriented planar graphs.  Information Processing Letters, 51(4):171–174, 1994.
  * [23] E. Sopena.  The chromatic number of oriented graphs.  Journal of Graph Theory, 25(3):191–205, 1997.
  * [24] É. Sopena.  Homomorphisms and colourings of oriented graphs: An updated survey.  Discrete Mathematics, 339(7):1993–2005, 2016.
  * [25] D. B. West.  Introduction to graph theory, volume 2.  Prentice hall Upper Saddle River, 2001.