\section{Introduction}
\label{Intro}

Let $\Gamma$ be a finite simplicial graph with vertex set $V=V(\Gamma)$ and edge set $E=E(\Gamma)$.
We say that $\Gamma$ is \emph{$k$--colorable} if there is a map $\kappa\colon V\to \{1,\ldots,k\}$ such that if  $\{v,w\}\in E$ then
$\kappa(v)\neq\kappa(w)$. The map $\kappa$ is called a \emph{$k$--coloring} of $\Gamma$.
 The minimal $k$ for which there exists such a map $\kappa$ is called the \emph{chromatic number} of
$\Gamma$ and is denoted $\chi(\Gamma)$.

The problem of finding a $k$--coloring of a given graph is fundamental in graph theory, and has many applications in discrete mathematics,
computational complexity, and computer science. Determining whether a given graph is $3$--colorable is known to be NP--complete, as is
determining a graph's chromatic number~\cite{GJ1979,Minsky67,AB09}.

As such, determining the existence of a $k$--coloring of a graph is a fundamental problem in theoretical complexity theory,
with a plethora of applications to
both theoretical and applied computer science; for instance, several cryptographic schemes based on the $3$--colorability problem
have been proposed, such as a post-quantum public key encryption known as Polly Cracker~\cite{LMPT}, and a zero-knowledge
proof system for graph
$3$--colorability~\cite{GMW91}.

This paper studies $k$--colorings of graphs via algebraic methods, specifically right-angled Artin groups~\cite{CharneyGD}.
To  a finite simplicial graph $\Gamma$,
we associate the right-angled Artin group $A(\Gamma)$ via \[A(\Gamma)=\langle V(\Gamma)\mid [v,w]=1 \textrm{ if and only if } \{v,w\}\in E(\Gamma)\rangle.\]

It is well-known that the isomorphism type of $A(\Gamma)$ determines the isomorphism type of $\Gamma$~\cite{Droms87,Sabalka09,KoberdaGAFA},
so that the graph theoretic properties of $\Gamma$ should be reflected in the algebra of $A(\Gamma)$. We are generally interested in the following
problem:
\begin{prob}\label{prob:property}
Let $P$ be a property of finite simplicial graphs. Find a property $Q$ of groups such that $\Gamma$ has $P$ if and only if $A(\Gamma)$ has
$Q$.
\end{prob}
In order for Problem~\ref{prob:property} to be interesting, one should insist that $Q$ be a property of the isomorphism type of a group only.
In particular, one should disallow reference to a generating set.

One reason for interest in Problem~\ref{prob:property} is that it can provide
insight into various graph theoretic problems and their computational complexity
from the more flexible point of view of the algebraic structure of $A(\Gamma)$. Moreover, algebraically formulated problems
can be approached using an arbitrary presentation  for $A(\Gamma)$, without reconstructing the full underlying graph of $A(\Gamma)$.

Here are some instances where a satisfactory answer to Problem~\ref{prob:property} is known:

\begin{enumerate}
\item
The graph $\Gamma$ is a nontrivial join if and only if $A(\Gamma)$ decomposes as a nontrivial direct product~\cite{Servatius1989}.
\item
The graph $\Gamma$ is disconnected if and only if $A(\Gamma)$ decomposes as a nontrivial free product~\cite{BradyMeier01}.
\item
The graph $\Gamma$ is square--free if and only if $A(\Gamma)$ does not contain a subgroup isomorphic to a product $F_2\times F_2$ of
nonabelian free groups~\cite{Kambites09,KK2013gt}.
\item 
The graph $\Gamma$ admits an independent set $D$ of vertices
such that every cycle in $\Gamma$ meets $D$ at least twice  if and only if the poly-free length of $A(\Gamma)$ is two~\cite{HS2007}.
\item
The graph $\Gamma$ is a cograph (i.e. a $P_4$--free graph) if and only if $A(\Gamma)$ is contained in the class of finitely generated groups which
contains $\mathbb{Z}$ and is closed under taking direct products and free products~\cite{KK2013gt,KK2018jt}.
\item 
The graph $\Gamma$ is a finite tree or a finite complete bipartite graph if and only if $A(\Gamma)$ is a semidirect product of
two free groups of finite rank~\cite{HS2007}.
\item
The graph $\Gamma$ admits a nontrivial automorphism if and only if the group $\mathrm{Out}(A(\Gamma))$ of outer automorphisms of $A(\Gamma)$ contains
a finite nonabelian group~\cite{FKK2019}.
\item
A sequence of graphs $\{\Gamma_i\}_{i\in\mathbb{N}}$ forms a graph expander family if and only if the cohomology rings $\{H^*(A(\Gamma_i),F)\}$ over an
arbitrary field $F$
 form a \emph{vector space expander family}~\cite{FKK2020exp}.
\end{enumerate}

In this paper, we prove the following result which characterizes the existence of a $k$--coloring of a graph $\Gamma$ (and in particular the
chromatic number of $\Gamma$) via right-angled Artin groups, thus providing an answer to Problem~\ref{prob:property} when $P$ is
$k$--colorability.

\begin{thm}\label{thm:main}
Let $\Gamma$ be a finite simplicial graph with $n$ vertices. The graph $\Gamma$ is $k$--colorable if and only if there is a surjective map
\[A(\Gamma)\to \prod_{i=1}^k F_i,\] where for $1\leq i\leq k$ the group $F_i$ is a free group of rank $m_i$, and where \[\sum_{i=1}^k m_i=n.\]
\end{thm}

We note that the number of vertices of $\Gamma$ is a canonical invariant of the isomorphism type of $A(\Gamma)$, since this is simply the rank
of the abelianization of $A(\Gamma)$. We state Theorem~\ref{thm:main} as we do
because  of the conciseness of  the hypotheses and the
conclusion,  though  in the course  of the  proof  it  will  become clear that we can weaken
the  hypotheses  somewhat. For  instance,  the target groups need  not be free,  but may be replaced by groups with the correct Betti numbers
in which infinite order elements have (virtually) cyclic centralizers. This last hypothesis is satisfied in all Gromov hyperbolic
groups~\cite{Gromov1987}, for instance. Moreover, we need not assume that $\phi$ is surjective ---  it  suffices  that $\phi$ induces an
isomorphism on  first rational homology.

Theorem~\ref{thm:main} has the following easy consequence, which  is of interest from the point of view of complexity theory.
\begin{cor}
Fix $k\geq 3$. The problem of determining whether a right-angled Artin group $A(\Gamma)$ surjects to a product of $k$ free groups, the sum
of whose ranks equals $|V(\Gamma)|$, is NP--complete.
\end{cor}
\begin{proof}
It is a direct consequence of Theorem~\ref{thm:main} and the fact that the $k$-colorability problem is NP--complete for $k\geq 3$ (see for example \cite{GJ1979}).
\end{proof}

\section{Proof of Theorem~\ref{thm:main}}

There is only one difficult direction in our proof of Theorem~\ref{thm:main}. The following easy lemma handles  the ``only if" direction.

\begin{lem}\label{lem:only if}
Suppose $\Gamma$ is a simplicial graph on $n$ vertices which is $k$--colorable.
Then $A(\Gamma)$ admits a surjection as in Theorem~\ref{thm:main}.
\end{lem}
\begin{proof}
Let $\kappa$ be a $k$--coloring, and write $V_i=\kappa^{-1}(i)\subset V$. If $\{v,w\}\in E$ then $v\in V_i$ and $w\in V_j$ for suitable
indices $i\neq j$. We may thus form a quotient $G$ of $A(\Gamma)$ by imposing the relation $[a,b]=1$ for all pairs $a\in V_i$ and $b\in V_j$
for $i\neq j$. Clearly the result will be a right-angled Artin group $A(\Lambda)$, where \[\Lambda=V_1*V_2*\cdots *V_k\] is the join
of the sets $\{V_1,\ldots,V_k\}$. Since for all $i$ the set $V_i$ is totally disconnected in $\Gamma$ (and hence in $\Lambda$), it is easy
to see that $A(\Lambda)$ is a direct product of free groups with ranks $\{|V_1|,\ldots,|V_k|\}$, and that
\[\sum_{i=1}^k |V_i|=n,\] as desired.
\end{proof}

We now turn our attention to the ``if" direction. Suppose
\[\phi\colon A(\Gamma)\to\prod_{i=1}^k F_i=G\] is a surjection as in Theorem~\ref{thm:main}.
We will fix notation and write $\{v_1,\ldots,v_n\}$ for the vertices of $\Gamma$ and $w_i=\phi(v_i)$. Recall that $m_i$ stands for the rank of $F_i$. We write $X=\{x_1,\ldots,x_n\}$ for a
generating set of $G$, where \[X_i=\{x_{1+\sum_{j<i}m_j},x_{2+\sum_{j<i}m_j},\ldots,x_{\sum_{j\leq i} m_j}\}\] generates the subgroup
\[\{1\}\times\cdots\times\{1\}\times F_i\times\{1\}\times\cdots\times\{1\}.\] For each $x_i\in X$ and $g\in G$, we write $\exp_{x_i}(g)$ for the
\emph{exponent sum} of $x_i$ in $g$, i.e. the image of the element $g$ under the homomorphism $G\to\mathbb{Z}$ which sends $x_i$ to $1$ and
$x_j$ to $0$ for $j\neq i$.

If $g\in G$ is arbitrary, we write $g=g_1\cdots g_k$, where $g_i\in\langle X_i\rangle$. It is easy to see that this expression for $g$ is unique.

\begin{lem}\label{lem:dimension}
Suppose $g,h\in G$ are elements such that $[g,h]=1$. Write $g=g_1\cdots g_k$ and $h=h_1\cdots h_k$.
Then for all $1\leq i\leq k$, the tuples \[(\exp_{\alpha}(g_i))_{\alpha\in X_i},(\exp_{\alpha}(h_i))_{\alpha\in X_i}\]
are rational multiples of each other.
\end{lem}

Note that the map \[g_i\mapsto (\exp_{\alpha}(g_i))_{\alpha\in X_i}\] just computes the image of $g_i$ in the abelianization
$H_1(F_i,\mathbb{Z})$, using the images of elements of $X_i$ as an additive basis for $\mathbb{Z}^{m_i}$.
\begin{proof}[Proof of Lemma~\ref{lem:dimension}]
Fix $i$ arbitrarily. If one of these tuples consists of all zeros then there is nothing to show. Otherwise, we may suppose that these tuples
are nontrivial for both $g_i$ and $h_i$. In particular, we must have that both $g_i$ and $h_i$ are nontrivial group elements of
$\langle X_i\rangle$. The
centralizer of a nontrivial element of a free group is cyclic, so that then $g_i$ and $h_i$ must share a common nonzero power. Since the
exponent sum map is a homomorphism, the lemma is now immediate.
\end{proof}

We will  require the  following fact from linear algebra, which  we include for completeness.

\begin{lem}\label{lem:lin-alg}
Let $M$ be a complex $n\times n$ matrix of rank $n$, let $1\leq k\leq n-1$ be an integer,
and consider the block decomposition $M=(M_1\mid M_2)$, where
$M_1$ is an $n\times k$ matrix. There exist $k$ rows $\{r_1,\ldots,r_k\}$ which have the following properties:
\begin{enumerate}
\item
The submatrix $M_1'$ of $M_1$ spanned by the rows $\{r_1,\ldots,r_k\}$ has rank $k$.
\item
The submatrix $M_2'$ of $M_2$ obtained by deleting the rows $\{r_1,\ldots,r_k\}$ has rank $n-k$.
\end{enumerate}
\end{lem}
\begin{proof}
We have that the determinant of $M$ is nonzero, since $M$ is invertible.
We may  now expand the determinant about $k\times k$--subminors of $M_1$. That is, we consider a submatrix $M_1'$ of $M_1$
spanned by $k$ rows, and the submatrix $M_2'$ of $M_2$ obtained by deleting the $k$ rows used to define $M_1'$. We then consider the
complex number $\zeta=(\det M_1')\cdot (\det M_2')$. An easy application of the Leibniz formula shows that $\det M$ is an alternating sum
of the complex numbers $\zeta$, as $M_1'$ ranges over all possible choices of $k$ rows. Since  $\det M\neq 0$, there is a choice of $M_1'$
and $M_2'$ so that the corresponding value of $\zeta$ is nonzero. In particular, such a choice of $M_1'$ and $M_2'$ gives the desired
matrices of the correct  ranks, whence the lemma follows.
\end{proof}

The following lemma completes the proof of Theorem~\ref{thm:main}.

\begin{lem}\label{lem:if}
Let $\phi\colon A(\Gamma)\to G$ be a surjective homomorphism as above. Then $\Gamma$ admits a $k$--coloring.
\end{lem}
\begin{proof}
Since the abelianizations of $A(\Gamma)$ and $G$ are both isomorphic to $\mathbb{Z}^n$, we have that the induced map
\[\phi_*\colon H_1(A(\Gamma),\mathbb{Q})\rightarrow  H_1(G,\mathbb{Q})\] is an isomorphism. We express this map as a matrix with respect to the additive bases
$\{v_1,\ldots,v_n\}$ for $H_1(A(\Gamma),\mathbb{Q})$ and $\{x_1,\ldots, x_n\}$ for $H_1(G,\mathbb{Q})$, so that \[\phi_*(v_i)=[w_i]=\sum_{j=1}^n \beta_j^i x_j\]
for suitable coefficients $\beta_j^i$. With respect to these bases, $\phi_*$ is represented by an $n\times n$ matrix
$A=(\beta_j^i)$ with rank exactly $n$, where here $\beta^i_j$ denotes the $(i,j)$--entry of $A$.
We write $A$ as a block column matrix \[A=(A_1\mid\cdots \mid A_k),\] where the column space of $A_i$ has dimension exactly $m_i$.

Consider the matrix $A_1$. Since $\phi_*$ is an isomorphism, we have that the row space of $A_1$ has dimension $m_1$. We may therefore
choose an $m_1\times m_1$ minor $B_1$ of $A_1$ with rank $m_1$. By
Lemma~\ref{lem:lin-alg}, we may assume that deleting the first $m_1$ columns of $A$ and the rows which appear in
$B_1$ results in a matrix of rank exactly $n-m_1$. We perform a row permutation of $A$
to get a matrix $A'$, so that the rows of $B_1$ are the
restriction of the first $m_1$ rows of $A'$ to the first $m_1$ columns of $A'$.

Deleting the first $m_1$ rows and columns of $A'$ results in a matrix of rank exactly $n-m_1$. Repeating this process for each block
column matrix results in an $n\times n$ block matrix \[B=(B_1\mid\cdots\mid B_k)\] with the following properties:
\begin{enumerate}
\item
The matrix $B$ is obtained from $A$  by permuting rows.
\item
The rows with index set $J_i=\{(\sum_{j<i}m_j)+1,\ldots,\sum_{j\leq i}m_j\}$ of $B_i$ have rank $m_i$.
\end{enumerate}

Observe that the rows of $B$ correspond to the group elements \[\{w_i=\phi(v_i)\}_{i=1}^n,\] where we have relabeled the
elements $\{v_1,\ldots,v_n\}$ so that $\phi(v_i)$ corresponds to the $i^{th}$ row of $B$. We define
$\kappa\colon V\to \{1,\ldots,k\}$ by
$\kappa(v_{\ell})=i$ if $\ell\in J_i$. It remains  to check that $\kappa$ is a valid coloring  of $\Gamma$. Suppose that $\kappa(v)=\kappa(w)=i$ for
distinct vertices of $V$. Then the elements $[\phi(v)]$ and $[\phi(w)]$ in $H_1(G,\mathbb{Q})$ correspond to linearly independent rows of the block
$B_i$. We have that if $\{v,w\}\in E$ then $v$ and $w$ commute. Lemma~\ref{lem:dimension} implies that the rows corresponding to
$[\phi(v)]$ and $[\phi(w)]$ in the block $B_i$ are rational multiples of each other, which is a contradiction. We conclude that
$\{v,w\}\notin E$, so that $\kappa$ is a valid coloring of $\Gamma$.
\end{proof}


Observe that the proof of Theorem~\ref{thm:main} builds an explicit coloring of $\Gamma$ using the image of $V(\Gamma)$ under $\phi$.
In  principle,  an  algorithm which takes as  input the surjection from Theorem~\ref{thm:main} and outputs a coloring of $\Gamma$ can  be
implemented,  and even in polynomial time.

More precisely, let $\Gamma$ be a graph with $n$ vertices and let  $\phi$ be a surjection
from $A(\Gamma)$ to a product of  $k$ free  groups of total  rank $n$, given in terms of generators. We can compute the map induced by
$\phi$ on abelianizations in time which is linear  in the complexity of $\phi$.
Let $M$  be the resulting matrix  and $N$  a bound on the maximum of the entries of $M$, in absolute value.
Following the proof of Theorem~\ref{thm:main}, we break $M$ into  submatrices $M_1$  and $M_2$, and compute a sequence of
 determinants of submatrices of $M_1$ and $M_2$, of which there are at  most polynomially many
 as a function of $n$. All this would require
a  computation time which  is bounded by  a polynomial in $n$ and $N$. This allows us to sort the rows  of $M$ as in the proof of the
theorem and therefore produce a $k$--coloring in polynomial computing time.

It it straightforward to see  that  one  can start with a  $k$--coloring of $\Gamma$ and produce the surjection $\phi$ in polynomial time.





\section*{Acknowledgements}


\vspace{.5cm}

Ram\'{o}n Flores is supported by FEDER-MEC grant MTM2016-76453-C2-1-P and FEDER grant US-1263032 from the Andalusian
Government. Thomas Koberda is partially supported  by an
Alfred P. Sloan Foundation Research Fellowship, by NSF Grant DMS-1711488, and by NSF Grant DMS-2002596.
Delaram Kahrobaei is supported in part by a 
Canada's New Frontiers in Research Fund, under the Exploration grant entitled ``Algebraic Techniques for Quantum Security".
We thank Yago Antol\'{i}n, Juan Gonz\'alez-Meneses, Sang-hyun Kim,
and Andrew Sale for helpful discussions  and comments.
We thank the University of York for hospitality while part of this research
 was conducted. Finally, we thank an anonymous referee for helpful comments.
\bibliographystyle{amsplain}
