11institutetext: Utrecht University, The Netherlands
11email<EMAIL_ADDRESS>22institutetext: Charles University in Prague,
Czechia
22email<EMAIL_ADDRESS>
# Role Coloring Bipartite Graphs

Sukanya Pandey 11 Vibha Sahlot 22

###### Abstract

A $k$-role coloring $\alpha$ of a graph $G$ is an assignment of $k$ colors to
the vertices of $G$ such that every color is used at least once and if any two
vertices are assigned the same color, then their neighborhood are assigned the
same set of colors. By definition, every graph on $n$ vertices admits an
$n$-role coloring.

While for every graph on $n$ vertices, it is trivial to decide if it admits a
$1$-role coloring, determining whether a graph admits a $k$-role coloring is a
notoriously hard problem for $k\geq 2$. In fact, it is known that $k$-Role
coloring is NP-complete for $k\geq 2$ on general graphs.

There has been extensive research on the complexity of $k$-role coloring on
various hereditary graph classes. Furthering this direction of research, we
show that $k$-Role coloring is NP-complete on bipartite graphs for $k\geq 3$
(while it is trivial for $k=2$). We complement the hardness result by
characterizing $3$-role colorable bipartite chain graphs, leading to a
polynomial time algorithm for $3$-Role coloring for this class of graphs. We
further show that $2$-Role coloring is NP-complete for graphs that are $d$
vertices or edges away from the class of bipartite graphs, even when $d=1$.

###### Keywords:

Role coloring Bipartite Graphs NP-hard Bipartite Chain Graphs

##  1 Introduction

Given a graph $G$, how would you assign $k$ colors to its vertices such that
every color is assigned to some vertex and if any two vertices get the same
color, then their neighborhood are assigned the same set of colors? Is such an
assignment possible for any input graph? Known as $k$-Role coloring, this
problem was motivated by applications in sociology. It was introduced as a
graph coloring problem by Borgatti and Everett [17] in 1991. The underlying
principle was that in a social network, individuals play the same role if they
relate in the same way to other individuals playing counterpart roles.

Formally, for any input graph $G$, a $k$-role coloring is an assignment of
exactly $k$ colors to its vertices such that if any two vertices get the same
color, then the set of colors assigned to their neighborhood is also the same.
That is, $k$-role coloring is a surjective map
$\alpha:V(G)\rightarrow\\{1,2,...,k\\}$ such that for all $u,v\in V(G)$, if
$\alpha(u)=\alpha(v)$ then $\alpha(N(u))=\alpha(N(v))$. For a function
$\alpha$ on domain $U$ and a set $A\subseteq U$, we abuse the notation
$\alpha(A)$ to denote the set $\\{\alpha(a)|a\in A\\}$.

Corresponding to a $k$-role assignment $\alpha$, the role graph $R$ is defined
as the graph with $V(R)=\\{1,2,...,k\\}$ and
$E(R)=\\{(\alpha(u),\alpha(v))|(u,v)\in E(G)\\}$. Since each color is assigned
to some vertex of $G$, it is easy to see that when $G$ is connected, the role
graph $R$ is also connected and $|V(R)|\leq|V(G)|$. Also, for all $v\in V(G)$,
$deg_{G}(v)\geq deg_{R}(\alpha(v))$.

We define the problem $k$-Role coloring as follows,

$k$-Role coloring Input: An undirected graph $G$ and an integer $k$. Question:
Does there exist a surjective function $\alpha:V(G)\rightarrow\\{1,2,...,k\\}$
satisfying: if $\alpha(u)=\alpha(v)$, then $\alpha(N(u))=\alpha(N(v))$ for all
$u,v\in V(G)$?

We can also define the problem in terms of role graphs. By $N_{G}(u)$ and
$N_{R}(v)$, we refer to the vertices in the neighborhood of the vertices $u\in
V(G)$ and $v\in V(R)$, respectively.

$R$-Role coloring Input: Undirected graphs $G$ and $R$. Question: Does there
exist a surjective function $\alpha:V(G)\rightarrow V(R)$ satisfying:
$\alpha(N_{G}(u))=N_{R}(\alpha(u))$ for all $u\in V(G)$?

This problem is equivalent to deciding if there exists a locally surjective
homomorphism between the graphs $G$ and $R$ [9]. Notice that given a role
graph $R$ and a role coloring $\alpha$ of $G$, we can find in polynomial time
if $\alpha$ agrees with $R$, that is whether $G$ is $R$-role colorable with
respect to $\alpha$. Also, given a role coloring $\alpha$ of $G$, we can find
whether $\alpha$ is a valid role coloring in polynomial time. Further, we can
also find the role graph $R$ corresponding to $\alpha$.

#### Previous Work:

Fiala et al. [9] showed that $R$-Role coloring can be solved in
$n^{\mathcal{O}(1)}$ time when

  * •

$R$ has no edges, or

  * •

it has a component isomorphic to a single loop-incident vertex, or

  * •

it is simple and bipartite and has at least one component isomorphic to a
$K_{2}$.

For all other cases, they proved that $R$-Role coloring is NP-complete. They
used this result to show that $k$-Role coloring is NP-complete for all $k\geq
3$. Prior to their work, it was shown by Roberts and Sheng [19] that $k$-Role
coloring is NP-complete for $k=2$. Hence, the following dichotomy exists for
$k$-Role coloring: Given any $n$ vertex graph $G$, $k$-Role coloring is
polynomial time solvable when $k=1$ or $n$ and NP-complete otherwise.

Various studies have been conducted to find the complexity of computing role-
coloring on hereditary graph classes. Sheng [20] gave a greedy algorithm to
compute a $2$-role coloring of chordal graphs in polynomial time.
Later,Heggernes et al. [14] showed that $k$-role coloring is NP-complete on
chordal graphs when $k\geq 3$. Following these results, Dourado [8] showed
that on split graphs, a subclass of chordal graphs, $3$-role coloring can be
decided in linear time, whereas for $k\geq 4$, $k$-role coloring is NP-
complete on split graphs. The problem remains NP-complete on planar graphs for
$k\geq 2$ [18]. The only known classes of graphs for which $k$-role coloring
can be decided in polynomial time for any fixed $k$, are Cographs [18] and
Proper Interval graphs [12].

Computational complexity and algorithms for many related variants of graph
colouring have been studied in the literature. One of the most common variants
is Perfect coloring. In this problem, the aim is to find the minimum number of
colors such that the endpoints of each edge in the graph are colored
differently. It is NP-complete to decide if a given graph admits a perfect
coloring with $k$ colors except for the cases $k\in\\{0,1,2\\}$ [10]. This
coloring problem remains NP-complete for $k=3$ even on $4$-regular planar
graphs [6]. A closely related variant is Ecological Coloring. A coloring is
ecological if any two vertices that are surrounded by the vertex set with the
same set of colors are colored the same. In this problem, our aim is to decide
whether there exists an ecological coloring for a given integer $k$ in a
graph. The computational complexity of this problem has also been studied for
different graph classes [2, 1, 5]. Another related problem is Coupon-coloring.
In this, we aim to find the maximum number of colors such that the open
neighborhood of each vertex contains all the colors [4]. This problem has been
investigated for several graph families [4, 11, 21].

#### Our Contribution:

Continuing the line of research on complexity of role coloring on hereditary
graph classes, we explore this problem when restricted to the class of
bipartite graphs. Due to the work of Fiala et al. [9], there exists a
complexity dichotomy for $R$-Role coloring on the class of bipartite graphs.
We build on this result and focus on the more general problem of $k$-Role
coloring on bipartite graphs. We show that $k$-Role coloring is NP-complete on
the class of bipartite graphs for all $k\geq 3$ (while it is trivial when
$k\leq 2$).

Note that the NP-completeness of $k$-Role coloring does not follow from the
NP-completeness of $R$-Role coloring, where $R$ is a graph on $k$ vertices
satisfying the characterization in [9]. To exemplify this, let us consider the
two variants of the problem with respect to the class of split graphs. Let
$R_{1}$ be a graph isomorphic to a $K_{2}$ with a self loop on exactly one end
point, and $R_{2}$ be isomorphic to a $K_{2}$ with self loops incident on both
the end points. It has been shown in [14] that $R_{2}$-Role coloring is NP-
complete on split graphs. However, $2$-Role coloring is trivially solvable in
polynomial time on split graphs with the corresponding role graph being
isomorphic to $R_{1}$.

Complementing our hardness result, we give a polynomial time algorithm for
$3$-Role coloring on bipartite chain graphs. Bipartite chain graphs are
bipartite graphs such that for the vertices in each partition, their
neighborhood can be ordered linearly with respect to inclusion. Equivalently,
they are bipartite graphs that exclude $2K_{2}$ as an induced subgraph. (A
$2K_{2}$ is a set of two disjoint edges).

Finally, we investigate the problem $2$-Role coloring on graphs that are $d$
vertices (or edges) away from bipartite graphs. We show that the problem is
NP-complete even when $d=1$. Henceforth, we shall refer to such a graph $G$ as
an “almost bipartite” graph. Parameterization by distance from a graph class
was first studied for the vertex coloring problem in [3]. We draw inspiration
from that and explore it with respect to $k$-Role coloring.

#### Organization of the paper:

The paper is organised as follows. We define the terminology and notations
used in this paper in Section 2.

Section 3 gives the proof for NP-completeness of $k$-Role coloring on
bipartite graphs, for fixed $k\geq 3$. The proof is divided into three parts.
We show separately the NP-completeness for each of the cases when
$k\in\\{3,4\\}$ and for the case when $k\geq 5$. In Section 4, we characterize
bipartite chain graphs that are $3$-role colorable, and in Section 5, we show
that $2$-role coloring is NP-complete on “almost bipartite graphs”.

##  2 Preliminaries

In this section, we state the graph theoretic terminology and notation used in
this paper. The set of consecutive integers from $1$ to $n$ is denoted by
$[n]$. Let $f:A\rightarrow B$ be a function. Then, for any non-empty set
$A^{\prime}\subseteq A$, by $f(A^{\prime})$, we denote the set $\\{f(a)|a\in
A^{\prime}\\}$. The vertex set and the edge set of a graph $G$ are denoted by
$V(G)$ and $E(G)$, respectively (or simply $V$ and $E$ when the underlying
graph $G$ is clear from the context). By $|G|$, we denote the order of $G$,
that is the number of its vertices $|V(G)|$. An edge between vertices $u$ and
$v$ is denoted as $(u,v)$.

For a vertex $v\in V(G)$, its neighborhood $N_{G}(v)$ is the set of all
vertices adjacent to it and its closed neighborhood $N_{G}[v]$ is the set
$N_{G}(v)\cup\\{v\\}$. This notation is extended to subsets of vertices as
$N_{G}[S]=\bigcup_{v\in S}N_{G}[v]$ and $N_{G}(S)=N_{G}[S]\setminus S$ where
$S\subseteq V(G)$. The degree of a vertex $v\in V(G)$, denoted by
$deg_{G}(v)$, is the size of $N_{G}(v)$. A pendant vertex is a vertex $v\in
V(G)$ with $deg_{G}(v)=1$. A graph $G^{\prime}$ is a _subgraph_ of $G$ if
$V(G^{\prime})\subseteq V(G)$ and $E(G^{\prime})\subseteq E(G)$. A graph
$G^{\prime}$ is an _induced subgraph_ of $G$ if for all $x,y\in V(G^{\prime})$
such that $(x,y)\in E(G)$, then $(x,y)\in E(G^{\prime})$. A path in a simple
graph is a sequence of distinct vertices with an edge between every pair of
consecutive vertices. The length of a path is the number of vertices in a
path. We denote a path on $n$ vertices by $P_{n}$. A pendant path is an
induced path attached to a vertex. For further details on graphs, refer to
[7].

A _hypergraph_ is a pair $H=(Q_{H},S_{H})$ where $Q_{H}$ is a finite set of
vertices and $S_{H}$ is a collection of non-empty subsets of $Q_{H}$ called
_hyper-edges_. We define the problem Hypergraph $k$-coloring as follows:
Hypergraph $k$-coloring Input: A connected hypergraph $H=(Q_{H},S_{H})$.
Question: Does there exist a coloring which assigns $k$ colors to vertices in
$Q_{H}$ such that no hyperedge $S\in S_{H}$ is monochromatic?

A hypergraph is called $k$-colorable if its vertices can be assigned $k$
colors such that none of its edges is monochromatic. A hypergraph is
$q$-uniform if each of its edges is a subset of its vertices of size $q$.
Lovász [16] showed that it is NP-hard to test $2$-colorability of $3$-uniform
hypergraphs. The following theorem by Khot implies that Hypergraph-k-coloring
is NP-hard on $3$-regular hypergraphs, for any fixed $k>1$.

###### Theorem 2.1

[15, Theorem 1.1] For every constant $\delta>0$, it is NP-hard to distinguish
whether an $n$-vertex $3$-uniform hypergraph is $3$-colorable or it contains
no independent set of size $\delta n$. In particular, it is NP-hard to color
$3$-colorable $3$-uniform hypergraphs with constantly many colors.

Following are some observations about the role graph that we use throughout
the paper without explicitly referring to them.

Observation 2.1 ([9]) If $G$ has an $R$-role coloring $\alpha$, then
$deg_{G}(u)\geq deg_{R}(\alpha(u))$ for all vertices $u\in V(G)$.

Observation 2.2 ([9]) If $G$ is a connected graph with a valid $k$-role
coloring $\alpha$, then the role graph corresponding to $\alpha$ must be
connected.
Proof. Since $G$ is connected, there is a path between every pair of vertices
$u,v$ $\in V(G)$. Let $P=u{x_{1}}{x_{2}}...{x_{l-2}}v$ be a path of length $l$
in $G$. Let $R$ be the role-graph corresponding to $\alpha$. By definition,
$\alpha(N_{G}(u))=N_{R}(\alpha(u))$. That is, $\alpha(x_{1})\in
N_{R}(\alpha(u))$. By induction on $l$, it can be shown that there exists a
path between $\alpha(u)$ and $\alpha(v)$ in $R$. Since the choice of $u$ and
$v$ was arbitrary, the claim is true for all pairs of vertices in $R$. Hence,
$R$ is connected.∎

##  3 NP-completeness of $k$-Role coloring on bipartite graphs

In this section, we prove that $k$-Role coloring is NP-complete on the class
of bipartite graphs, when $k\geq 3$.

###### Theorem 3.1

$k$-Role coloring is NP-complete on bipartite graphs, for any fixed $k\geq 3$.

Given a $k$-role coloring of $G$, we can verify if it is valid in
$n^{{\mathcal{O}}(1)}$ time by checking for each vertex $v$ in a color class,
if its neighborhood is assigned the same set of colors. Hence, $k$-role
coloring is in NP. We prove the NP-hardness in four parts. We separately deal
with the cases when $k=3$, $k=4$, and $k\geq 5$. We show a reduction from
Hypergraph-$2$-coloring for $k=3$ and $k\geq 5$, and from
Hypergraph-$3$-coloring for $k=4$.

For each case, the hypergraph is denoted by $H=(Q_{H},S_{H})$, where $Q_{H}$
is a finite set of vertices and $S_{H}$ is a collection of non-empty subsets
of $Q_{H}$ called hyperedges such that $|s|=3$ for each $s\in S_{H}$. The
corresponding _canonical incidence graph_ of the hypergraph $H=(Q_{H},S_{H})$
is a bipartite graph denoted as $G=(Q,S,E)$ with $Q$ and $S$ as the two parts
of the bipartition, and for all $q\in Q$ and $s\in S$, $(q,s)\in E(G)$ if and
only if the vertex corresponding to $q\in Q_{H}$ belongs to the hyperedge
$s\in S_{H}$.

###### Lemma 3.1

$3$-Role coloring is NP-complete on connected bipartite graphs.

###### Proof

Consider the incidence graph $G=(Q,S,E)$ of a hypergraph $H=(Q_{H},S_{H})$. To
each vertex $q\in Q$, we add a path on two vertices, such that the vertex
adjacent to $q$ is labeled $b_{q}$ and the other vertex adjacent to $b_{q}$ is
$a_{q}$. For each $q\in Q$, the sub-graph induced on $\\{q,b_{q},a_{q}\\}$ is
a “pendant path” and has length $3$. The new graph thus obtained is denoted by
$G^{\prime}$ (refer to Figure 1).

Figure 1: $G^{\prime}$ is a connected bipartite graph constructed from the
incidence graph $G$ of a $3$-regular hypergraph $H$. To each vertex $q\in Q$,
we add a $P_{2}$. The vertex adjacent to $q$ is denoted by $a_{q}$ and the
other one by $b_{q}$.

We claim that $H$ is a _y_ es instance of Hypergraph $2$-coloring if and only
if $G^{\prime}$ is a _y_ es instance of $3$-Role coloring. First, assume that
$H$ is a _y_ es instance and $\beta:Q_{H}\rightarrow\\{1,2\\}$ is a 2-coloring
of the vertices in $Q_{H}$.Then, the role coloring
$\alpha:V(G^{\prime})\rightarrow\\{1,2,3\\}$ can be defined as: for all $q\in
Q$, $\alpha(q)=\beta(q)$; $\alpha(b_{q})=3$; for all $s\in S$ $\alpha(s)=3$,
and $\alpha(a_{q})=j,j\in\\{1,2\\}\setminus\alpha(q)$. The coloring is
consistent as each vertex colored $1$ is adjacent to some vertex colored $3$.
Similarly, every vertex colored $2$ is adjacent to some vertex colored $3$.
Finally, since each hyperedge in $S_{H}$ is bichromatic, the corresponding
vertices in $S$ are each adjacent to some vertex colored $1$ and some vertex
colored $2$. Also, each vertex $b_{q}$ is adjacent to one vertex colored $1$
and one colored $2$. $G^{\prime}$ is, therefore, a _y_ es instance of $3$-role
coloring.

Conversely, suppose that $G^{\prime}$ is a _y_ es instance of $3$-role
coloring with the $3$-role coloring assignment $\alpha^{\prime}$ and the
corresponding role graph $R^{\prime}$. Without loss of generality, assume that
for some $q\in Q$, $\alpha^{\prime}(a_{q})=1$. Then,
$\alpha^{\prime}(b_{q})\neq 1$, or else the role graph would be disconnected
(with one component isomorphic to a single vertex with a loop). This is a
contradiction as $G^{\prime}$ is connected. So let $\alpha^{\prime}(b_{q})=2$.
Now, $\alpha^{\prime}(q)\neq 1$ and $\alpha^{\prime}(q)\neq 2$, otherwise role
graph would again be disconnected. So, let $\alpha^{\prime}(q)=3$. We prove
that $\alpha^{\prime}(S)=\\{2\\}$. The neighbor of $q$, say $s\in S$ could
either be colored $2$ or $3$. Suppose that $\alpha^{\prime}(s)=3$. This forces
one of the neighbors of $s$ to be colored $2$. Since, no hyperedge in $S_{H}$
is singleton, let there be a neighbor $q^{\prime}$ of $s$ such that
$\alpha^{\prime}(q^{\prime})=2$. Consider the vertex $b_{q^{\prime}}$ adjacent
to $q^{\prime}$. $\alpha^{\prime}(b_{q^{\prime}})\neq 1$ as that would force
$\alpha^{\prime}(a_{q^{\prime}})=2$. This is not possible because
$a_{q^{\prime}}$ has no neighbor colored $3$. Similarly,
$\alpha^{\prime}(b_{q}^{\prime})\neq 3$. Therefore, in a valid role coloring
of $G^{\prime}$, $\alpha^{\prime}(s)\neq 3$, for any $s\in S$. Also
$\alpha^{\prime}(s)\neq 1$ for $s\in S$ as $3$ is not adjacent to $1$ in the
role graph. Hence, $\alpha^{\prime}(s)=2$ for all $s\in S$. We define the
coloring of the hypergraph $\beta:Q_{H}\longrightarrow\\{1,3\\}$, as follows
as $\beta(q)=\alpha^{\prime}(q)$. This is a valid $2$-coloring of $H$, as
every $s\in S$ is adjacent to at least one vertex colored $1$ and at least one
vertex colored $3$. Hence, $H$ is a _y_ es instance of
Hypergraph-$2$-coloring.∎

###### Lemma 3.2

$4$-Role coloring is NP-complete on bipartite graphs.

###### Proof

Let $H$ be an instance of Hypergraph $3$-coloring such that $H$ is
$3$-regular. The incidence graph $G=(Q,S,E)$ is a connected bipartite graph,
with the bipartition $(Q,S)$. To construct the graph $G^{\prime}$ from $G$, we
add a pendant vertex $p^{s}$ to every vertex $s\in S$ (refer to Figure 2). Let
$P^{S}=\\{p^{s}\mid s\in S\\}$.

Figure 2: $G^{\prime}$ shown in the figure is a connected bipartite graph with
the bipartition $(Q\cup P^{S},S)$. It is constructed from the incidence graph
$G$ of the hypergraph $H$ by adding a pendant vertex to each vertex in $S$.

We now claim that $H=(Q_{H},S_{H})$ admits a $3$-coloring if and only if
$G^{\prime}$ admits a $4$-role coloring. Suppose that $H$ has a $3$-coloring,
$\beta$ : $Q_{H}\rightarrow\\{1,2,3\\}$. Then the role coloring for
$G^{\prime}$ is defined as: for each $q\in Q$, $\alpha(q)$=$\beta(q)$; for all
$s\in S$, $\alpha(s)=4$ and for each $s$, if $|\alpha(N_{Q}(s))|=2$, then
$\alpha(p^{s})=x\in\\{1,2,3\\}$ such that $x\notin\alpha(N_{Q}(s))$.
Otherwise, arbitrarily assign any of the three colors to $p^{s}$.
Corresponding to $\alpha$, the role graph $R$ is defined as
$V(R)=\\{1,2,3,4\\}$ and $E(R)=\\{(1,4),(2,4),(3,4)\\}$. As $H$ is a _y_ es
instance of Hypergraph $3$-coloring, every vertex $s\in S$ colored $4$ is
adjacent to vertices colored $1$, $2$ and $3$ in $Q\cup P^{s}$. Thus, $\alpha$
is consistent with $R$.

Conversely, suppose that $G^{\prime}$ has a valid $4$-role coloring
$\alpha^{\prime}:V(G)\rightarrow\\{1,2,3,4\\}$, and the corresponding role
graph is $R^{\prime}$.

####  Claim 1.

In any valid $4$-role coloring of $G^{\prime}$,
$\alpha^{\prime}(S)\cap\alpha^{\prime}(Q)=\emptyset$.

Proof. Towards a contradiction, let us suppose that there exists an $s\in S$
such that $\alpha^{\prime}(s)=\alpha^{\prime}(q)=x$, for some $q\in Q$ and
$x\in\\{1,2,3,4\\}$. Then $\alpha^{\prime}(p^{s})\neq x$ or else $R^{\prime}$
would be disconnected with a component containing $x$ with a loop. By
Observation 2.2, this is not possible. Therefore, let
$\alpha^{\prime}(p^{s})=y$, such that $y\in\\{1,2,3,4\\}\setminus\\{x\\}$. For
$\alpha^{\prime}$ to be valid, $q$ must have a neighbour $s^{\prime}\in S$
such that $\alpha^{\prime}(s^{\prime})=y$. Consider $p^{s^{\prime}}$. Since
$N_{R^{\prime}}(y)=\\{x\\}$, $\alpha^{\prime}(p^{s^{\prime}})$ must be equal
to $x$. However, by Observation 1.1, this is not possible because
$deg_{R^{\prime}}(x)>1$. ∎

####  Claim 2.

When $|\alpha^{\prime}(Q)|=1$, $G^{\prime}$ does not admit any valid $4$-role
coloring.

Proof. Towards a contradiction, assume that $Q$ is a monochromatic set.
Without loss of generality let $\alpha^{\prime}(q)=1$, for each $q\in Q$.

By claim 1, no vertex in $S$ is assigned the color $1$. We show that none of
the pendant vertices in $P^{s}$ gets the color $1$. Suppose that there exists
a vertex $p^{s}$ of $P^{s}$ colored $1$. Suppose that $\alpha^{\prime}(s)$ =
$2$. Since the vertices colored $1$ are only adjacent to vertices colored $2$,
$S$ must be monochromatic with the color $2$, as by our assumption $Q$ is
monochromatic with the color $1$. Therefore, $P^{s}$ must be monochromatic
with the color $1$ assigned to its vertices as the vertex $s$ colored $2$ is
only adjacent to vertices colored $1$, a contradiction to $\alpha^{\prime}$
being a $4$-role coloring of $G^{\prime}$. Therefore, it follows that
$1\notin\alpha^{\prime}(P^{s}\cup S)$.

We now prove that $P^{s}$ must be monochromatic. Towards a contradiction,
suppose that there exist vertices $p^{s}$ and $p^{s^{\prime}}$ colored $2$ and
$3$, respectively. Then $\alpha^{\prime}(s)\neq 2$ and
$\alpha^{\prime}(s^{\prime})\neq 3$, or else every vertex colored $2$ or $3$
could only have neighbors of the same color. As every $s\in S$ has a neighbor
in $Q$ colored $1$, we know that that is not possible. This implies that $s\in
S$ is adjacent to vertices colored $1$ and $2$, whereas the $s^{\prime}\in S$
has neighbors colored $1$ and $3$. Suppose that we color $s$ with $4$, then
there is no color that can be assigned to $s^{\prime}$. This is a
contradiction to $G^{\prime}$ admitting a valid $4$-role coloring. Hence,
$P^{s}$ must be monochromatic.

Let $\alpha^{\prime}(P^{s})$=$\\{2\\}$. That forces $S$ to be monochromatic
with a third color, say $3$, which again contradicts the assumption that
$G^{\prime}$ admits a valid $4$-role coloring. Therefore, when $Q$ is
monochromatic, $G^{\prime}$ does not admit any $4$-role coloring. ∎

####  Claim 3.

When $|\alpha(Q)|=2$, $G^{\prime}$ has a valid $4$-role coloring.

Proof. Let the colors assigned to vertices in $Q$ by $\alpha^{\prime}$ be $1$
and $2$.

By claim 1, $\alpha^{\prime}(S)\cap\\{1,2\\}=\emptyset$. Next, we show that
the pendants in $\alpha^{\prime}(P^{s})\cap\alpha^{\prime}(Q)=\emptyset$.
Suppose that there exists a pendant vertex $p^{s}$ colored $1$. Let its
neighbor $s\in S$ be colored $3$. Also, $3$ must be adjacent to a different
color, say $2$, otherwise the role graph would be disconnected with a
component containing just $1$ and $3$. This means that no pendant receives the
color $3$ as the degree of $3$ in $R^{\prime}$ is at least equal to 2. If
there exists a pendant colored $2$, then its neighbor must be colored $3$ as
well. So, $N_{R^{\prime}}(1)=N_{R^{\prime}}(2)=\\{3\\}$ and
$N_{R^{\prime}}(3)=\\{1,2\\}$. All the vertices in $Q$ are adjacent only to
vertices in $S$. Hence, $S$ is monochromatic with the role $3$. This is a
contradiction to $\alpha^{\prime}$ being a $4$-role coloring. This implies
that $1\notin\alpha(P^{s})$ and $2\notin\alpha^{\prime}(P^{s})$. This proves
our claim that $\alpha(Q)\cap\alpha^{\prime}(P^{s})$ = $\emptyset$.

Thus, the only possible role coloring in this case is
$\alpha^{\prime}(Q)\in\\{1,2\\}$, $\alpha^{\prime}(S)=\\{3\\}$, and
$\alpha^{\prime}(P^{s})=\\{4\\}$. So, every vertex in $S$ is forced to be
adjacent to at least one vertex having color $1$ and at least one vertex
having color $2$.

The corresponding coloring for the hypergraph $H$ is as follows: for some
$q^{\prime}\in Q_{H},\beta(q^{\prime})=3$ and $\forall q\in
Q_{H}\setminus\\{q^{\prime}\\},\beta(q)=\alpha(q)$. Clearly, no hyperedge is
monochromatic and $|\beta(Q_{H})|=3$. ∎

####  Claim 4.

When $|\alpha^{\prime}(Q)|=3,G^{\prime}$ admits a valid $4$-role coloring.

Proof. Suppose that the colors assigned to $Q$ by $\alpha^{\prime}$ are
$\\{1,2,3\\}$.

By Claim 1, $\alpha^{\prime}(S)\cap\alpha^{\prime}(Q)=\emptyset$. Therefore,
$\alpha^{\prime}(S)=\\{4\\}$ and $R^{\prime}=(\\{1,2,3,4\\},$
$\\{(1,4),(2,4),(3,4)\\})$. We propose the following coloring for the
hypergraph $H$. For every $q\in Q_{H}$, $\beta(q)=\alpha^{\prime}(q)$ such
that $q\in Q$ is the corresponding vertex in $G^{\prime}$. ∎

####  Claim 5:

When $|\alpha^{\prime}(Q)|=4$, no valid $4$-role coloring of $G^{\prime}$
exists.

Proof By Claim 1, $\alpha^{\prime}(Q)\cap\alpha^{\prime}(S)=\emptyset$.
Therefore, there is no color that can be assigned to $S$ in a valid $4$-role
coloring of $G^{\prime}$. ∎

∎

###### Lemma 3.3

$k$-role coloring is NP-complete on connected bipartite graphs, for any fixed
$k\geq 5$.

###### Proof

We show a reduction from Hypergraph-2-coloring. Let $H=(Q_{H},S_{H})$ be an
instance of Hypergraph-2-coloring such that $H$ is $3$-regular. Let $G=(Q\cup
S,E)$ be its canonical incidence graph. We create the instance
$G^{\prime\prime}$ of $k$-Role coloring by attaching to each $s\in S$ a “
_pendant path_ ” $p^{s}$ = $\\{p^{s}_{1},...,p^{s}_{k-3}\\}$. Each path
$p^{s}$ is attached to the vertex $s$ through the edge ($p^{s}_{k-3},s)$. The
set of all the pendant paths is denoted by $P^{S}$. Refer to Figure 3.

Figure 3: We show the graph $G^{\prime\prime}$ in this figure which is a
connected bipartite graph. The set $Q$ contains a vertex $q$ for every vertex
$q\in Q_{H}$. The set $S$ contains a vertex $s$ for each hyperedge $s\in
S_{H}$. To each $s\in S$ we attach a path of length $k-3$ denoted by $p^{s}$.

We prove that $H$ has a $2$-coloring if and only if $G^{\prime\prime}$ admits
a $k$-role coloring. Suppose that the hypergraph $H$ has a $2$-coloring,
$\beta$ : $Q_{H}\longrightarrow\\{1,2\\}$. Let the role coloring for
$G^{\prime\prime}$ be the following: $\alpha(q)$ =$\beta(q)$, for each $q\in
Q$; $\alpha(s)$= $3$, for all $s\in S$; $\alpha({p^{s}}_{k-3})=4$, for all
$s\in S$; $\alpha({p^{s}_{j}})$= $k-j+1$, where $1\leq j\leq k-4$. This gives
us a $k$-role coloring of $G^{\prime\prime}$ with the corresponding role-graph
$R$ defined as: $V(R)=\\{1,2,\dots,k\\}$ and
$E(R)=\\{(1,3),(2,3)\\}\cup\\{(j,j+1)\mid 3\leq j\leq k-1\\}$.

We now prove the converse. We assume that $G^{\prime\prime}$ has a valid
$k$-role coloring $\alpha^{\prime}$.

#### Claim 1:

In any valid $k$-role coloring of $G^{\prime\prime}$, each vertex of any
pendant path $p^{s}$ gets a distinct color.

Proof. Assume the contrary. Let $p^{s}_{i}$ be the first vertex such that its
neighbour $p^{s}_{i+1}$ gets the same color. For convenience, let us assume
that $\alpha^{\prime}(p^{s}_{j})=j$ for $1\leq j\leq i$. Then,
$\alpha^{\prime}(p^{s}_{i+2})=i-1$ because any vertex colored $i$ needs a
neighbour coloured $i-1$ and the only neighbour of $p^{s}_{i+1}$ other than
$p^{s}_{i}$ is $p^{s}_{i+2}$. Similarly, $\alpha^{\prime}(p^{i+3})=i-2$, and
so on. Therefore the role graph $R^{\prime}$ corresponding to
$\alpha^{\prime}$ would be disconnected with a component isomorphic to a
$P_{i}$ with a loop on an end point. This is not possible as
$G^{\prime\prime}$ is connected. ∎

#### Claim 2:

$\alpha^{\prime}(Q)\cap\alpha^{\prime}(S\cup P^{S})=\emptyset$.

Proof. Suppose that there exists a vertex $s\in S$ such that
$\alpha^{\prime}(s)=\alpha^{\prime}(q)=x$ for some $q\in Q$ and some
$x\in\\{1,2,\ldots k\\}.$ Consider its pendant path $p^{s}$. By the previous
claim, there must be $k-3$ distinct colors given to the vertices of $p^{s}$.
Without loss of generality, let these colors be $1,\ldots k-3$ such that
$\alpha^{\prime}(p^{s}_{j})=j$ for all $1\leq j\leq k-3$. Therefore, $x$ must
be adjacent to $k-3$ in $R^{\prime}$. If $x=k-3$ then $s$ must have a
neighbour $q^{\prime}\in Q$ colored $k-4$. $q^{\prime}$ in turn must be
adjacent to some $s^{\prime}\in S$ colored $k-5$. Consider the pendant path
$p^{s^{\prime}}$. Since $k-5$ is only adjacent to either $k-4$ or $k-6$,
$p^{s^{\prime}}_{k-3}$ must get one of the two colors. In the former case
$\alpha^{\prime}(p^{s^{\prime}}_{2})=1$ and since $1$ is adjacent only to $2$,
there is no color that can be given to $p^{s^{\prime}}_{1}$. In the latter
case,
$\alpha^{\prime}(p^{s^{\prime}}_{3})=1,\alpha^{\prime}(p^{s^{\prime}}_{2})=2$
but there is no valid color that can be given to $p^{s^{\prime}}_{1}$ as
$p^{s^{\prime}}_{2}$ needs a neighbour colored $3$ but
$deg_{R^{\prime}}(3)>1$.

Therefore, let $x=k-2$. Since $\alpha^{\prime}(q)=k-2$, $q$ needs at least one
neighbour $s^{\prime}\in S$ colored $k-3$ as $x$ is adjacent to $k-3$ in
$R^{\prime}$. The pendant path attached to $s^{\prime}$ gets the colors
$k-4,\ldots 1$ in order such that $\alpha^{\prime}(p^{s^{\prime}}_{k-3})=k-4$
and $\alpha^{\prime}(p^{s^{\prime}}_{2})=1$. There is no valid color that can
be given to $p^{s^{\prime}}_{1}$.

Similarly if there exists a vertex $q\in Q$ such that
$\alpha^{\prime}(q)\in\\{1,2,\ldots k-3\\}$, then its neighbour $s\in S$ must
get a color $i\in\\{1,2,\ldots k-3\\}$ such that $i=\alpha^{\prime}(q)+1$ or
$i=\alpha^{\prime}(q)-1$. As above, there would be no valid colour that can be
given to $p^{s}_{1}$. This is a contradiction to the validity of
$\alpha^{\prime}$. ∎

#### Claim 3:

In any valid $k$-role coloring of $G^{\prime\prime}$, $Q$ cannot be
monochromatic.

Proof. Assume the contrary. Without loss of generality, let
$\alpha^{\prime}(Q)=k$. By Claim 2,
$\alpha^{\prime}(Q)\cap\alpha^{\prime}(S\cup P^{S})=\emptyset$. Therefore, let
$s\in S$ get the color $k-1$. We shall show that $S$ is monochromatic and
$\alpha^{\prime}(S)=k-1$. None of the vertices in $p^{s}$ could get the color
$k$ by claim 2. So, $p^{s}_{k-3}$ could either get $k-1$ or a distinct color
$k-2$. By claim 1, each vertex in $p^{s}$ gets a distinct color. Let the set
of colors given to $p^{s}$ be $\\{k-1,k-2,\ldots 3\\}$ in the former case and
$\\{k-2,\ldots 2\\}$ in the latter. Suppose that $q$ has another neighbour
$s_{1}\in S$ colored $1$. Then, $p^{s_{1}}_{k-3}$ could get color $2$ in the
former case, but there would be no valid color that could be given to
$p^{s_{1}}_{k-4}$ as none of the other colors are adjacent to $2$. In the
latter case, there would be no valid color that could be given to
$p^{s_{1}}_{k-3}$. Therefore, $S$ must be monochromatic with $k-1$. $P^{S}$
gets additional $k-3$ colors and the total number of colors assigned are
$k-1$. This is a contradiction to $\alpha^{\prime}$ being a $k$-role coloring.
∎

∎

##  4 3-role coloring bipartite chain graphs

Definition[13, 22] A bipartite graph is a chain graph if and only if the
neighborhood of the vertices of each partition can be linearly ordered with
respect to inclusion. Equivalently, a bipartite graph is a chain graph if and
only if it is $2K_{2}$-free.

A universal vertex333Our definition of “universal vertex” is different from
the standard definition. is a vertex in one partition of a bipartite graph
that is adjacent to every vertex in the other partition.

Throughout this section, we assume $G=(X,Y,E)$ is a bipartite chain graph.
$U_{X}$ and $U_{Y}$ are the sets of universal vertices in the partitions $X$
and $Y$, respectively. Likewise, $P_{X}$ and $P_{Y}$ are sets of pendant
vertices in the partitions $X$ and $Y$. Note that $P_{X}$ and/or $P_{Y}$ may
be empty. We also assume $|V(G)|\geq 3$ or else, $G$ is trivially a _n_ o
instance. In the rest of this section, we aim to prove the following theorem.

###### Theorem 4.1

A bipartite chain graph $G=(X,Y,E)$, where $|X\cup Y|\geq 3$, has a valid
$3$-role coloring if and only if any of the following is true:

  1. 1.

$G$ is not connected

  2. 2.

$|X|=1$ or $|Y|=1$

  3. 3.

$|X|=2$ (or $|Y|=2$) and both the vertices of $X$ (or $Y$) are universal
vertices.

  4. 4.

$|X|=2$, $|Y|>2$ and $|Y\setminus P_{Y}|>1$. (symmetrically, $|Y|=2$, $|X|>2$
and $|X\setminus P_{X}|>1$)

  5. 5.

$|X|\geq 3$ and $|Y|\geq 3$.

Furthermore, given any bipartite chain graph we can check in polynomial time
whether it has a valid $3$-role coloring.

###### Proof

We shall first prove that in each of the cases above, $G$ has a valid $3$-role
coloring. Thereafter, we show that $G$ does not admit a valid $3$-role
coloring in any other case.

  1. 1.

We prove that there exists a valid $3$-role coloring of $G$, when it is
disconnected and $|G|\geq 3$. Note that edges are present in at most one of
the connected components of a disconnected bipartite chain graph, otherwise it
would contain a $2K_{2}$. So there are two cases, first when $G$ is edgeless.
As we have assumed that there are at least three vertices, thus the graph can
be trivially $3$-role colored with the corresponding role graph being an
edgeless graph on $3$ vertices. In the second case, exactly one component has
edges. We color the connected component with edges using colors $1$ and $2$.
This can be done as the graph is bipartite. Color the rest of the isolated
vertices with color $3$. Note that this is a valid $3$-role coloring with role
graph $R$ such that $V(R)=\\{1,2,3\\}$ and $E(R)=\\{(1,2)\\}$.

  2. 2.

Henceforth, we assume that $G$ is connected. As there are no isolated vertices
in $G$, the linear ordering on the neighborhood of vertices in each partition
ensures that the largest neighborhood contains all the vertices in the
partition. Hence, each partition has at least one universal vertex. We claim
that $G$ has a valid $3$\- role coloring if $|X|=1$. The only vertex $v\in X$
is universal. Let $\alpha(v)=1$ and for a vertex $w\in Y$ $\alpha(w)=2$.
Assign color $3$ to the rest of vertices in $Y$. It is easy to check that this
coloring agrees with the role graph $R=(\\{1,2,3\\},\\{(1,2),(1,3)\\})$. We
can argue symmetrically for $Y$.

  3. 3.

Assume that $|X|=2$ and $X=\\{u,v\\}$. We show that $G$ has a valid $3$-role
coloring if both the vertices in $X$ are universal. Assign color $1$ to $u$,
color $2$ to $v$ and color $3$ to vertices of $Y$. The corresponding role
graph is defined as $R=(\\{1,2,3\\},\\{(1,3),(2,3)\\})$.

  4. 4.

Suppose that $|X|=2$ and $|Y|>2$, such that there exist at least one vertex in
$Y$ that is not a pendant vertex. As before, let $X=\\{u,v\\}$ such that $u$
is universal, bur $v$ is not. First, let $P_{X}=\emptyset=P_{Y}$. Then, we
define the role coloring assignment as $\alpha(u)=1$, $\alpha(Y)=\\{2\\}$; and
$\alpha(v)=3$. Each vertex in $Y$ has a neighbor colored $1$, as $u$ is
universal. Since there are no pendants in $G$, each of them has at least one
other neighbor in $X$. This ensures that each vertex colored $2$ also has a
neighbor colored $3$.

Next, we assume that $P_{Y}$ is non-empty. Let $Y=P_{Y}\cup T$ where $T$ is
the set of vertices of degree two. We prove that $G$ has a valid $3$-role
coloring if $|T|\geq 2$. Let $\alpha(a)=1$, for some $a\in P_{Y}$. We cannot
assign $1$ to $u$, due to the connectivity constraint of the role graph, by
Observation 2.2. So, let $\alpha(u)=2$. So $(1,2)\in E(R)$. Let $t\in T$ be a
neighbor of $v$. By assumption 4., $|T|\geq 2$. We define the role coloring
as: $\alpha(v)=\alpha(u)=2$, $\alpha(t)=1$. Also, color all the vertices in
$P_{Y}$ with the color $1$ and all the remaining vertices in
$T\setminus\\{t\\}$ with the color $3$. It is easy to verify that this
coloring is consistent with the role graph
$R=(\\{1,2,3\\},\\{(1,2),(2,3)\\})$.

  5. 5.

We finally show that $G$ has a valid $3$-role coloring if it is connected and
$|X|\geq 3$, and $|Y|\geq 3$. We demonstrate a $3$-role coloring for each of
the following sub-cases:

####  Sub-case 1.

$P_{X}=P_{Y}=\emptyset$
Let $\alpha(u)=\\{1\\}$ for some $u\in U_{X}$, $\alpha(Y)=\\{2\\}$, and
$\alpha(w)=3$, for all $w\in G\setminus N[U_{X}]$. The validity follows from
the preceding case 4..

####  Sub-case 2.

$P_{X}\neq\emptyset$, and $P_{Y}=\emptyset$
The unique neighbor of a pendant in $P_{X}$ must be a universal vertex.
Moreover, $|U_{Y}|=1$. Suppose that $|U_{Y}|\geq 2$. Then every vertex in $X$
would have degree at least 2. This contradicts our assumption that
$P_{X}\neq\emptyset$.

Now, we define the role coloring of vertices in $G$ as follows:
$\alpha:V(G)\longrightarrow\\{1,2,3\\}$, $\alpha(y)=1$, for all $y$ in $Y$;
$\alpha(u)=2$, where $u\in U_{X}$ and $\alpha(X\setminus\\{u\\})=3$. Every
vertex colored $1$ is adjacent to the vertex colored $2$ (that is $u$) and at
least one vertex colored $3$. Thus, $\alpha$ is a valid role-coloring of $G$.

####  Sub-case 3.

Pendants occur in both the partitions.
Note that $|U_{X}|=|U_{Y}|=1$. Let $x$ and $y$ be the universal vertices in
$X$ and $Y$, respectively. We first assume that $N(x)\cup N(y)$ does not
induce an independent set. Let $alpha:V\longrightarrow\\{1,2,3\\}$ be a role
coloring of $G$, as before.

In this case, $\alpha(P_{X}\cup P_{Y})=\\{1\\}$; $\alpha(x)=\alpha(y)=2$;
$\alpha(G\setminus\\{\\{x\\}\cup\\{y\\}\cup P_{X}\cup P_{Y}\\})=\\{3\\}$.
Therefore, every vertex colored $1$ is adjacent only to vertices colored $2$.
The two vertices colored $2$ are adjacent to all the vertices in each
partition and hence adjacent to both $1$ and $3$. Since the neighborhood of
$x$ and $y$ do not form an independent set, at least one vertex in each
partition is not a pendant. Hence, there are vertices colored $3$ which are
adjacent to each other and the universal vertices and $\alpha$ is a valid role
coloring of $G$.

Now, suppose that $N(x)\cup N(y)$ is an independent set. Then, $|N(x)|\geq 2$
and $|N(y)|\geq 2$, as each partition has at least $3$ vertices. Define the
role coloring as: $\alpha(x)=\alpha(y)=2$. Color any one neighbor each of $x$
and $y$ with the color $1$ and another neighbor with the color $3$. The
remaining vertices can be arbitrarily given the colors $1$ or $3$. $\alpha$ is
a valid role coloring of $G$, in this case too.

We claim that if $G$ has a valid $3$-role coloring, it must satisfy at least
one of the conditions in Theorem 4.1.1. Towards a contradiction suppose that
none of the cases hold. Then, $|X|=2$, one of its vertices is not universal,
$|Y|=2$ and $|Y\setminus P_{Y}|=1$. We also assume that $X=\\{u,v\\}$, and
that $u$ is universal, whereas $v$ is not. This implies that $G$ is isomorphic
to a $P_{4}$, which is a _n_ o instance for $3$-Role coloring.

To see that, assign the color $1$ to $a\in P_{Y}$. By Observation 2.2, the
role graph $R$ corresponding to $\alpha$ must be connected. Thus, the neighbor
of $u$ must get a new color, say $2$. If possible, let $\alpha(v)=1$. It
forces $\alpha(t)=2$. This contradicts that $\alpha$ is a $3$-role coloring of
$G$. So let $\alpha(v)=2$. If $\alpha(t)=2$, it forces the role graph to have
a single vertex labeled $2$, with a self loop which contradicts the fact that
$(1,2)\in E(R)$. If $\alpha(t)=3$, then $v$ has no neighbor colored $1$, which
is again a contradiction as $(1,2)\in E(R)$. Therefore, let $\alpha(v)=3$.
Then, $\alpha(t)\neq 1$, as $t$ is adjacent to vertices colored $2$ and $3$,
but the degree of the color $1$ in $R$ is equal to one. Also, $\alpha(t)\neq
2$, as $t$ has no neighbor colored $1$. If possible, let $\alpha(t)=3$. This
is not a valid role coloring as $\alpha(v)=\alpha(t)=3$ but
$\alpha(N(v))=\\{1,3\\}\neq\\{2,3\\}=\alpha(N(t))$. Hence if $G$ is isomorphic
to a $P_{4}$, $G$ is a no instance of $3$-Role coloring.

There are a finite number of cases for which $G$ can be $3$-role colored, and
each case can be verified in $\mathcal{O}(n+m)$ time, where $n$ and $m$ are
the number of vertices and edges of $G$. Since we have shown that a valid
$3$-role coloring exists of these cases alone, it follows that each of them is
a _y_ es instance of $3$-Role coloring and every other case is a _n_ o
instance. Hence, we can decide $3$-role coloring on bipartite chain graphs in
$\mathcal{O}(n+m)$. ∎

##  5 Almost bipartite graphs

An “almost bipartite” graph is a graph that has a set of at most $d$ vertices
or $d$ edges, $d$ being a constant, which on deletion yield a bipartite graph.
Here, we prove that $2$-Role coloring is NP-complete on the class of almost
bipartite graphs, even if $d=1$.

###### Theorem 5.1

$2$-Role coloring is NP-complete on the class of almost bipartite graphs.

###### Proof

We know from [9] that given a connected bipartite graph $G$ and a role graph
$R$ isomorphic to an edge with a self loop incident on one of its end points,
deciding if $G$ has a valid $R$-role coloring, is NP-complete. Thus, we show a
reduction from this problem to $2$-Role coloring on almost bipartite graphs
with $d=1$. Refer to Figure 4.

Figure 4: The figure depicts a connected bipartite graph with the bipartition
$X$ and $Y$. To the bipartite graph the vertices $a,b,\,\text{and},c$ are
added. Deleting the vertex $b$ yields a bipartite graph back.

Let $R$ be defined as $V(R)=\\{1,2\\}$ and $E(R)=\\{(1,1),(1,2)\\}$. Let $G$
be a connected bipartite graph and let $x\in V(G)$. We construct $G^{\prime}$
from $G$ by adding to it 3 vertices $a,b$ and $c$ and the edges
$(a,b),(a,c),(x,a),(x,b)$. $G^{\prime}$ is not bipartite as it contains a
triangle, namely, $abx$. It is 1 vertex (remove $b$) and 1 edge (remove
$(x,b)$) away from the bipartite graph $G$.

Suppose that $G$ is a _y_ es instance of $R$-Role coloring. Then, it has a
role coloring $\alpha$, with the corresponding role graph being isomorphic to
$R$. Then we can extend $\alpha$ to the vertices of $G^{\prime}$ as follows:
If $\alpha(x)=1$, then color $a$ with $1$ and $b$ and $c$ with $2$. If
$\alpha(x)=2$ then color both $a$ and $b$ with $1$ and $c$ with $2$. Thus,
$G^{\prime}$ has an $R$-role coloring and therefore a valid $2$-role coloring.

Conversely, suppose that $G^{\prime}$ has a $2$-role coloring
$\alpha^{\prime}$. First assume that $\alpha^{\prime}(a)=1$. If both $x$ and
$b$ received the color $1$, then $b$ would only be adjacent to vertices
colored $1$. Thus, the role graph would be disconnected, as $1$ could only be
adjacent to itself. This is not possible as $G^{\prime}$ is a connected graph.
Hence, at least one of them gets the color $2$. Also, $c$ gets color $2$ as
its degree is one, but the degree of $1$ in $R$ is two. Now, there are two
possible subcases:
Subcase 1: $\alpha^{\prime}(b)=1$ and $\alpha^{\prime}(x)=2$.
Any other neighbor $y$ of $x$ in $G^{\prime}$ must be colored $1$. As per the
assignment $\alpha^{\prime}$, $y$ must have a neighbor colored $1$ and another
neighbor colored $2$. Therefore, $\alpha^{\prime}$ restricted to $G$ is an
$R$-role coloring, and $G$ has a valid $R$-role coloring.
Subcase 2: $\alpha^{\prime}(b)=2$ and $\alpha^{\prime}(x)=1$
Suppose that all the other neighbors of $x$ in $G^{\prime}$ are colored $2$.
Those neighbors would, in turn, be adjacent to vertices colored $1$ in the
partition of $x$. These vertices colored $1$ must obey the coloring
$\alpha^{\prime}$, and have neighbors of both the colors $1$ and $2$. Once
again, restricting $\alpha^{\prime}$ to $G$, gives an $R$-role coloring of
$G$, showing that $G$ has a valid $R$-role coloring.

Symmetrically, if $\alpha^{\prime}(a)=2$, the role graph is again isomorphic
to $R$. Hence, if $G^{\prime}$ has a $2$-role coloring it has an $R$-role
coloring and therefore $G$ has a valid $R$-role coloring. ∎

##  6 Conclusions

We have proved that $k$-Role coloring, for a fixed $k\geq 3$, remains NP-
complete even when restricted to the class of bipartite graphs. We have also
shown that $2$-Role coloring, which is polynomial time solvable on bipartite
graphs, becomes NP-complete on graphs that are a constant number of vertices
or edges away from bipartite graphs. We do not know of any existing literature
on $k$-Role coloring on graphs close to a specific hereditary class of graphs.
This opens avenues for further research.

On a subclass of $2K_{2}$-free graphs, i.e, bipartite chain graphs, we have
shown that $3$-Role coloring can be solved in polynomial time. However, the
complexity of $k$-Role coloring, for $k$= $2$ and $3$, is open on general
$2K_{2}$-free graphs.

### Acknowledgements

The authors would like to thank Professor Venkatesh Raman for several fruitful
discussions and his invaluable feedback. We are also grateful to the anonymous
reviewers whose thorough and precise feedback helped us improve the paper.

## References

  * [1] Borgatti, S.P., Everett, M.G.: Graph colorings and power in experimental exchange networks. Social Networks 14(3), 287–308 (1992), special Issue Location of Power in Exchange Networks
  * [2] Borgatti, S.P., Everett, M.G.: Ecological and perfect colorings. Social Networks 16(1), 43–55 (1994)
  * [3] Cai, L.: Parameterized complexity of vertex colouring. Discrete Applied Mathematics 127(3), 415 – 429 (2003)
  * [4] Chen, B., Kim, J.H., Tait, M., Verstraete, J.: On coupon colorings of graphs. Discrete Applied Mathematics 193, 94–101 (2015)
  * [5] Crescenzi, P., Ianni, M.D., Greco, F., Rossi, G., Vocca, P.: Making role assignment feasible: A polynomial-time algorithm for computing ecological colorings. In: Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers. Lecture Notes in Computer Science, vol. 5344, pp. 90–100 (2008)
  * [6] Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Mathematics 30(3), 289–293 (1980)
  * [7] Diestel, R.: Graph Theory. Springer-Verlag (2005)
  * [8] Dourado, M.C.: Computing role assignments of split graphs. Theor. Comput. Sci. 635, 74–84 (2016)
  * [9] Fiala, J., Paulusma, D.: A complete complexity classification of the role assignment problem. Theor. Comput. Sci. 349(1), 67–81 (2005)
  * [10] Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified np-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)
  * [11] Goddard, W., Henning, M.A.: Thoroughly dispersed colorings. Journal of Graph Theory 88, 174–191 (2018)
  * [12] Heggernes, P., van ’t Hof, P., Paulusma, D.: Computing role assignments of proper interval graphs in polynomial time. J. Discrete Algorithms 14, 173–188 (2012)
  * [13] Heggernes, P., Kratsch, D.: Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic J. of Computing 14(1), 87–108 (jan 2007)
  * [14] van’t Hof, P., Paulusma, D., van Rooij, J.M.M.: Computing role assignments of chordal graphs. Theor. Comput. Sci. 411(40-42), 3601–3613 (2010)
  * [15] Khot, S.: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. pp. 23–32 (2002)
  * [16] Lovász, L.: Coverings and colorings of hypergraphs. In: 4th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica Publishing, Winnipeg, Proceedings. p. 3–12 (1973)
  * [17] Martin G. Everett, S.B.: Role colouring a graph. Mathematical Social Sciences pp. 183–188 (1991)
  * [18] Purcell, C., Rombach, M.P.: On the complexity of role colouring planar graphs, trees and cographs. J. Discrete Algorithms 35, 1–8 (2015)
  * [19] Roberts, F.S., Sheng, L.: How hard is it to determine if a graph has a 2-role assignment? Networks 37, 67–73 (2001)
  * [20] Sheng, L.: 2-role assignments on triangulated graphs. Theor. Comput. Sci. 304(1-3), 201–214 (2003)
  * [21] Shi, Y., Wei, M., Yue, J., Zhao, Y.: Coupon coloring of some special graphs 33(1), 156–164 (2017)
  * [22] Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebraic Discrete Methods 3, 351–358 (1982)


# Number of points on a family of curves over a finite field

Thiéyacine Top∗

###### Abstract

In this paper we study a family of curves obtained by fibre products of
hyperelliptic curves. We then exploit this family to construct examples of
curves of given genus $g$ over a finite field $\mathbb{F}_{q}$ with many
rational points. The results obtained improve the known bounds for a few pairs
$(q,g)$.

Key words. Curves over finite fields, jacobian varieties.
AMS subject classification. 11G20, 14G15, 14H45.

††∗ Université Blaise Pascal, Clermont-Ferrand, France (E-mail:
<EMAIL_ADDRESS>
##  1 Introduction

Let $\mathcal{C}$ be a (projective, non-singular and geometrically
irreducible) curve of genus $g$ defined over the finite field $\mathbb{F}_{q}$
with $q$ elements. We denote by $N_{q}(g)$ the maximum number of rational
points on a curve of genus $g$ over $\mathbb{F}_{q}$, namely

$N_{q}(g)=\max\left\\{|\mathcal{C}(\mathbb{F}_{q})|:\mathcal{C}~{}~{}\text{is
a curve over }\mathbb{F}_{q}~{}~{}\text{of genus}~{}~{}g\right\\}.$

In the last years, due mainly to applications in Coding Theory and
Cryptography (see e.g.[8]) , there has been considerable interest in computing
$N_{q}(g)$. It is a classical result that $N_{q}(0)=q+1$. Deuring and
Waterhouse[10], and Serre [6] computed $N_{q}(1)$ and $N_{q}(2)$ respectively.
Serre also computed $N_{q}(3)$ for $q<25$ and Top [7] extended these
computations to $q<100$.

For $g\geq 3$ no such general formula is known. However, Serre [6] building on
earlier results by Hasse and Weil proved the following upper-bound:

$N_{q}(g)\leq q+1+g\lfloor 2\sqrt{q}\rfloor,$

where $\lfloor x\rfloor$ denotes the floor part of a real number $x$. This
bound is now called Hasse-Weil-Serre bound.
Some partial results for some specific pairs $(q,g)$ are recorded on the
website http:// www.manypoints.org in the form $N_{q}(g)\in[c_{1},c_{2}]$ or
$[\ldots,c_{2}]$, where

  * •

$c_{2}$ is the bound given by Hasse-Weil-Serre or by "explicit formulas", or
by more intricate arguments.

  * •

$c_{1}$ is the bound given by the existence of a curve $\mathcal{C}$ with
$|\mathcal{C}(\mathbb{F}_{q})|=c_{1}$,

  * •

… when $c_{1}\leq c_{2}/\sqrt{2}$.

Our work consists in studying geometric families of curves and studying among
them those which have many points over $\mathbb{F}_{q}$. The curves we are
considering are certain fibre products of hyperelliptic curves, we prove a
formula for the genus and a formula for the number of rational points of such
curves that depend are the polynomial $f_{i}$’s and the hyperelliptic they
define. In particular by building curves of given genus explicitly, we have
the following result:
Let $k$ be an integer $\geq 1$ and $q\geq 2$ be a prime power. Let $I$ be a
non-empty subset $\\{1,2,\ldots,k\\}$ and denote by $\mathcal{I}$ the set of
all non-empty subsets of $I$. Let $f_{1},f_{2},\ldots,f_{k}$ be polynomials of
respective degrees $d_{i}$’s, with coefficients in the finite fields
$\mathbb{F}_{q}$ such that the polynomial $f_{1}\times f_{2}\times\ldots\times
f_{k}$ is separable. We define the polynomial

$f_{I}(x)=\prod_{i\in I}f_{i}(x)$

and denote by $\mathcal{C}_{I}$ the hyperelliptic curve of equation
$y^{2}=f_{I}(x)$. Let $A_{I}=q+1-|\mathcal{C}_{I}(\mathbb{F}_{q})|$. Consider
now the fibre product $\mathcal{C}$ of which an open affine subset is given by

$\left\\{\begin{array}[]{ccc}y_{1}^{2}&=&f_{1}(x)\\\ &\vdots&\\\
y_{k}^{2}&=&f_{k}(x)\end{array}\right.,$

Let $N=|\mathcal{C}(\mathbb{F}_{q})|$ where $|\mathcal{C}(\mathbb{F}_{q})|$ is
the number of $\mathbb{F}_{q}$-rational points on $\mathcal{C}$.

######  Theorem 1.1.

In this notation:

  * •

The genus $g$ of $\mathcal{C}$ is givin by:

$g=2^{k-2}(d_{1}+\ldots+d_{k}-4)+1+\delta_{k},$

with $\delta_{k}=2^{k-2}$ (resp. $\delta_{k}=0$) if one of the $d_{i}$’s is
odd (resp. all of the $d_{i}$’s are even). There are $2^{k-1}$ (resp. $2^{k}$)
points at infinity if one of the $d_{i}$’s is odd (resp. all of the $d_{i}$’s
are even).

  * •

The number of $\mathbb{F}_{q}$-rational points of $\mathcal{C}$ is given by:

$N=q+1-\sum_{I\in\mathcal{I}}A_{I}.$

The proof of the above theorem follows from the lemma 2.1. and the lemma 3.3.
for the computation of $g$ and $|\mathcal{C}(\mathbb{F}_{q})|$ respectively.
In a second part of the paper, we use Theorem1.1 on specific examples in order
to improve a current lower bounds for $N_{q}(g)$ for some values of $(q,g)$.
The results we obtain are listed in Table 1.

$g$ | $q$ | $N_{q}(g)$ | $g$ | $q$ | $N_{q}(g)$
---|---|---|---|---|---
New enter | Old | New enter | Old
5 | $17$ | 48 | $[\ldots,53]$ | 5 | $73$ | 148 | $[\ldots,156]$
| $19$ | 52 | $[\ldots,60]$ |  | $79$ | 156 | $[\ldots,165]$
| $23$ | 62 | $[\ldots,67]$ |  | $83$ | 162 | $[\ldots,172]$
| $29$ | 72 | $[\ldots,80]$ |  | $89$ | 168 | $[136,180]$
| $31$ | 76 | $[\ldots,84]$ |  | $97$ | 180 | $[\ldots,193]$
| $37$ | 88 | $[\ldots,96]$ |  | $5^{2}$ | 64 | $[\ldots,72]$
| $41$ | 94 | $[\ldots,102]$ |  | $13^{2}$ | 295 | $[232,300]$
| $43$ | 100 | $[\ldots,106]$ |  | $17^{2}$ | 454 | $[376,460]$
| $47$ | 102 | $[\ldots,113]$ | 6 | $23$ | 66 | $[60,78]$
| $53$ | 120 | $[\ldots,124]$ |  | $31$ | 84 | $[80,92]$
| $59$ | 124 | $[\ldots,133]$ |  | $41$ | 104 | $[102,114]$
| $61$ | 126 | $[\ldots,137]$ |  | $59$ | 134 | $[132,150]$
| $67$ | 136 | $[\ldots,148]$ | $7$ | $29$ | $80$ | $[72,100]$
| $71$ | 144 | $[\ldots,152]$ | $8$ | 11 | $46$ | $[42,55]$
Table 1: The specified interval (Old) is that given by the website http://
www.manypoints.org as of Avril 2016

##  2 Geometry of curves

Let $k$ be a positive integer. Consider now the fibre product
$\mathcal{C}=\mathcal{C}_{f_{1}\ldots f_{k}}$ of which an open affine subset
is given by

$\left\\{\begin{array}[]{ccc}y_{1}^{2}&=&f_{1}(x)\\\ &\vdots&\\\
y_{k}^{2}&=&f_{k}(x)\end{array}\right.,$

where the $f_{i}$’s are coprime polynomials over $\mathbb{F}_{q}$ of
respective degrees $d_{i}$’s.

######  Lemma 2.1.

Suppose the polynomial $f(x):=\prod_{i}f_{i}(x)$ is separable, then the affine
curve is smooth. The genus of the complete curve is

$g=2^{k-2}(d_{1}+\ldots+d_{k}-4)+1+\delta_{k},$

with $\delta_{k}=2^{k-2}$ (resp. $\delta_{k}=0$) if one of the $d_{i}$’s is
odd (resp. all of the $d_{i}$’s are even). There are $2^{k-1}$ (resp. $2^{k}$)
points at infinity if one of the $d_{i}$’s is odd (resp. all of the $d_{i}$’s
are even).

Proof. Smoothness follows from the jacobian criterion applied to the matrix

$\left(\begin{array}[]{ccccc}f^{\prime}_{1}(x)&2y_{1}&0&&\\\
f^{\prime}_{2}(x)&0&2y_{2}&0&\\\ &&&\ldots&\\\
f^{\prime}_{k}(x)&&&0&2y_{k}\end{array}\right).$

If none of the $y_{i}$’s is zero, there exists a minor equal to

$2^{k-1}y_{1}\ldots y_{i-1}f^{\prime}_{i}(x)y_{i+1}\ldots y_{k}\neq 0;$

If for some $i$, $y_{i}=0$, then $f_{i}(x)=0$ and therefore
$f^{\prime}_{i}(x)\neq 0$ and, for $j\neq i$, we have $f_{j}(x)\neq 0$ and
there exists a minor equal to

$2^{k-1}y_{1}\ldots y_{i-1}f^{\prime}_{i}(x)y_{i+1}\ldots y_{k}\neq 0.$

The group $G=\left\\{\pm 1\right\\}^{k}\cong(\mathbb{Z}/2\mathbb{Z})^{k}$ acts
in an obvious way on $\mathcal{C}$ by

$[\varepsilon](x,y_{1},\ldots,y_{k})=(x,\varepsilon_{1}y_{1},\ldots,\varepsilon_{k}y_{k})$

and is the Galois group of the covering

$\phi:\mathcal{C}\rightarrow\mathbb{P}^{1}$

given by

$(x,y_{1},\ldots,y_{k})\mapsto x.$

The group $G$ acts transitively on the set $\mathcal{C}_{\infty}$, of points
at infinity; the inertia group is cyclic therefore is trivial or reduced to
$\mathbb{Z}/2\mathbb{Z}$.
If one of the $d_{i}$’s is odd (resp. all $d_{i}$’s are even), there is
ramification above $\infty\in\mathbb{P}^{1}$ hence we obtain
$|C_{\infty}|=2^{k-1}$ (resp. $=2^{k}$ ). The Riemann-Hurwitz formula applied
to the morphism $\phi$ gives the genus, observing that $\phi$ is branched at
every point $x=\alpha_{i}$ with $f_{i}(\alpha_{i})=0$ , i.e

$(x,y_{1},\ldots,y_{k})=(\alpha_{i},\pm\sqrt{f_{1}(\alpha_{i})},\ldots,0,\ldots,\pm\sqrt{f_{k}(\alpha_{i})}),$

and possibly above $\infty$.

##  3 Computation the number of points

We keep the same notation as before.

######  Definition 3.1.

Let $I$ be a non-empty subset of $\\{1,\ldots,k\\}$, we define:

  1. 1.

the polynomial $f_{I}(x)=\prod_{i\in I}f_{i}(x)$ and we denote by $d_{I}$ its
degree;

  2. 2.

the smooth projective curve $\mathcal{C}_{I}$ whose affine model is given by
$v^{2}=f_{I}(u)$;

  3. 3.

we denote by $g_{I}$ the genus of $\mathcal{C}_{I}$;

  4. 4.

the morphism $\phi_{I}:\mathcal{C}\rightarrow C_{I}$ given by
$\phi_{I}(x,y_{1},\ldots,y_{k})=(x,y_{I})$ (where $y_{I}=\prod_{i\in
I}y_{i})$.

We denote by $\mathcal{I}$ the set of non-empty subsets of $\\{1,\ldots,k\\}$.

######  Lemma 3.2.

The morphism

$\begin{array}[]{rcl}\Psi:\prod_{I\in\mathcal{I}}\mathrm{Jac}(\mathcal{C}_{I})&\longrightarrow&\mathrm{Jac}(\mathcal{C})\\\
(\mathcal{C}_{I})_{I\in\mathcal{I}}&\longmapsto&\sum_{I\in\mathcal{I}}\phi_{I}^{\ast}(\mathcal{C}_{I}).\end{array}$

is a separable isogeny.

Proof. We first verify that $\sum_{I\in\mathcal{I}}g_{I}=g$; indeed, if we put
$d_{I}=\sum_{i\in I}d_{i}=\mathrm{deg}f_{I}$ then
$g_{I}=\left\lfloor\frac{d_{I}-1}{2}\right\rfloor$, which we may write
$\frac{d_{I}-1-\varepsilon_{I}}{2}$ with $\varepsilon_{I}=0$ or 1.
So

$\sum_{I\in\mathcal{I}}g_{I}=\sum_{I\in\mathcal{I}}\frac{d_{I}-1-\varepsilon_{I}}{2}=\frac{1}{2}\left(\sum_{i=1}^{k}d_{i}N_{i}-2^{k}+1-\sum_{I}\varepsilon_{I}\right)$

where $N_{i}$ is the number of $I$’s containing $i$, i.e $N_{i}=2^{k-1}$.
If all $d_{i}$ are even, all the $\varepsilon_{I}$ = 1 and
$\frac{1}{2}\sum_{I}(1+\varepsilon_{I})=2^{k}-1$ and the formula follows. If
at least one of $d_{i}$ is odd, denote by $M$ the number of $I$ with $d_{I}$
odd , then $\frac{1}{2}\sum_{I}(1+\varepsilon_{I})=2^{k}-1-\frac{M}{2}$; we
conclude by using $M=2^{k-1}$.

The abelian varieties $\prod_{I\in\mathcal{I}}\mathrm{Jac}(C_{I})$ and
$\mathrm{Jac}(C)$ have the same dimension. Furthermore, if
$\eta_{j}=u^{j-1}du/v$ is a regular differential form on $C_{I}$ (for $1\leq
j\leq g_{I})$ then $\omega_{I,j}:=\phi^{\ast}_{I}(\eta_{j})=x^{j-1}dx/y_{I}$
is regular on $C$ and these forms are linearly independent. Indeed an equality
of type:

$\sum_{I}\sum_{j=1}^{g_{I}}\lambda_{I,j}\omega_{I,j}=0,$

implies

$\sum_{I}P_{I}(x)y_{I^{c}}=0,$

where $I^{c}:=[1,k]\backslash I$ ; which implies the $P_{I}$’s are zero. The
differential of $\Psi$ is an isomorphism, which proves that $\Psi$ is a
separable isogeny.
Remark. We can deduce from the previous calculation, when $k\geq 2$, that the
curve $C$ is not hyperelliptic. In fact the canonical morphism
$P\mapsto(\omega_{I,j}(P))$ may be written
$P\mapsto(1,x,x^{2},\ldots,y_{1},\ldots,y_{k},\ldots)$ thus is generically of
degree 1, therefore an isomorphism (if $C$ were hyperelliptic, it would be a
morphism of degree 2).

######  Lemma 3.3.

Let $f_{1},\ldots,f_{k}$ be polynomials with coefficients in the finite field
$\mathbb{F}_{q}$ such that the product $f_{1}...f_{k}$ is separable, and let
$C$ be the associated curve. Let $A_{I}=q+1-|C_{I}(\mathbb{F}_{q})|$ then,

$|C(\mathbb{F}_{q})|=q+1-\sum_{I\in\mathcal{I}}A_{I}.$

Proof. The abelian varieties $\mathrm{Jac}(C)$ and
$\prod_{I}\mathrm{Jac}(C_{I})$ are $\mathbb{F}_{q}$-isogenous therefore have
the same number of points on $\mathbb{F}_{q^{m}}$. If

$|C(\mathbb{F}_{q^{m}})|=q^{m}+1-(\beta^{m}_{1}+\ldots+\beta^{m}_{2g})$

then

$|\mathrm{Jac}(C)(\mathbb{F}_{q^{m}})|=\prod_{1\leq i\leq
2g}(1-\beta^{m}_{i})$

and if

$|C_{I}(\mathbb{F}_{q^{m}})|=q^{m}+1-((\alpha^{(I)}_{1})^{m}+\ldots+(\alpha^{(I)}_{2g})^{m})$

then

$|\mathrm{Jac}(C_{I})(\mathbb{F}_{q^{m}})|=\prod_{1\leq i\leq
2g}(1-(\alpha^{(I)}_{i})^{m})$

and thus therefore

$|\mathrm{Jac}(\mathcal{C})(\mathbb{F}_{q^{m}})|=\prod_{I}|\mathrm{Jac}(C_{I})(\mathbb{F}_{q^{m}})|=\prod_{I}\prod_{j}(1-(\alpha^{(I)}_{j})^{m}),$
$|C_{I}(\mathbb{F}_{q^{m}})|=q^{m}+1-((\alpha^{(I)}_{1})^{m}+\ldots+(\alpha^{(I)}_{2g})^{m})=q^{m}+1-\sum_{I}\sum_{1\leq
j\leq g_{I}}(\alpha_{j}^{(I)})^{m},$

and, in particular , for $m=1$, we get

$|C(\mathbb{F}_{q})|=q+1-\sum_{I}\sum_{1\leq j\leq
g_{I}}\alpha_{j}^{(I)}=q+1-\sum_{I\in\mathcal{I}}A_{I}.$

##  4 Numerical examples

Examples of genus-$g$ curves $y_{1}^{2}=f_{1}$, $y_{2}^{2}=f_{2}$ over ${\bf
F}_{q}$ having many points. The meaning of the quantities $A_{1}$, $A_{2}$,
$A_{3}$, and $N$ is explained in the text. The following examples improve some
results listed on the website http:// www.manypoints.org and were computed
using the computer algebra package Magma.

$q=17$ | $f_{1}=x^{4}+x^{3}+16x^{2}+15x+1$ | $A_{1}=-8$ | $N=48\in[\ldots,53]$
---|---|---|---
| $f_{2}=x^{4}+13x^{3}+16x^{2}+15$ | $A_{2}=-6$ |
|  | $A_{3}=-16$ |
$q=19$ | $f_{1}=x^{4}+x^{3}+18x^{2}+13x+14$ | $A_{1}=-8$ | $N=52\in[\ldots,60]$
| $f_{2}=x^{4}+4x^{3}+18x^{2}+7x+12$ | $A_{2}=-8$ |
|  | $A_{3}=-16$ |
$q=23$ | $f_{1}=x^{4}+19x^{3}+7$ | $A_{1}=-9$ | $N=60\in[\ldots,67]$
| $f_{2}=x^{3}+x+11$ | $A_{2}=-9$ |
|  | $A_{3}=-18$ |
$q=29$ | $f_{1}=x^{4}+x^{3}+28x^{2}+28x+18$ | $A_{1}=-10$ | $N=72\in[\ldots,80]$
| $f_{2}=x^{4}+27x^{3}+27x^{2}+28x+15$ | $A_{2}=-10$ |
|  | $A_{3}=-22$ |
$q=31$ | $f_{1}=x^{4}+x^{3}+30x^{2}+30x+10$ | $A_{1}=-11$ | $N=76\in[\ldots,84]$
| $f_{2}=x^{4}+30x^{3}+5x^{2}+19x+14$ | $A_{2}=-10$ |
|  | $A_{3}=-23$ |
$q=37$ | $f_{1}=x^{4}+x^{3}+35x^{2}+32x+1$ | $A_{1}=-12$ | $N=88\in[\ldots,96]$
| $f_{2}=x^{4}+11x^{3}+29x^{2}+13x+29$ | $A_{2}=-12$ |
|  | $A_{3}=-26$ |
$q=41$ | $f_{1}=x^{4}+x^{3}+40x^{2}+40x+36$ | $A_{1}=-12$ | $N=94\in[\ldots,102]$
| $f_{2}=x^{4}+23x^{3}+10x^{2}+20x+36$ | $A_{2}=-11$ |
|  | $A_{3}=-29$ |
$q=43$ | $f_{1}=x^{4}+x^{3}+41x^{2}+34x+1$ | $A_{1}=-13$ | $N=100\in[\ldots,106]$
| $f_{2}=x^{4}+12x^{3}+17x^{2}+41x+38$ | $A_{2}=-13$ |
|  | $A_{3}=-30$ |
$q=47$ | $f_{1}=x^{4}+25x^{3}+x^{2}+2x+31$ | $A_{1}=-12$ | $N=102\in[\ldots,113]$
| $f_{2}=x^{3}+x+38$ | $A_{2}=-13$ |
|  | $A_{3}=-29$ |
$q=53$ | $f_{1}(x)=x^{4}+x^{3}+52x^{2}+47x+1$ | $A_{1}=-14$ | $N=120\in[...,124]$
| $f_{2}(x)=x^{4}+16x^{3}+36x^{2}+18x+46$ | $A_{2}=-14$ |
|  | $A_{3}=-38$ |

$q=59$ | $f_{1}(x)=x^{4}+x^{3}+54x^{2}+6x+1$ | $A_{1}=-15$ | $N=124\in[...,133]$
---|---|---|---
| $f_{2}(x)=x^{4}+13x^{3}+22x^{2}+3x+9$ | $A_{2}=-15$ |
|  | $A_{3}=-34$ |
$q=61$ | $f_{1}(x)=x^{4}+x^{3}+58x^{2}+18x+1$ | $A_{1}=-15$ | $N=126\in[...,137]$
| $f_{2}(x)=x^{4}+27x^{3}+5x^{2}+47x+28$ | $A_{2}=-14$ |
|  | $A_{3}=-35$ |
$q=67$ | $f_{1}(x)=x^{4}+x^{3}+66x^{2}+57x+1$ | $A_{1}=-16$ | $N=136\in[...,148]$
| $f_{2}(x)=x^{4}+2x^{3}+49x^{2}+24x+1$ | $A_{2}=-16$ |
|  | $A_{3}=-36$ |
For $q=71$ | $f_{1}(x)=x^{4}+x^{3}+x^{2}+44x+1$ | $A_{1}=-16$ | $N=144\in[...,152]$
| $f_{2}(x)=x^{4}+9x^{3}+8x^{2}+21x+64$ | $A_{2}=-16$ |
|  | $A_{3}=-40$ |
For $q=73$ | $f_{1}(x)=x^{4}+x^{3}+66x^{2}+57x+1$ | $A_{1}=-17$ | $N=148\in[...,156]$
| $f_{2}(x)=x^{4}+2x^{3}+49x^{2}+24x+1$ | $A_{2}=-17$ |
|  | $A_{3}=-40$ |
For $q=79$ | $f_{1}(x)=x^{4}+x^{3}+3x^{2}+7x+1$ | $A_{1}=-16$ | $N=156\in[...,165]$
| $f_{2}(x)=x^{4}+4x^{3}+5x^{2}+24x+68$ | $A_{2}=-16$ |
|  | $A_{3}=-36$ |
For $q=83$ | $f_{1}(x)=x^{4}+x^{3}+x^{2}+5x+1$ | $A_{1}=-18$ | $N=162\in[...,172]$
| $f_{2}(x)=x^{4}+72x^{3}+54x^{2}+29x+36$ | $A_{2}=-16$ |
|  | $A_{3}=-44$ |
For $q=89$ | $f_{1}(x)=x^{4}+x^{3}+3x^{2}+7x+1$ | $A_{1}=-16$ | $N=168\in[136,180]$
| $f_{2}(x)=x^{4}+4x^{3}+5x^{2}+24x+68$ | $A_{2}=-16$ |
|  | $A_{3}=-36$ |
$q=97$ | $f_{1}(x)=x^{4}+8x^{3}+3x^{2}+23x+1$ | $A_{1}=-19$ | $N=180\in[...,193]$
| $f_{2}(x)=x^{4}+9x^{3}+63x^{2}+28x+91$ | $A_{2}=-19$ |
|  | $A_{3}=-44$ |
$q=5^{2}$ | $f_{1}(x)=x^{4}+x^{2}+rx$ | $A_{1}=-9$ | $N=68\in[...,72]$
| $f_{2}(x)=x^{4}-2rx^{3}+rx+2$ | $A_{2}=-9$ |
| with $r^{2}+r+1=0$ | $A_{3}=-24$ |
$q=13^{2}$ | $f_{1}(x)=(x-2)(x^{2}-2)$ | $A_{1}=-26$ | $N=295\in[232,300]$
| $f_{2}(x)=x^{4}-4x^{2}+1$ | $A_{2}=-21$ |
|  | $A_{3}=-78$ |
$q=17^{2}$ | $f_{1}(x)=(x+2)(x+10)(x^{2}+6)$ | $A_{1}=-33$ | $N=454\in[376,460]$
| $f_{2}(x)=(x^{2}+10)(x^{2}+6x+3)$ | $A_{2}=-29$ |
|  | $A_{3}=-102$ |
Table 2: Examples of genus-$5$. $q=23$ | $f_{1}(x)=x^{5}+12x^{4}+19x^{3}+x+2$ |  $A_{1}=-13$ $N=66\in[60,78]$
---|---|---
| $f_{2}(x)=x^{3}+12x^{2}+18x+4$ | $A_{2}=-9$
|  | $A_{3}=-20$
$q=31$ | $f_{1}(x)=x^{5}+6x^{4}+4x^{3}+4x^{2}+17x+16$ |  $A_{1}=-19$ $N=84\in[80,92]$
| $f_{2}(x)=(x)^{3}+13x^{2}+15x+13$ | $A_{2}=-11$
|  | $A_{3}=-22$
$q=41$ | $f_{1}(x)=x^{5}+31x^{4}+11x^{3}+14x^{2}+35x+40$ |  $A_{1}=-23$ $N=104\in[102,114]$
| $f_{2}(x)=x^{3}+23x^{2}+5x+17$ | $A_{2}=-12$
|  | $A_{3}=-27$
$q=59$ | $f_{1}(x)=x^{5}+57x^{4}+17x^{3}+48$ |  $A_{1}=-25$ $N=134\in[132,150]$
| $f_{2}(x)=x^{3}+2x+22$ | $A_{2}=-15$
|  | $A_{3}=-34$
Table 3: Examples of genus-$6$ . $q=29$ | $f_{1}(x)=x^{6}+9x^{5}+3x^{4}+1$ | $A_{1}=-46$ | $N=80\in[72,100]$
---|---|---|---
| $f_{2}(x)=x^{4}+13x^{3}+28x^{2}+12x+1$ | $A_{2}=-40$ |
|  | $A_{3}=-54$ |
Table 4: Examples of genus-$7$ .

### Acknowledgements

We thank Professor Marc Hindry (Paris 7), the mathematics lab of the
University Blaise Pascal in particular Nicolas Billerey and Marusia Rebelledo.

## References

  * [1]
  * [1] Everett W. Howe. New bounds on the maximum number of points on genus-4 curves over small finite fields, Arithmetic, Geometry, Cryptography and Coding Theory (Y. Aubry, C. Ritzenthaler, and A. Zykin, eds.), Contempory Mathematics 574,in American Mathematical Sociaty,Providence, RI, 2012, pp 69-86.
  * [2] Yasutaka Ihara. Some remarks on the number of rational points of algebraic curves over finite fields. J. Fac. Sci. Univ. Tokyo Sect. IA Math., 28(3):721–724 (1982), 1981.
  * [3] Tetsuo Kodama, Jaap Top, and Tadashi Washio. Maximal hyperelliptic curves of genus three. Finite Fields Appl., 15(3):392–403, 2009.
  * [4] Stephen Meagher and Jaap Top. Twists of genus three curves over finite fields. Finite Fields and their Appl., 16:347–368, 2010.
  * [5] Jean-Pierre Serre. Nombres de points des courbes algébriques sur $\mathbb{F}_{q}$. In Seminar on number theory, 1982–1983 (Talence, 1982/1983), pages Exp. No. 22, 8. Univ. Bordeaux I, Talence, 1983.
  * [6] Jean-Pierre Serre. Rational points on curves over finite fields. Unpublished notes by F.Q. Gouvêa of lectures at Harvard. 1985.
  * [7] Jaap Top. Curves of genus 3 over small finite fields. Indag. Math. (N.S.), 14(2):275–283, 2003.
  * [8] Michael Tsfasman, Serge Vladut¸, and Dmitry Nogin. Algebraic geometric codes: basic notions, volume 139 of Mathematical Survey and Monographs. American Mathematical Society, Providence, RI, 2007.
  * [9] Gerard van der Geer and Marcel van der Vlugt. Tables of curves with many points. Math. Comp., 69(230):797–810, 2000.
  * [10] William C. Waterhouse. Abelian varieties over finite fields. Ann. Sci. Ecole Norm. Sup. (4), 2:521–560, 1969.