\section{\@startsection {section}{1}{\z@}{-3ex \@plus -1ex \@minus -.2ex}{2ex \@plus.2ex}{\normalfont\large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}{-2.5ex\@plus -1ex \@minus -.2ex}{1.5ex \@plus .2ex}{\normalfont\normalsize\bfseries}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}{-2ex\@plus -1ex \@minus -.2ex}{1ex \@plus .2ex}{\normalfont\normalsize\bfseries}}
 \renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}{1.5ex \@plus.5ex \@minus.2ex}{-1em}{\normalfont\normalsize\bfseries}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}  {1.5ex \@plus.5ex \@minus .2ex}  {-1em} {\normalfont\normalsize\bfseries}}
\makeatother
\def{\mathcal X} {{\mathcal X}}
\def{\mathcal S} {{\mathcal S}}
\def{\mathcal C} {{\mathcal C}}
\def{\mathcal V} {{\mathcal V}}
\def{\mathcal M} {{\mathcal M}}
\def{\mathcal P} {{\mathcal P}}
\def{\mathcal{Q}} {{\mathcal{Q}}}
\def{\mathcal L} {{\mathcal L}}
\DeclareMathOperator{\dist}{dist}
\newcommand{\ngs}[2][]{N_{#1}^{\geq s}(#2)}
\newcommand{\nls}[2][]{N_{#1}^{< s}(#2)}
\newcommand\comment[1]{\noindent\textcolor{red}{[#1]}}
\newcommand\res[1]{\noindent\textcolor{blue}{[#1]}}
\newcommand{\ceil}[1]{\lceil{#1}\rceil}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\newcommand\abs[1]{\lvert #1\rvert}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcommand{\defn}[1]{\textcolor{Maroon}{\emph{#1}}\index{#1}}
\newcommand{\mathdef}[2]{\textcolor{Maroon}{\emph{#1-#2}}\index{#2@#1-#2}}
\newcommand{\word}[1]{#1\index{#1}}
\begin{document}
\title{\bf\Large\boldmath
Clustered Coloring of Graphs with \\
Bounded Layered Treewidth and Bounded Degree\footnote{This material is based upon work supported by the National Science Foundation under Grant No.\ DMS-1664593, DMS-1929851, DMS-1954054 and DMS-2144042.}}
\footnotetext[0]{First released on 22nd May 2019 as part of arXiv:1905.08969. Revised \today.}
\author{%
Chun-Hung Liu\footnote{Department of Mathematics, Texas A\&M University, Texas, USA, \texttt{chliu@math.tamu.edu}. Partially supported by NSF under award No.\ DMS-1664593, DMS-1929851 and DMS-1954054 and CAREER award DMS-2144042.}
\quad David R. Wood\footnote{School of Mathematics, Monash University, Melbourne, Australia, \texttt{david.wood@monash.edu}. Research supported by the Australian Research Council.}
}
\date{}
\maketitle
\begin{abstract}
The clustering of a graph coloring is the maximum size of monochromatic components.
This paper studies colorings with bounded clustering in graph classes with bounded layered treewidth, which include planar graphs, graphs of bounded Euler genus, graphs embeddable on a fixed surface with a bounded number of crossings per edge, map graphs, amongst other examples. Our main theorem says that every graph with layered treewidth at most $k$ and with maximum degree at most $\Delta$ is $3$-colorable with clustering $O(k^{19}\Delta^{37})$.
This is the first known polynomial bound on the clustering. This greatly improves upon a corresponding result of Esperet and Joret for graphs of bounded genus.
\end{abstract}
\renewcommand{\thefootnote}{\arabic{footnote}}
\section{Introduction}
\label{Introduction}

This paper considers graph\footnote{Let $G$ be a graph with vertex-set $V(G)$ and edge-set $E(G)$.
For $v\in V(G)$, let $N_G(v):=\{w\in V(G): vw\in E(G)\}$ be the neighborhood of $v$, and let  $N_G[v] :=N_G(v) \cup\{v\}$.
For $X\subseteq V(G)$, let $N_G(X):= \bigcup_{v\in X} (N_G(v) \setminus X)$ and $N_G[X]:= N_G(X)\cup X$.
Denote the subgraph of $G$ induced by $X$ by $G[X]$.
Let $\mathbb{N}:=\{1,2,\dots\}$ and $\mathbb{N}_0:=\{0,1,2,\dots\}$.
For $m,n\in\mathbb{N}_0$, let $[m,n]:=\{m,m+1,\dots,n\}$ and $[n]:=[1,n]$.} colorings where the condition that adjacent vertices are assigned distinct colors is relaxed. Instead, we require that every monochromatic component has bounded size (for a given graph class).
More formally, a \defn{coloring} of a graph $G$ is a function that assigns one color to each vertex of $G$. For a coloring $c$ of $G$, a \mathdef{$c$}{monochromatic component}, or simply \defn{monochromatic component},
is any connected component of the subgraph of $G$ induced by all the vertices assigned the same color. A coloring has \defn{clustering} $\eta$ if every monochromatic component has at most $\eta$ vertices. Our focus is on minimizing the number of colors, with small monochromatic components as a secondary goal.
The \defn{clustered chromatic number} of a graph class $\mathcal{G}$ is the minimum integer $k$ such that for some integer $\eta$, every graph in $\mathcal{G}$ is $k$-colorable with clustering $\eta$. There have been several recent papers on this topic~\citep{NSSW19,vdHW18,HST03,ADOV03,CE19,Kawa08,KM07,LMST08,KO19,EJ14,EO16,DN17,LO17,HW19,MRW17}; see \citep{WoodSurvey} for a survey.

Planar graphs are 4-colorable, and indeed have clustered chromatic number 4. That is, for every $c$ there is a planar graph that is not 3-colorable with clustering $c$ \cite{KMRV97}. These examples have unbounded maximum degree. This led \citet{KMRV97} to conjecture that planar graphs with bounded maximum degree are 3-colorable with bounded clustering. Note that three colors is best possible since the Hex Lemma~\citep{Gale79} says that every 2-coloring of the $n\times n$ planar triangular grid (which has  maximum degree 6) contains a monochromatic path of length at least $n$.

\citet{EJ14} proved the conjecture of \citet{KMRV97}. In particular, they proved that every planar graph with maximum degree $\Delta$ is 3-colorable with clustering  $\Delta^{O(\Delta)}$. While \citet{EJ14} made no effort to reduce this function, their method will not lead to a  sub-exponential clustering bound. We prove the first known polynomial bound in such a result. \citet{EJ14} in fact proved 3-colorability in the more general setting of graphs embeddable on a fixed surface\footnote{The \defn{Euler genus} of an orientable surface with $h$ handles is $2h$. The \defn{Euler genus} of  a non-orientable surface with $c$ cross-caps is $c$. The \defn{Euler genus} of a graph $G$ is the minimum Euler genus of a surface in which $G$ embeds (with no crossings).}. In particular, they proved that graphs with Euler genus $g$ are 3-colorable with clustering $\Delta^{O(\Delta\,2^g)}$. We prove a polynomial bound in this setting as well.

\begin{theorem}\label{GenusDegree}
Every graph with Euler genus at most $g$ and maximum degree at most $\Delta$ is 3-colorable with clustering $O(g^{19}\Delta^{37})$.
\end{theorem}

Note that \citet{LO17} proved that for all fixed $t,\Delta$ there exists a constant $c$ such that every (odd) $K_t$-minor-free graph with maximum degree at most $\Delta$ is 3-colorable with clustering $c$.
This result extends \cref{GenusDegree} to more general graph classes but with much worse clustering $c$.

\cref{GenusDegree} is in fact a corollary of a more general result of this paper in terms of layered treewidth. First we explain what this means. A \defn{tree-decomposition} of a graph $G$ is a pair $(T,\mathcal{X} = (X_x:x\in V(T))$, where $T$ is a tree,  and for each node $x\in V(T)$,  $X_x$ is a non-empty subset of $V(G)$ called a \defn{bag}, such that for each vertex $v\in V(G)$, the set $\{x\in V(T):v\in X_x\}$ induces a non-empty (connected) subtree of $T$, and for each edge $vw\in E(G)$ there is a node $x\in V(T)$ such that $\{v,w\}\subseteq X_x$.
The \defn{width} of a tree-decomposition $(T,\mathcal{X})$ is $\max\{|X_x|-1: x\in V(T)\}$. The \defn{treewidth} of a graph $G$ is the minimum width of a tree-decomposition of $G$. Treewidth is a key parameter in algorithmic and structural graph theory; see \citep{Reed03,Reed97,Bodlaender-TCS98,HW17} for surveys.

A \defn{layering} of a graph $G$ is an ordered partition $(V_1,\dots,V_n)$ of $V(G)$ into (possibly empty) sets such that for each edge $vw\in E(G)$ there exists $i\in[1,n-1]$ such that $\{v,w\}\subseteq V_i\cup V_{i+1}$.
The \defn{layered treewidth} of a graph $G$ is the minimum nonnegative integer $\ell$ such that $G$ has a tree-decomposition $(T, \mathcal{X} = (X_x:x\in V(T))$ and a layering $(V_1,\dots,V_n)$, such that $|X_x\cap V_i|\leq\ell$ for each bag $X_x$ and layer $V_i$. This says that the subgraph induced by each layer has bounded treewidth, and moreover, a single tree-decomposition of $G$ has bounded treewidth when restricted to each layer. In fact, these properties hold when considering a bounded sequence of consecutive layers.

Layered treewidth was independently introduced by \citet{DMW17} and \citet{Shahrokhi13}. \citet{DMW17} proved that every planar graph has layered treewidth at most 3;  more generally, that every graph with Euler genus at most $g$ has layered treewidth at most $2g+3$; and most generally, that a minor-closed class has bounded layered treewidth if and only if it excludes some apex graph as a minor. Layered treewidth is of interest beyond minor-closed classes, since as described below, there are several natural graph classes that have bounded layered treewidth but contain arbitrarily large complete graph minors.

We prove that only three colors are needed
for clustered coloring of graphs with bounded layered treewidth and with bounded maximum degree. This is the main result of the paper.

\begin{theorem}\label{ltwdegree}
Every graph with layered treewidth at most $w$ and maximum degree at most $\Delta$ is 3-colorable with clustering $O(w^{19}\Delta^{37})$.
\end{theorem}

\cref{GenusDegree} is an immediate corollary of \cref{ltwdegree} and the above-mentioned bound of \citet{DMW17}. The proof of \cref{ltwdegree} (presented in \cref{BoundedDegree}) is simpler than the proof in \cite{EJ14}, avoiding many technicalities that arise when dealing with graph embeddings. This proof highlights the utility of layered treewidth as a general tool. Moreover, it leads to more general results, as we now explain.

\medskip
We now give three examples of graph classes with bounded layered treewidth, for which \cref{ltwdegree} give interesting results.

\paragraph{\boldmath $(g,k)$-Planar Graphs:} A graph is \mathdef{$(g,k)$}{planar} if it can be drawn in a surface of Euler genus at most $g$ with at most $k$ crossings on each edge (assuming no three edges cross at a single point). Such graphs can contain arbitrarily large complete graph minors, even in the $g=0$ and $k=1$ case \cite{DEW17}, so the above-mentioned result of \citet{LO17} is not applicable. On the other hand, \citet{DEW17} proved that every $(g,k)$-planar graph has layered treewidth at most $(4g + 6)(k + 1)$. \cref{ltwdegree} then implies:

\begin{corollary}
\label{gkPlanarDegree}
For all $g,k,\Delta \in \mathbb{N}$, every $(g,k)$-planar graph with maximum degree at most $\Delta$ is 3-colorable with clustering $O(g^{19}k^{19}\Delta^{37})$.
\end{corollary}

\paragraph{Map Graphs:} Map graphs are defined as follows. Start with a graph $G_0$ embedded in a surface of Euler genus $g$, with each face labelled a ``nation'' or a ``lake'', where each vertex of $G_0$ is incident with at most $d$ nations. Let $G$ be the graph whose vertices are the nations of $G_0$, where two vertices are adjacent in $G$ if the corresponding faces in $G_0$ share a vertex. Then $G$ is called a \mathdef{$(g,d)$}{map graph}. A $(0,d)$-map graph is called a \emph{(plane)} \mathdef{$d$}{map graph}; such graphs have been extensively studied \citep{FLS-SODA12,Chen07,DFHT05,CGP02,Chen01}. The $(g,3)$-map graphs are precisely the graphs of Euler genus at most $g$ (see \citep{CGP02,DEW17}).
So $(g,d)$-map graphs provide a natural generalization of graphs embedded in a surface that allows for arbitrarily large cliques even in the $g=0$ case (since if a vertex of $G_0$ is incident with $d$ nations then $G$ contains $K_d$).
\citet{DEW17} proved that every $(g,d)$-map graph has layered treewidth at most $(2g+3)(2d+1)$. Thus \cref{ltwdegree} implies:

\begin{corollary}
\label{MapGraphBoundedDegree}
For all $g,d,\Delta \in \mathbb{N}$, every $(g,d)$-map graph with maximum degree at most $\Delta$ is 3-colorable with clustering $O(g^{19}d^{19}\Delta^{37})$.
\end{corollary}

\paragraph{String Graphs:} A \defn{string graph} is the intersection graph of a set of curves in the plane with no three curves meeting at a single point \cite{PachToth-DCG02,SS-JCSS04,SSS-JCSS03,Krat-JCTB91,FP10,FP14}. For an integer $k\geq 2$, if each curve is in at most $k$ intersections with other curves, then the corresponding string graph is called a \mathdef{$k$}{string graph}. Note that two curves can intersect multiple times and contribute more than one intersection to each curve. A \mathdef{$(g,k)$}{string} graph is defined analogously for curves on a surface of Euler genus at most $g$. \citet{DJMNW18} proved that every $(g,k)$-string graph has layered treewidth at most $2(k-1)(2g+3)$. By definition, the maximum degree of a $(g,k)$-string graph is at most $k$. Thus \cref{ltwdegree} implies:

\begin{corollary}
\label{StringColor}
For all integers $g\geq 0$ and $k\geq 2$, there exists $\eta\in\mathbb{N}$ such that every $(g,k)$-string graph is $3$-colorable with clustering $O(g^{19}k^{56})$.
\end{corollary}

\section{The Proof}
\label{BoundedDegree}

This section proves \cref{ltwdegree}, which says that graphs of bounded layered treewidth and bounded maximum degree are  3-colorable with bounded clustering. We need the following analogous result by \citet{ADOV03} for bounded treewidth graphs.

\begin{lemma}[\citep{ADOV03}]
\label{ClusteringDegreeTreewidth}
There is a function $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ such that every graph with treewidth $w$  and maximum degree $\Delta$ is 2-colorable with clustering $f(w,\Delta) \in O(w\Delta)$.
\end{lemma}

For a graph $G$ with bounded maximum degree and bounded layered treewidth, if $(V_1,\dots,V_n)$ is the corresponding layering of $G$, then
\cref{ClusteringDegreeTreewidth} is applicable to $G[V_i]$, which has bounded treewidth.
The idea of the proof of \cref{ltwdegree} is to
use colors 1 and 2 for all layers $V_i$ with $i\equiv 1\pmod{3}$,
use colors 2 and 3 for all layers $V_i$ with $i\equiv 2\pmod{3}$,
and
use colors 3 and 1 for all layers $V_i$ with $i\equiv 3\pmod{3}$.
Then each monochromatic component is contained within two consecutive layers.
The key to the proof is to control the growth of monochromatic components between consecutive layers. The next lemma is useful for this purpose.

\begin{lemma} \label{enlarge}
Let $w,\Delta,d,k,h\in\mathbb{N}$.
Let $G$ be a graph with maximum degree at most $\Delta$.
Let $(T,{\mathcal X})$ be a tree-decomposition of $G$ with width at most $w$, where ${\mathcal X}=(X_t:t\in V(T))$.
For $i \geq 1$, let $Y_i$ be a subset of $V(T)$, $T_i$ a subtree of $T$ containing $Y_i$, and $E_i$ a set of pairs of vertices in $\bigcup_{x \in Y_i}X_x$ with $\lvert E_i \rvert \leq k$.
Let $G'$ be the graph with $V(G')=V(G)$ and $E(G')=E(G) \cup \bigcup_{i \geq 1} E_i$.
If every vertex of $G$ appears in at most $d$ pairs in $\bigcup_{i \geq 1} E_i$, and every vertex of $T$ is contained in at most $h$ members of $\{T_1,T_2,\dots\}$, then $G'$ has maximum degree at most $\Delta+d$ and has a tree-decomposition $(T,{\mathcal X}')$ of width at most $w+2hk$ with $X'_t \supseteq X_t$ for every $t \in V(T)$, where ${\mathcal X}'=(X'_t: t \in V(T))$.
\end{lemma}

\begin{proof}
Since every vertex of $G$ appears in at most $d$ pairs in $\bigcup_{i \geq 1} E_i$, $G'$ has maximum degree at most $\Delta+d$.
For every $i \geq 1$, let $Z_i$ be the set of the vertices appearing in some pair of $E_i$.
Note that $Z_i \subseteq \bigcup_{x \in Y_i}X_x$ and $\lvert Z_i \rvert \leq 2\lvert E_i \rvert \leq 2k$.
For every $t \in V(T)$, let $X_t' := X_t \cup \bigcup_{\{i: t \in V(T_i)\}}Z_i$.
Let ${\mathcal X}' := (X_t': t \in V(T))$.

We claim that $(T,{\mathcal X}')$ is a tree-decomposition of $G'$.
It is clear that $\bigcup_{t \in V(T)} X'_t \supseteq V(G')$.
For each $i \in\mathbb{N}$, for every $t \in V(T_i)$, since $X_t' \supseteq Z_i$, $X_t'$ contains both ends of each edge in $E_i$.
For each $v \in V(G')$,
$$\{t \in V(T): v \in X_t'\}=\{t \in V(T): v \in X_t\} \cup \bigcup_{\{i: v \in Z_i\}}V(T_i).$$
Note that for every $v \in V(G)$ and $i \geq 1$, if $v \in Z_i$ then $v\in X_t$ for some  $t \in Y_i \subseteq V(T_i)$.
Hence $\{t: v \in X_t'\}$ induces a subtree of $T$.
This proves that $(T,{\mathcal X}')$ is a tree-decomposition of $G'$.

Since for every $t \in V(T)$, $|X'_t| \leq |X_t| + \sum_{\{i:t\in V(T_i)\}}|Z_i|  \leq w+1+2hk$, the width of $(T,{\mathcal X}')$ is at most $w+2hk$.
Moreover, $X'_t \supseteq X_t$ for every $t \in V(T)$ by definition.
This proves the lemma.
\end{proof}

We now prove \cref{ltwdegree}.

\begin{theorem}
Let $\Delta, w \in \mathbb{N}$.
Then every graph $G$ with maximum degree at most $\Delta$ and with layered treewidth at most $w$ is 3-colorable with clustering  $g(w,\Delta)$, for some function $g(w,\Delta) \in O(w^{19}\Delta^{37})$.
\end{theorem}

\begin{proof}
Let $f$ be the function from \cref{ClusteringDegreeTreewidth}. Define
\begin{align*}
f_1 & := f(w,\Delta)  & &  \in O(w\Delta)\\
\Delta_2 & :=\Delta+ f_1\Delta^2 & & \in O(w\Delta^3)\\
w_2 & := w+2(w+1)f_1^2\Delta^2 & & \in O(w^3\Delta^4),\\
f_2 & := f(w_2,\Delta_2) & & \in O(w^4\Delta^7)\\
\Delta_3 & := \Delta+f_2\Delta^2 &  & \in O( w^4\Delta^{9})\\
w_3 & := w+4(w_2+1)f_2^2\Delta^2 & & \in O( w^{11} \Delta^{20})\\
f_3 & := f(w_3,\Delta_3) & & \in O( w^{15} \Delta^{29} )\\
g(w,\Delta) & :=(1+f_2\Delta)f_3 & & \in O( w^{19} \Delta^{37}  ).
\end{align*}

Let $G$ be a graph of maximum degree at most $\Delta$ and layered treewidth at most $w$.
Let $(T,{\mathcal X})$ and $(V_i: i \geq 1)$ be a tree-decomposition of $G$ and a layering of $G$ such that $\lvert X_t \cap V_i \rvert \leq w$ for every $t \in V(T)$ and $i \geq 1$, where ${\mathcal X}=(X_t: t \in V(T))$.
For $j \in [3]$, let $U_j = \bigcup_{i=0}^\infty V_{3i+j}$.

By \cref{ClusteringDegreeTreewidth}, there exists a coloring $c_1: U_1 \rightarrow \{1,2\}$ such that every monochromatic component of $G[U_1]$ contains at most $f_1$ vertices.
For each $i \in\mathbb{N}_0$, let ${\mathcal C}_i$ be the set of $c_1$-monochromatic components of $G[U_1]$ contained in $V_{3i+1}$ with color 2.
For each $i \in\mathbb{N}_0$ and $C \in {\mathcal C}_i$, define the following:
	\begin{itemize}
		\item Let $Y_{i,C}$  be a minimal subset of $V(T)$ such that for every edge $e$ of $G$ between $V(C)$ and $N_G(V(C)) \cap V_{3i+2}$, there exists a node $t \in Y_{i,C}$ such that both ends of $e$ belong to $X_t$.
		\item Let $E_{i,C}$  be the set of all pairs of distinct vertices in $N_G(V(C)) \cap V_{3i+2}$.
		\item Let $T_{i,C}$  be the subtree of $T$ induced by $\{t \in V(T): X_t \cap V(C) \neq \emptyset\}$.
	\end{itemize}
Note that there are at most $\lvert V(C) \rvert \Delta \leq f_1\Delta$ edges of $G$ between $V(C)$ and $N_G(V(C))$.
So $\lvert Y_{i,C} \rvert \leq f_1\Delta$ and $\lvert E_{i,C} \rvert \leq f_1^2\Delta^2$ for every $i \in\mathbb{N}_0$ and $C \in {\mathcal C}_i$.
In addition, $Y_{i,C} \subseteq V(T_{i,C})$ for every $i \in\mathbb{N}_0$ and $C \in {\mathcal C}_i$.
Since $(T,(X_t \cap U_1: t \in V(T)))$ is a tree-decomposition of $G[U_1]$ with width at most $w$, for every $t \in V(T)$ and $i \in\mathbb{N}_0$, there exist at most $w+1$ different members $C$ of ${\mathcal C}_i$ such that $t \in V(T_{i,C})$.
Furthermore, $N_G(V(C)) \cap V_{3i+2} \subseteq \bigcup_{x \in Y_{i,C}} X_x$, so each pair in $E_{i,C}$ consists of two vertices in $\bigcup_{x \in Y_{i,C}}X_x$.
Since every vertex $v$ in $U_2$ is adjacent in $G$ to at most $\Delta$ members of $\bigcup_{i \in\mathbb{N}_0}{\mathcal C}_i$ and every member $C$ of $\bigcup_{i \in\mathbb{N}_0}{\mathcal C}_i$ creates at most $f_1\Delta$ pairs in $E_{i_C,C}$ involving $v$, where $i_C$ is the index such that $C \in {\mathcal C}_{i_{C}}$, every vertex in $U_2$ appears in at most $f_1\Delta \cdot \Delta=f_1\Delta^2$ pairs in $\bigcup_{i \in\mathbb{N}_0,C \in {\mathcal C}_i} E_{i,C}$.

Let $G_2$ be the graph with $V(G_2):=U_2$ and
$$E(G_2):=E(G[U_2]) \cup \bigcup_{i \in\mathbb{N}_0, C \in {\mathcal C}_i} E_{i,C}.$$
We have shown that \cref{enlarge} is applicable with $(G,T,{\mathcal X})=(G[V_{3i+2}],T,(X_t \cap V_{3i+2}: t \in V(T)))$ (for each $i \in \mathbb{N}_0$), $k=f_1^2\Delta^2$ and $d=f_1\Delta^2$ and $h=w+1$.
Thus $G_2$ has maximum degree at most $\Delta_2$ and a tree-decomposition $(T,{\mathcal X}^{(2)})$ with $X^{(2)}_t \supseteq X_t$ for every $t \in V(T)$, where ${\mathcal X}^{(2)} = (X^{(2)}_t: t \in V(T))$, such that for each $i \in \mathbb{N}_0$, $(T,(X^{(2)}_t \cap V_{3i+2}: t \in V(T)))$ is a tree-decomposition of $G_2[V_{3i+2}]$ of width at most $w_2$.
Since there exists no edge of $G_2$ between $V_{3i+2}$ and $V_{3i'+2}$ for $i<i'$, by \cref{ClusteringDegreeTreewidth}, there exists a coloring $c_2: U_2 \rightarrow \{2,3\}$ such that every $c_2$-monochromatic component of $G_2$ contains at most $f_2$ vertices.

Since $X^{(2)}_t \supseteq X_t$ for every $t \in V(T)$, we may assume that $(T,{\mathcal X}^{(2)})$ is a tree-decomposition of $G[U_1 \cup U_2]$ by redefining $X^{(2)}_t$ to be the union of $X^{(2)}_t$ and $X_t \cap U_1$, for every $t \in V(T)$.

For each $i \in\mathbb{N}_0$, let ${\mathcal C}_i'$ be the set of the monochromatic components either of $G[U_1]$ with color 1 with respect to $c_1$ contained in $V_{3i+4}$ or of $G_2$ with color 3 with respect to $c_2$ contained in $V_{3i+2}$.
For each $i \in\mathbb{N}_0$ and $C \in {\mathcal C}_i'$, define the following:
	\begin{itemize}
		\item Let $Y'_{i,C}$ be a minimal subset of $V(T)$ such that for every edge $e$ of $G$ between $V(C)$ and $N_G(V(C)) \cap V_{3i+3}$, there exists a node $t \in Y'_{i,C}$ such that both ends of $e$ belong to $X_t$.
		\item Let $E'_{i,C}$ be the set of all pairs of distinct vertices of $N_G(V(C)) \cap V_{3i+3}$.
		\item Let $T'_{i,C}$ be the subtree of $T$ induced by $\{t \in V(T): X^{(2)}_t \cap V(C) \neq \emptyset\}$.
	\end{itemize}
Note that there are at most $\lvert V(C) \rvert \Delta \leq f_2\Delta$ edges of $G$ between $V(C)$ and $N_G(V(C)) \cap V_{3i+3}$ for every $i \in\mathbb{N}_0$ and $C \in {\mathcal C}_i'$.
So $\lvert Y'_{i,C} \rvert \leq f_2\Delta$ and $\lvert E'_{i,C} \rvert \leq f_2^2\Delta^2$ for every $i \in\mathbb{N}_0$ and $C \in {\mathcal C}_i'$.
In addition, $Y'_{i,C} \subseteq V(T'_{i,C})$ for every $i \in\mathbb{N}_0$ and $C \in {\mathcal C}_i'$.
For every $i \in \mathbb{N}_0$, since $(T,(X^{(2)}_t \cap U_2: t \in V(T)))$ is a tree-decomposition of $G_2$ with $\lvert X^{(2)}_t \cap V_{3i+2} \rvert \leq w_2+1$ and $(T,(X_t^{(2)} \cap U_1: t \in V(T)))$ is a tree-decomposition of $G[U_1]$ with $\lvert X^{(2)}_t \cap V_{3i+4} \rvert \leq w+1 \leq w_2+1$, we know that for every $t \in V(T)$, there exist at most $2(w_2+1)$ different members $C \in {\mathcal C}_i$ such that $t \in V(T'_{i,C})$.
Furthermore, each pair in $E'_{i,C}$ consists of two vertices in $\bigcup_{x \in Y'_{i,C}}X_x^{(2)}$.
Since every vertex $v$ in $U_3$ is adjacent in $G$ to at most $\Delta$ members of $\bigcup_{i \in\mathbb{N}_0}{\mathcal C}_i'$, and every member $C$ of $\bigcup_{i \in\mathbb{N}_0}{\mathcal C}_i'$ creates at most $f_2\Delta$ pairs in $E_{i_C,C}$ involving $v$, where $i_C$ is the index such that $C \in {\mathcal C}_{i_C}'$, every vertex in $U_3$ appears in at most $f_2\Delta^2$ pairs in $\bigcup_{i \in\mathbb{N}_0,C \in {\mathcal C}_i'} E_{i,C}$.

Let $G_3$ be the graph with $V(G_3):=U_3$ and
$$E(G_3):=E(G[U_3]) \cup \bigcup_{i \in\mathbb{N}_0, C \in {\mathcal C}_i'} E'_{i,C}.$$
We have shown that \cref{enlarge} is applicable with $(G,T,{\mathcal X})=(G[V_{3i+3}],T,(X_t \cap V_{3i+3}: t \in V(T)))$ (for each $i \in \mathbb{N}_0$), $k=f_2^2\Delta^2$ and $d=f_2\Delta^2$ and $h=2(w_2+1)$.
Hence $G_3$ has maximum degree at most $\Delta_3$ and a tree-decomposition $(T,{\mathcal X}^{(3)})$ with $X^{(3)}_t \supseteq X_t$ for each $t \in V(T)$, where ${\mathcal X}^{(3)}=(X^{(3)}_t: t \in V(T))$, such that $(T,(X^{(3)}_t \cap V_{3i+3}: t \in V(T)))$ is a tree-decomposition of $G_3[V_{3i+3}]$ of width at most $w_3$ for every $i \in \mathbb{N}_0$.
Since there exists no edge of $G_3$ between $V_{3i+3}$ and $V_{3i'+3}$ for $i<i'$, by \cref{ClusteringDegreeTreewidth}, there exists a coloring $c_3: U_3 \rightarrow \{1,3\}$ such that every monochromatic component of $G_3$ contains at most $f_3$ vertices.

Define $c: V(G) \rightarrow \{1,2,3\}$ such that for every $v \in V(G)$, we have $c(v):=c_j(v)$, where $j$ is the index for which $v \in U_j$.
Now we prove that every $c$-monochromatic component of $G$ contains at most $g(w,\Delta)$ vertices.

Let $D$ be a $c$-monochromatic component of $G$ with color 2.
Since $D$ is connected, for every pair of vertices $u,v \in V(D) \cap U_2$, there exists a path $P_{uv}$ in $D$ from $u$ to $v$.
Since $V(D) \subseteq U_1 \cup U_2$, for every maximal subpath $P$ of $P_{uv}$ contained in $U_1$,
there exists $i\in\mathbb{N}_0$ and $C \in {\mathcal C}_i$ such that there exists a pair in
$E_{i,C}$ consisting of the two vertices in $P_{uv}$ adjacent to the ends of $P$.
That is, there exists a path in $G_2[V(D) \cap U_2]$ connecting $u,v$ for every pair $u,v \in V(D) \cap U_2$.
Hence $G_2[V(D) \cap U_2]$ is connected.
So $G_2[V(D) \cap U_2]$ is a $c_2$-monochromatic component of $G_2$ with color 2 and contains at most $f_2$ vertices.
Hence there are at most $f_2\Delta$ edges of $G$ between $V(D) \cap U_2$ and $N_G(V(D) \cap U_2)$.
So $D[V(D) \cap U_1]$ contains at most $f_2\Delta$ components.
Since each component of $D[V(D) \cap U_1]$ is a $c_1$-monochromatic component of $G[U_1]$, it contains at most $f_1$ vertices.
Hence $D[V(D) \cap U_1]$ contains at most $f_2\Delta f_1$ vertices.
Since $D$ has color 2, $V(D) \cap U_3=\emptyset$.
Therefore, $D$ contains at most $(1+f_1\Delta)f_2 \leq g(w,\Delta)$ vertices.

Let $D'$ be a $c$-monochromatic component of $G$ with color $b$, where $b \in \{1,3\}$.
Since $D'$ is connected, by an analogous argument to that in the previous paragraph, $G_3[V(D') \cap U_3]$ is connected.
So $G_3[V(D') \cap U_3]$ is a $c_3$-monochromatic component of $G_3$ with color $b$ and contains at most $f_3$ vertices.
Hence there are at most $f_3\Delta$ edges of $G$ between $V(D') \cap U_3$ and $N_G(V(D') \cap U_3)$.
So $D[V(D) \cap U_{b'}]$ contains at most $f_3\Delta$ components, where $b'=1$ if $b=1$ and $b'=2$ if $b=3$.
Since each component of $D[V(D) \cap U_{b'}]$ is a $c_{b'}$-monochromatic component of $G[U_{b'}]$, it contains at most $f_2$ vertices.
Hence $D[V(D) \cap U_{b'}]$ contains at most $f_3\Delta f_2$ vertices.
Since $D$ has color $b$, $V(D) \cap U_{b+1}=\emptyset$, where $U_4=U_1$.
Therefore, $D$ contains at most $(1+f_2\Delta)f_3 \leq g(w,\Delta)$ vertices.
This completes the proof.
\end{proof}

\section{Subsequent Work}

The following extension of \cref{ltwdegree} is proved in our companion paper~\citep{LW1}.

\begin{theorem}[\citep{LW1}]
\label{ltwbasic}
For all $s,t,w\in\mathbb{N}$ there exists $\eta\in\mathbb{N}$ such that every graph with layered treewidth at most $w$ and with no $K_{s,t}$ subgraph is $(s+2)$-colorable with clustering $\eta$.
\end{theorem}

Graphs with no $K_{1,t}$ subgraph are exactly those with maximum degree less than $t$. Thus, \cref{ltwbasic} with $s=1$ says that graphs with bounded layered treewidth and bounded maximum degree are 3-colourable with bounded clustering, as in \cref{ltwdegree}. On the other hand, the proof of \cref{ltwbasic} is much more complicated than that of \cref{ltwdegree} and the clustering bound in \cref{ltwbasic} is much larger than the polynomial clustering bound in \cref{ltwdegree}.

\cref{ltwdegree,ltwbasic} (and their proofs) were first presented in reference~\citep{LW1} in 2019. This paper has now been split into the present paper and a separate paper proving \cref{ltwbasic}. Other proofs of \cref{ltwdegree} have since been obtained. One such proof is obtained via weak diameter coloring~\citep{BBEGLPS,Liu21a}, although this proof does not give a polynomial bound for the clustering. Another proof, due to \citet{DEMWW22}, improves the $O(w^{19}\Delta^{37})$ bound in \cref{ltwdegree} to $O(w^3\Delta^2)$.

Recall that \citet{LO17} proved that every $K_t$-minor free graph with bounded maximum degree is 3-colorable with bounded clustering. New proofs of this result are included in \citep{BBEGLPS,Liu21a,Liu22}, where the proof in \citep{Liu22} relies on \cref{ltwdegree} in the present paper.

\bibliographystyle{DavidNatbibStyle}


\section*{Ethical Implications}

This work aims to provide users with an effective framework for adapting the output of diffusion models to the preferred aesthetics of the user. While general text-to-image models might be biased towards specific attributes when synthesizing images from text, our approach enables the user to better reflect the desirable effects. On the other hand, malicious agents might try to use generated images to mislead viewers. This is a common issue, existing in other generative modeling approaches. Future research in generative modeling and personalization must continue investigating and revaluing these issues.

{
\small

\bibliographystyle{plain}


\section{Introduction}

Van der Waals (vdW) two-dimensional (2D) materials have attracted tremendous attention as they host novel properties in atomically thin systems, creating a wide area for fundamental research and potentital applications~\cite{1,2}. Many novel quantum phenomena, such as superconductivity, topological order and anomalous quantum Hall effect, which are promising in future quantum technologies, have also been found in vdW materials~\cite{2-1,2-2,2-3,2-4}.
Among them, vdW materials with intrinsic magnetic and ferroelectric orders down to atomically thin layers, have received special attention, due to their potential to provide valuable platforms for the realization of nanoscale electronic devices~\cite{5,6}, such as spin field-effect  transistors~\cite{6-1,6-2} and ferroelectric random access memories~\cite{7-1,7-2,7-3,7,8}. Especially, vdW materials with intrinsic type-II multiferroicity, whose inversion symmetry is broken by magnetic orders, have created new opportunities to not only explore novel mechanisms of magnetoelectric coupling in 2D ~\cite{9}, but also construct multifunctional electronic devices.

Transition-metal dihalides MX$_{2}$ (where M is a transition metal and X is a haloge) is a class of vdW material with many multiferroic members, such as NiBr$_{2}$, MnI$_{2}$, CoI$_{2}$ and NiI$_{2}$~\cite{10,11}. Among them, NiI$_{2}$, a typical transition-metal dihalides with helical magnetic structures~\cite{12}, has attracted a lot of researchers to study its magnetic properties~\cite{13,14,15}. After type-II multiferroic ground state been confirmed in bulk NiI$_{2}$~\cite{16}, great efforts have been made to study its magnetic and ferroelectric properties in few layers form. Ju \textit{et al.} demonstrated that the NiI$_{2}$  has a  multiferroic state with a helical spin order even down to bilayer~\cite{17}. More recently, convincing evidence of the existence of multiferroic order in NiI$_{2}$ monolayer has been reported below a transition temperature $\sim$ 21 K~\cite{9}. Fumega \textit{et al.} then studied the freestanding NiI$_{2}$ monolayer based on \textit{ ab initio} calculations and revealed a locking between its helimagnetic and ferroelectric orders. However, the low transition temperature and weak ferroelectricity hinder its future applications in multifunctional devices. Strain engineering has been proven a powerful tool to tune properties of 2D materials, such as in CrI$_{3}$~\cite{20}, Fe$_{3}$GeTe$_{2}$~\cite{21}, and CrTe$_{2}$~\cite{22}. By varing applied strains, such as epitaxially growing monolayer NiI$_{2}$ on different substrates, we may manipulate its structure and magnetic orders to promote the multiferroic transition temperatures and electric polarizations.

In this work, we study the multiferroic order of freestanding monolayer NiI$_{2}$ with engineered levels of strain using density functional theory (DFT) calculations and Monte Carlo(MC) simulations. Through the investigation of strain-free monolayer NiI$_{2}$, we find that the first nearest neighbor (NN) and third NN exchange interactions play an essential role in the formation of its magnetic phase diagrams. The competition of these interactions induces magnetic frustration, leading to the formation of proper-screw helimagnetic (HM) ground state. We further show that these conclusions drawing from the strain-free monolayer can be well generalized to the cases within our engineered range of strains. Notably, our calculations show that with 6\% tensile strain on the $a$-axis and 8\% compressive strain on the $b$-axis, the N\'{e}el temperature $T_N$ can be significantly enhanced to 101 K, about 5 times higher than that of the strain-free one. The strength of spontaneous electric polarizations can also be more than doubled under 8\% uniform compressive strain on both axises. Moreover, we construct a NiI$_{2}$ (monolayer)/Graphene (bilayer) heterostructure to simulate a more realistic strain engineering and obtain results in good agreement with that from our calculations on corresponding freestanding one. Our work suggests that strain is a promising way to tune multiferroic orders in the monolayer NiI$_{2}$, with the potential to signicanlty promote its transition temperatures and electric polarizations, therefore broaden the prospect of its applications in spintronics devices.

\begin{figure}[t]
	\includegraphics[scale=0.40]{chutu_1.pdf}
	\caption{ (a) Side and top view of monolayer NiI$_{2}$ in a primitive cell. Blue and gray spheres represent Ni and I atoms, respectively.
	(b) The exchange paths are shown in black dotted line with arrows.}
	\label{tu1}
\end{figure}

\section{methods}

First-principles calculations are carried out with the Vienna $ab\ initio$ Simulation Package (VASP)~\cite{23,24}. We use the Perdew Burke-Ernzerhof functional with a spin-polarized generalized gradient approximation (GGA). The projector augmented-wave (PAW)~\cite{26} method with a 500 eV plane wave cutoff is employed, and a 20 $\times$ 20 $\times$ 4 $\Gamma$-centered k-point mesh allows the calculations to converge well. A vacuum layer thickness of 15 \AA\ along the out-of-plane direction is used to avoid interaction between adjacent atomic layers. The spin-polarized GGA is combined with onsite Coulomb interactions, $U$, included for Ni 3$d$ orbitals (GGA + $U$)~\cite{25}. We employ $U = 4$ eV and $J = 1$ eV, which achieves values of the magnetic moments and band gap consistent with experiments~\cite{28,29}. Upon applying strain, we relax the crystal structure until the forces acting on each atom are less than 1 meV/\AA. We determine the values of Heisenberg exchange interactions by fitting all $J$ parameters to energies calculated by DFT using 20 randomly generated collinear magnetic configurations~\cite{30,31,PhysRevB.105.214303}. In-plane strain is defined as  $\frac{a-a_0}{a_0}$ $\times$ 100\%\, where $a_0$ and $a$ denote lattice constants before and after applying strain. Moreover, we consider the strains within [ -8\%, 8\% ], which are sampled with an interval of 1\% strain along each direction. For convenience,  $x$ and $y$ are used to denote the strain level applied on the $a$-axis and $b$-axis, respectively. Electric polarizations are calculated using the Berry phase method~\cite{27}. The full atomic relaxtion for all atoms in the heterostructure takes into account the vdW force through DFT-D3 method of Grimme~\cite{grimme2010consistent}. Based on the calculated magnetic exchange interactions, we then explore the magnetic phase diagrams by a replica-exchange MC method~\cite{32}. The helical magnetic orders and corresponding magnetic propogation vectors $\boldsymbol{Q}$ are identified by performing Fourier analysis on the magnetic configurations produced from MC simulations.

\section{Results and discussions}

\subsection{Strain-free monolayer NiI$_{2}$ }

Bulk NiI$_2$ has the space group \textit{R$\overline{3}$m} (No. 166) with experimental lattice constants $a$ = $b$ = 4.46 \AA\ and c = 10.73 \AA~\cite{9,32-1}. Experiments confirm that a HM state coexists with spontaneous electric polarization in the bulk NiI$_{2}$ when tempearture drops below $T_{N}$ = 59.5 K, with a HM propogation vector $\boldsymbol{Q}$ = (0.138, 0, 1.457)~\cite{12}. The monolayer NiI$_{2}$ , which could be potentially exfoliated from a bulk NiI$_{2}$, has a reduced lattice symmetry with \textit{P$\overline{3}$m1} (No.164)~\cite{32-2}. As shown in Fig.~\ref{tu1}(a), the monolayer NiI$_{2}$ is constructed by sandwiching one layer of Ni atoms between two layers of I atoms, where the three nearest Ni atoms form an equilateral triangle, with each Ni centred at a NiI$_{6}$ octahedron. For magnetic structures, although a nearest neighbour ferromagnetic (FM) interaction is expected from a 92$^{\circ}$ Ni-I-Ni bond angle according to the Goodenough-Kanamori rule~\cite{33}, both experimental and theoretical studies show that a HM state is more stable in the bulk NiI$_{2}$~\cite{12,32-3} and even in the few-layers form~\cite{32-1,9}, suggesting that a HM ground state is also likely in the monolayer.

\begin{figure*}[t]
	\includegraphics[scale=0.45]{chutu_2.pdf}
	\caption{ (a) Schematic of the directions of $\boldsymbol{Q}$ and electric polarization $\boldsymbol{P}$ in real space. (b) The schematic of the cycloid and proper-screw magnetic order. (c) Illustration of the $\boldsymbol{Q}_{1}$ = (0.25, -0.125, 0) HM state, where the large blue arrows and small black arrows represent the spin of Ni and I atoms respectively. The colour map shows the out-of-plane spin component with red and green denoting spin-up and spin-down respectively.  (d)-(e) The band structures of monolayer NiI$_{2}$ in FM and HM states folded back into a primitive cell calculated without SOC. (f) The Band structure of FM and HM states with SOC.}
	\label{tu2}
\end{figure*}

We utilize the classic Heisenberg model to describe the magnetic interactions in freestanding monolayer NiI$_{2}$~\cite{19,34},
  \begin{equation}
    \begin{aligned}
    \textit{H} = \sum_{ij}J_{ij}\textbf{S}_i\ \cdot\ \textbf{S}_j-\sum_{i}(\textbf{D}\ \cdot\ \textbf{S}_i)^{2}
    \end{aligned}\label{eq:1}
  \end{equation}
where $J_{ij}$ are exchange interactions between Ni spins $\boldsymbol{S}_i$ and $\boldsymbol{S}_j$. The term with $\boldsymbol{D}$ represents the magnetic anisotropy energy (MAE). We only consider exchange interactions with Ni-Ni bond lengths less than 10 \AA\ .Because of the preservation of three-fold rotation axis in the strain-free case, there are only three types of nonequivalent exchange interactions, labeled as $J_{1}$, $J_{2}$ and $J_{3}$, as shown in Fig.~\ref{tu1}(b). Our DFT calculations produce $J_{1}$, $J_{2}$ and $J_{3}$ as -4.52 meV, -0.21 meV and 3.92 meV, respectively. The $\boldsymbol{D}$ are calculated to be (0, 0, 0.39) meV, corresponding to an MAE $\sim$ 0.15 meV/Ni with an easy axis along the $c$ direction. Evidently, the MAE is too weak to affect the $T_N$, as well as the magnetic vectors of the HM states, therefore for simplicity, we first analyse the ground state magnetic structures without considering MAE.

In the absence of MAE, a spin rotation axis in HM state can be generally assumed to be along the $c$ direction and then each spin value in the monolayer NiI$_{2}$ can be determined by
\begin{equation}
\begin{aligned}
\textbf{S$_{n,0}$} = &S_0\cdot(cos(\textbf{Q} \cdot\ (\textbf{R}_n\ + \textbf{R}_0\ ))sin(\gamma\ ))\ \textbf{a}\ \\
&+ S_0\cdot(sin(\textbf{Q} \cdot\ (\textbf{R}_n\ + \textbf{R}_0\ ))sin(\gamma\ ))\ \textbf{b}\  \\
&+ cos(\gamma\ )\ \textbf{c}\
\end{aligned}\label{eq:2}
\end{equation}
where $S_{0}$ is the magnitude of each spin, $\boldsymbol{R}_{n}$ is the lattice vector pointing from the unit cell 0 to unit cell n,  $\boldsymbol{R}_{0}$ is the position of the spin at origin, $\gamma$ is the cone angle between the rotation axis and the magnetic moment of each atoms.

Denoting $\boldsymbol{Q}$ =($q_{a}$, $q_{b}$, 0), the magnetic Hamiltonian in a primitive cell can then be explicitly written as
  \begin{equation}
\begin{aligned}
\textit{H$_{iso}$} &= J_1 S_0^2 sin^2(\gamma\ ) (cos(q_a)+cos(q_b)+cos(q_a+q_b))\ \\
&+J_2 S_0^2 sin^2(\gamma\ ) (cos(2q_a+q_b)+cos(q_a+2q_b)\\
& \ \ \  \ \ \ \ \ \  \ \ \ \ \ \  \ \ \ \ \ \ \ +cos(q_a-q_b))\ \\
&+ J_3 S_0^2 sin^2(\gamma\ ) (cos(2q_a)+cos(2q_b)\\
& \ \ \  \ \ \ \ \ \  \ \ \ \ \ \  \ \ \ \ \ \ \ +cos(2q_a+2q_b))\ \\
&+(J_1+J_2+J_3)S_0^2 cos^2(\gamma\ )
\end{aligned}\label{eq:3}
\end{equation}
By performing derivation of Eq. (\ref{eq:3}) with respect to $q_{a}$ and $q_{b}$,  we can find the corresponding magnetic ground state.
  \begin{equation}
\begin{aligned}
\frac{\partial\ \textit{H$_{iso}$}}{\partial\ q_a} =0\ \& \ \frac{\partial\ \textit{H$_{iso}$}}{\partial\ q_b} =0
\end{aligned}\label{eq:4}
\end{equation}
By solving Eq. (\ref{eq:4}), we get the relation
  \begin{equation}
\begin{aligned}
 q_a , q_b \sim arctan((\frac{J_1 +3J_2 +4J_3 }{J_2-J_1+4J_3})^{1/2})
\end{aligned}\label{eq:5}
\end{equation}
From Eq. (\ref{eq:5}), we can see that the solutions of $q_{a}$ and $q_{b}$ only exist when
  \begin{equation}
\begin{aligned}
\frac{J_1 +3J_2 +4J_3 }{J_2-J_1+4J_3} > 0
\end{aligned}\label{eq:6}
\end{equation}

\begin{figure}[t]
	\includegraphics[scale=0.50]{chutu_3.pdf}
	\caption{ (a) The magnetic exchange interactions $J_{1}$, $J_{2}$ , $J_{3}$, and the N\'{e}el temperature $T_N$ with uniform strains. (b) The $J_{1a-1c}$,$J_{2a-2c}$ , $J_{3a-3c}$ and $T_N$ as functions of $y$, with $x=0 \%$.}
	\label{tu3}
\end{figure}

\begin{table*}[t!]
	\caption{ \label{tab1-1} Values (in meV) of magnetic exchange couplings and $T_{N}$ by DFT calculation and MC simulations in three typical strains. }
	\begin{ruledtabular}
		\begin{tabular}{cccccccccccc}
			& $x$($a$-axis) \& $y$($b$-axis) strain & $ J_{1a}$ & $ J_{1b}$ & $J_{1c}$ & $ J_{2a}$  & $ J_{2b}$ & $J_{2c}$ & $ J_{3a}$ & $ J_{3b}$ & $ J_3c$ & $T_{N}$(K) \\
			\hline  \\[-1.0ex]
			& 7\% \& 8\% & -3.74 & -3.73 & -3.74 & -0.14 & -0.14 & -0.16 & 1.83 & 1.70 & 1.59 & 13.77  \\
			& 7\% \& -3\% &-4.02 & -4.39 & -4.60 & -0.06 & -0.16 & -0.26 & 6.74 & 2.76 & 1.53  & 51.85\\
			& 6\% \& -8\% &-3.42 & -4.25 & -4.68 & 0.34 & -0.05 & -0.44 & 13.27 & 3.47 & 1.52 &  101.17 \\
		\end{tabular}
	\end{ruledtabular}
\end{table*}

\begin{figure}[t]
	\includegraphics[scale=0.47]{chutu_4.pdf}
	\caption{ (a) $T_{N}$ as a function of lattice constants $a$ and $b$, where the dark spots represent sampled strain points. (b)-(c) The $q_a$ and $q_b$ component of HM spin vector $\boldsymbol{Q}$ as a function of lattice constants $a$ and $b$.}
	\label{tu4}
\end{figure}

Our calculated $J$'s fulfill the requirement of Eq. (\ref{eq:6}), suggesting that the ground state of monolayer NiI$_{2}$ should be HM. Evidently, frustration from the strong FM $J_{1}$ and the AFM $J_{3}$ are the main driving force for the formation of the HM state, while $J_2$ is too weak to qualitatively contribute. MC simulations with the calculated parameters are then performed, confirming the presence of a single phase transtion from a paramagnetic phase to a HM phase, with a $T_{N}$ = 22.81 K, in good agreement with the experimental result of 21 K~\cite{9}. The HM state possesses a single $\boldsymbol{Q}$ , which has six symmetrically equivalent values(see Fig.~\ref{tu2}(a)), confirmed by Fourier analysis on the spin configurations output by the MC simulations. All six $\boldsymbol{Q}$ are along $C_{2}$ axis of monolayer NiI$_{2}$, i.e. [100], [010] and [110] directions, with $|\boldsymbol{Q}|$= 0.216 (2$\pi$)/$a$ (see Fig.~\ref{tu2}(a)). The two-component $\boldsymbol{Q}$'s are distinct from that used in literatures, where the in-plane component (0.138, 0, 0) of the experimental $\boldsymbol{Q}$ of the bulk NiI$_{2}$ is simply assumed~\cite{19}. To double check our model against DFT calculations, we further performed calculations on cycloid magnetic structures using the generalized Bloch theorem. The results show that the total energy of our HM state is lower than the most stable single-component $\boldsymbol{Q}$ state.

The electric polarization $\boldsymbol{P}$ of monolayer NiI$_{2}$ was reported to be parallel to the $C_2$ axis~\cite{9}. Given our calculated $\boldsymbol{Q}$ values, which are also parallel to the $C_2$ axis (see also illustration in Fig.~\ref{tu2}(a)), the measured $\boldsymbol{P}$ is expected to correspond to proper-screw HM states, according to symmetry arguements and calculations in isostructural MnI$_2$~\cite{18}. However, our model can not distinguish a cycloid from a proper-screw order (see Fig.~\ref{tu2}(b)). We thus again resort to direct DFT calculations. Without losing generality, we focus on the case with $\boldsymbol{Q}_{1}$ = (0.25, -0.125, 0), which can be simulated using a 4$\times$8$\times$1 supercell for both cycloid and proper-screw HM case. DFT calculations show that the proper-screw HM state is energetically more stable with 11.67 meV lower than the cycloidal one. We therefore propose that the magnetic ground state of monolayer NiI$_{2}$ is a proper-screw HM state. It is worth noting that the I atoms are also calculated to develop sizable magnetizations about 0.20 $\mu_B$, forming a proper-screw HM state in coordination with that formed by the Ni spins(see Fig.~\ref{tu2}(c)). Furthermore for ferroelectricity, we obtain an estimation of the polarization with an amplidute $|\boldsymbol{P}|$ $\sim$ 2.62 $\times$ 10$^{-13}$ Cm$^{-1}$, with directions parallel to each $\boldsymbol{Q}$ (see Fig.~\ref{tu2}(a)).

We further systematically investigate the electronic structure of monolayer NiI$_{2}$. For comparison, the band structure of the FM state without SOC is first calculated. As shown in Fig.~\ref{tu2}(d), the band gap is 3.13 eV for the spin-up channel and 1.27 eV for the spin-down channel, respectively. This significant difference between the two band gaps indicates that the FM monolayer NiI$_{2}$ is a half-semiconductor~\cite{AN2022115262,dong2022quantum}, which has great potential for spintronic applications~\cite{35}. The conduction band minimum (CBM) is composed of spin-down states only, while the valence band maximum (VBM) is composed of spin-up states, leading to an overall band gap of 1.05 eV in the FM monolayer NiI$_{2}$. However, the band gap in the FM state with SOC decreases to 0.73 eV. We further use a 4$\times$8$\times$1 supercell to calculate the HM state with $\boldsymbol{Q}_{1}$ = (0.25, -0.125, 0), with the bands unfolded to the Brillouin zone of a primitive cell~\cite{PhysRevLett.104.216401}. As shown in  Fig.~\ref{tu2}(e), without SOC, the monolayer NiI$_{2}$ with the HM state is calculated to have a 1.23 eV indirect band gap near the $\Gamma$ point. When SOC is considered, the  CBM moves downward, leading to a slightly smaller gap (Fig.~\ref{tu2}(f)). This overall semiconducting nature of the HM state provides a prerequisite for the appearance of spontaneous electric polarization in the monolayer NiI$_{2}$.

\subsection{Strain engineered monolayer NiI$_{2}$}

We firstly investigate the case of applying uniform biaxial strain, i.e., the same strain on both the $a$-axis and $b$-aixs, to gain an insight about how strain generally affect the atomic structure and exchange interactions, hence the magnetic ordering. In this case, the original lattice symmetry is preserved. With the strain changed from -8\% to 8 \%, the bond lengths of $J_{1}$, $J_{2}$ and $J_{3}$ extend from 3.66 \AA\ to 4.30 \AA,  6.34 \AA\ to 7.44 \AA, 7.32 \AA\ to 8.59 \AA\ , respectively. Fig.~\ref{tu3}(a) shows the evolvement of the magnetic exchange interactions with the strain level $x$. It can be seen that $J_{1}$ keeps ferromagnetic, showing only slight variations. In contrast, although the $J_{3}$ remains antiferromagnetic, it decreases dramatically and monotonously with the increase of $x$, exhibiting much more tunability. Meanwhile, $J_{2}$ remains negligiblly close to 0 throughout the whole range of $x$, therefore Eq. (\ref{eq:6}) can be simplified as
 \begin{equation}
\begin{aligned}
\frac{J_1}{J_3} > -4
\end{aligned}\label{eq:7}
\end{equation}
Our calculated ratio of $J_{1}$ and $J_{3}$ ranges from -2.25 to -0.24, satisfying Eq. (\ref{eq:7}), therefore suggests that the ground states remain HM under these strains.

To further explore the impact of different kind of strains on magnetic interactions, we now consider the case of uniaxial strains, i.e., zero strain on the $a$-axis combined with varying strain levels $y$ on the $b$-axis. The $J_{1}$, $J_{2}$ and $J_{3}$ now split into  $J_{1a-1c}$ , $J_{2a-2c}$ and $J_{3a-3c}$ respectively, due to a reduced lattice symmetry. In Fig.~\ref{tu3}(b), it can be seen that $J_{1a-1c}$ and $J_{2a-2c}$ are overall not senstitive to the strains, similar to the behavior of their counterparts in the uniform strain case.  Exceptionally, $J_{3a-3c}$ behave differently among each other, with the $J_{3a}$ showing signicantly higher tunability, inheriting the characteristic of $J_3$. Particularly, under maximum tensile strain with $y = -8 \%$, although only small variation in the $J_{3a-3c}$ bond length is induced, $J_{3a}$ becomes over 4 times larger than $J_{3b}$ (see Fig.~\ref{tu3}(b)).

\begin{figure}[t]
	\includegraphics[scale=0.5]{chutu_5.pdf}
	\caption{ (a) Band gap of the FM NiI$_{2}$ monolayer as a function of lattice constants $a$ and $b$, where the dark spots represent sampled strain points. (b) The polarization of monolayer NiI$_{2}$ in proper-screw HM states as a function of lattice constants $a$ and $b$, where the the dark stars are data points form the supercell calculation.}
	\label{tu5}
\end{figure}

We now turn to arbitrary strains with unequal $x$ and $y$ ( -8\% $\leq$ $x$, $y$ $\leq$ 8\% ). We find that in all scenarios, the calculated $J's$ behave similarly as been shown in Fig.~\ref{tu3}(a)-(b), with only $J_3$ varies significantly with $x$ and $y$. Importantly, the magnetic ground states are all predicted to be HM according to the Eq. (\ref{eq:7}). With the calculated $J'$s, we further perform MC simulations for all sampled strains, with calculated $T_{N}$ shown in Fig.~\ref{tu4}(a). The corresponding color map is plotted to be symmetrical with respect to the diagonal line since the $a$-axis and $b$-axis are equivalent. Notably, the $T_{N}$ exhibits dramatic variations, dropping with the increasing of tensile strains, down to 10.45 K at $x=8\%$ and $y=8\%$. Surprisingly, the $T_{N}$ rises to 101.17 K with the $x=-8 \%$\ and $y = 6\%$, which is the highest among all our sampled cases, almost 5 times higher than that of the strain-free one. By examining the corresponding $J'$s, we find that the $T_{N}$ largely evolves following the trend of the $J_{3}$, and in the case of lowered symmetry, $J_{3a}$, which is the exchange interaction with the highest tunability (see Fig.~\ref{tu3}(a)-(b) and Table.~\ref{tab1-1} for typical strain cases). We then further identify the HM propogation vectors $\boldsymbol{Q}$ from the outputed spin configurations of MC simulations, with $q_a$ and $q_b$ shown in Fig.~\ref{tu4}(b)-\ref{tu4}(c) respectively. It can be seen that the amplitude of $q_a$ are enlarged with the increasing tensile strains, while the $q_b$ increases with the compressive strains (the diagonal lines of the color maps).

\begin{figure}[t]
	\includegraphics[scale=0.45]{chutu_6.pdf}
	\caption{ (a)-(b) The top and side view of  4 $\times$ 2 $\times$ 1 NiI$_{2}$ (monolayer)/ 7 $\times$ 3 $\times$ 1 graphene (bilayer) heterostructures.}
	\label{tu6}
\end{figure}

\begin{table*}[t!]
	\caption{ \label{tab2} Values (in meV) of magnetic exchange couplings and $T_{N}$ by DFT calculation and MC simulations.The freestanding monolayer NiI$_{2}$ is under $x$ = -7\% and $y$ = 8\% strain, where the NiI$_{2}$ layer in NiI$_{2}$/BLG heterostructure is taking similar compressive and tensile strains. }
	\begin{ruledtabular}
		\begin{tabular}{cccccccccccc}
			&  & $ J_{1a}$ & $ J_{1b}$ & $ J_{1c}$ & $ J_{2a}$  & $ J_{2b}$ & $ J_{2c}$ & $ J_{3a}$ & $ J_{3b}$ & $ J_3c$ & $T_{N}$(K) \\
			\hline  \\[-1.0ex]
			& NiI$_{2}$ monolayer & -2.98 & -4.18  & -4.58 & 0.08 & -0.15 & -0.20 & 12.38 & 2.49 & 1.02 & 71.07  \\
			& NiI$_{2}$/BLG heterostructure & -3.50 & -4.27  & -4.51 & 0.22 & -0.09 & -0.37 & 12.06 & 2.81 & 1.22 & 70.73  \\
		\end{tabular}
	\end{ruledtabular}
\end{table*}

Once the $\boldsymbol{Q}$ values are confirmed, we construct supercells to accommodate corresponding proper-screw spiral states to study their ferroelectricity. Since the supercell calculations are expensive, to reduce computational effort, we only perform supercell calculations on selected representative strain values, shown as stars in Fig.~\ref{tu5}(b). We find that all the selected HM states have larger band gaps than that of the corresponding FM states. Therefore, to have a full sampling, band gaps of FM states with all strains are calculated and shown as a color map in Fig.~\ref{tu5}(a). It can be seen that in all cases, the band gaps are finite, ranging from 0.30 eV to 1.36 eV, which increase with tensile strains and reduce with compressive strains, consistent with the general text-book physical picture. These band gaps guarantee that the HM ground states under the whole strain range are possible to sustain spontaneous electric polarizations. The electric polarziations $\boldsymbol{P}$ are then calculated, with their amplitude $|\boldsymbol{P}|$ interpolated to a diagram in the strain map. As can be seen in Fig.~\ref{tu5}(b), $|\boldsymbol{P}|$ keeps the same order in the whole strain range, with their behavior closely resembling that of the band gaps, but in an opposite way, which is quite evident from the comparison of Fig.~\ref{tu5}(a) and Fig.~\ref{tu5}(b). Therefore, the main driving force for the enhancement of  $|\boldsymbol{P}|$ is the corresponding shrinking of the bang gap, although with compressive strains, the surface of the monolayer NiI$_{2}$ also contracts. For instance, with the maximum compressive strain $x = -8 \%$ and $y = -8 \%$, the surface area of the monolayer NiI$_{2}$ is reduced by 15 \%, but $|\boldsymbol{P}|$ becomes more than two times larger than that of the strain-free case.

To check the reliability of applying strain by solely changing the lattice constants, we construct a NiI$_{2}$/graphene heterostructure to simulate practical exitaxial strain engineering through substate.  Bilayer graphene (BLG) has been successfully used as substrates to grow 2D magnetic materials, such as monolayer CrTe$_{2}$~\cite{41}. As shown in Fig.~\ref{tu6}(a), the constructed NiI$_{2}$/BLG heterostructure is composed of a 4 $\times$ 2 $\times$ 1 supercell of NiI$_{2}$ and a 7 $\times$ 3 $\times$ 1 supercell of BLG. By fixing the lattice constants of the BLG, 7.24\% compressive strain ($x=-7.24\%$) and 8.22\% tensile strain ($y=8.22\%$) are applied on the $a$-axis and $b$-axis of monolayer NiI$_{2}$ , respectively. The calculated magnetic exchange interactions $J$$_{1a-1c}$ , $J$$_{2a-2c}$ and $J$$_{3a-3c}$ in this heterostructure are shown in Table.~\ref{tab2}, resulting in a HM ground state with a $T$$_{N}$ = 71.07 K. In comparison, as shown in Fig.~\ref{tu4}(a), our calculations of freestanding monolayer NiI$_{2}$ with strain values of $x = -7\%$ and $y = 8\%$ produces a $T$$_{N}$ = 70.73 K (Table.~\ref{tab2}), with the corresponding $J$ values very close to that from the heterostructures. This excellent agreement validates the high reliablity of our predictions based on freestanding calculations.

\section{Summary}
In summary, we study the multiferroic order of freestanding monolayer NiI$_{2}$ with engineered levels of strain using DFT calculations and MC simulations. Through the investigation of strain-free monolayer NiI$_{2}$, we find that the first NN and third NN exchange interactions play an essential role in the formation of its magnetic phase diagrams. The competition of these interactions induces magnetic frustration, leading to the formation of proper-screw HM ground state. We further show that these conclusions drawing from the strain-free monolayer can be well generalized to the cases within our engineered range of strains. Notably, our calculations show that with 6\% tensile strain on the $a$-axis and 8\% compressive strain on the $b$-axis, the N\'{e}el temperature $T_N$ can be significantly enhanced to 101 K, about 5 times larger than that of the strain-free one. The strength of spontaneous electric polarizations can also be more than doubled under 8\% uniform compressive strain on both axises. Moreover, we construct a NiI$_{2}$ (monolayer)/Graphene (bilayer) heterostructure to simulate a more realistic strain engineering and obtain results in good agreement with that based on calculations on corresponding freestanding one. Our work suggests that strain is a promising way to tune multiferroic orders in the monolayer NiI$_{2}$, with the potential to signicanlty promote its transition temperatures and electric polarizations, therefore broaden the prospect of its applications in spintronics devices.

\section{acknowledgments}

Work at Sun Yat-Sen University was supported by the National Key Research and Development Program of China (Grants No. 2018YFA0306001, 2017YFA0206203), and the Guangdong Basic and Applied Basic Research Foundation (Grants No. 2022A1515011618, No. 2019A1515011337), and the National Natural Science Foundation of China (Grants No. 92165204, No. 11974432), and the Shenzhen International Quantum Academy (Grant No. SIQA202102), Leading Talent Program of Guangdong Special Projects (201626003).