# On graphs with well-distributed edge density

Syed Mujtaba<EMAIL_ADDRESS>Computer Science Department,
Habib University, Karachi, Pakistan (corresponding author) Shahid
<EMAIL_ADDRESS>Computer Science Department, Institute of
Business Administration, Karachi, Pakistan

(March 21, 2024)

###### Abstract

In this paper, we introduce a class of graphs which we call _average
hereditary graphs_. Most graphs that occur in the usual graph theory
applications belong to this class of graphs. Many popular types of graphs fall
under this class, such as regular graphs, trees and other popular classes of
graphs. We prove a new upper bound for the chromatic number of a graph in
terms of its maximum average degree and show that this bound is an improvement
on previous bounds. From this, we show a relationship between the average
degree and the chromatic number of an average hereditary graph. This class of
graphs is explored further by proving some interesting properties regarding
the class of _average hereditary graphs_. An equivalent condition is provided
for a graph to be average hereditary, through which we show that we can decide
if a given graph is average hereditary in polynomial time. We then provide a
construction for average hereditary graphs, using which an average hereditary
graph can be recursively constructed. We also show that this class of graphs
is closed under a binary operation, from this another construction is obtained
for average hereditary graphs, and we see some interesting algebraic
properties this class of graphs has. We then explore the effect on the
complexity of graph 3-coloring problem when the input is restricted to
_average hereditary graphs_.

Keywords: Graph theory, graph coloring, NP-Hard graph problem, graph average
degree

##  1 Introduction

We introduce a new class of graphs that we call average hereditary graphs.
There are many interesting properties regarding this class of graphs. In this
paper, we explore a few of those properties. We provide a new upper bound for
the chromatic number of a graph in terms of its maximum average degree, that
is $\chi(G)\leq\text{{MAD}}(G)+1$, we then show that this new bound is an
improvement on previous results. We use this bound to find a relationship
between the average degree of a graph and its chromatic number, from this, we
prove a general case for which we know the exact chromatic number of an
average hereditary graph. What’s interesting is that the class of average
hereditary graphs is quite broad as it contains many popular classes of
graphs, furthermore, most graphs that occur in graph theory applications
belong to the class of average hereditary graphs. So the class only restricts
some extreme cases. We will analyze the computational complexity of deciding
if a graph is average hereditary, and show that we can compute if a graph is
average hereditary in polynomial time. This is done by providing an equivalent
condition for a graph to be average hereditary.

We will then give a construction of average hereditary graphs and show that
the class is closed under the graph join operation. Our construction gives us
an algorithm to recursively construct average hereditary graphs. The closure
under the binary operation also provides a method to construct average
hereditary graphs. Furthermore, this also tells us about some interesting
algebraic properties the class of average hereditary graphs has, such as the
set of all average hereditary graphs is a commutative monoid. We then show
that the graph 3-coloring problem remains NP-hard when the input is restricted
to average hereditary graphs.

The main result of our paper is the new general case upper bound on the
chromatic number of graphs which is an improvement on previous bounds found in
literature.

###  1.1 Preliminaries

Throughout this document, we will denote a graph as $G=(V,E)$ where $G$ is a
graph with vertex set $V$ and edge set $E$. An edge is represented as a set
$\\{v,u\\}$ for some $v$ and $u$ belonging to $V$ such that $v\neq u$. Also,
for a graph $G$ we use $V(G)$ to denote the vertex set of $G$ and $E(G)$ to
denote the edge set of $G$. All graphs considered here are undirected and
simple meaning they contain no loops, multi-edges or directed edges. We will
use $H\subseteq G$ to denote an induced subgraph of $G$. For some $U\subseteq
V$, $G-U$ denotes the subgraph of $G$ obtained by removing the vertices in
$U$. For $H\subseteq G$, $\overline{H}$ denote the graph $G-V(H)$. For each
vertex $v\in V$ we used $d_{G}(v)$ to denote the degree of $v$ in $G$. We also
use $\Delta(G)$ to denote the maximum degree of $G$ and $\delta(G)$ to denote
the minimum degree of $G$. The average degree of $G$, denoted by $d(G)$ is the
average of all the degrees of $G$, which can be computed by
$d(G)=\frac{\sum_{v\in V}d_{G}(v)}{|V|}=\frac{2|E|}{|V|}$ if $V$ is nonempty.
For a null graph, we define the average degree as 0. If the degrees of all the
vertices of a graph $G$ are equal to $k$, we say $G$ is $k$-regular.

The edge cut $[V(H),\overline{V(H)}]$ is the smallest set of edges you need to
remove from $G$ to break $G$ into two components $H$ and $\overline{H}$, for
$H\subseteq G$. The edge connectivity is the size of the smallest cut edge,
denoted by $\kappa^{\prime}(G)$. If a graph $G^{\prime}$ is constructed by
adding a vertex $x$ to $G$ and connecting $x$ to some $v\in V$ and all the
neighbors of $v$, we say $G^{\prime}$ is obtained from $G$ by expanding $v$ to
an edge $\\{v,x\\}$. We denote this as $G^{\prime}=G\text{exp}(v,x)$. The join
of two graphs $G$ and $H$ is a graph $K$ such that $K$ contains all the edges
and vertices of $G$ and $H$ and in $K$, each vertex in $G$ is connected to
every vertex in $H$. We denote this as $K=G\land H$. The clique size is the
size of the largest complete subgraph of $G$, we denote it by $\omega(G)$.

Coloring a graph $G$ is assigning a color to each vertex of $G$ such that if
two vertices are adjacent then they are assigned a different color than each
other. The smallest natural number $k$ such that $G$ can be colored with $k$
colors is known as the chromatic number of $G$. We denote the chromatic number
of $G$ by $\chi(G)$. If $k=\chi(G)$ then we say $G$ is $k$-chromatic. $G$ is
called $k$-critical if $\chi(G)=k$ and $\forall v\in V,\;\chi(G-v)<k$.
$\mathbb{N}$ denotes the set of natural numbers which includes $0$.

###  1.2 Average Hereditary Graphs

We now define our new class of graph that we call average hereditary graphs,
we then show how broad this class of graph is, in other words, we show that
this class of graph is a superset of many other popular classes of graphs.

We define a new class of graphs called average hereditary graphs. A graph
$G=(V,E)$ is _average hereditary_ if for every induced subgraph $H$ of $G$,
$d(H)\leq d(G)$. Note that this definition is equivalent to saying that for
every subgraph $H$ of $G$ (not necessarily induced), $d(H)\leq d(G)$. As if
$d(H)\leq d(G)$ for all $H\subseteq G$ then we have that $d(H^{\prime})\leq
d(G)$ for all induced subgraphs $H^{\prime}$ of $G$ and conversely if
$d(G^{\prime})\leq d(G)$ for all induced subgraphs $G^{\prime}$ of $G$ then as
for every subgraph $H$ of $G$ there exists an induced subgraph $H^{\prime}$ of
$G$ such that $V(H)=V(H^{\prime})$ and $d(H)\leq d(H^{\prime})$.

One way to think about such graphs is that the edge density is more
“uniformly” distributed over the graph. Most graphs that occur in usual graph
theory applications or other areas belong to this class and the class only
restricts some extreme cases. Most graphs we see are average hereditary. Many
popular classes of graphs belong to this class of graphs. For example, all
regular graphs and all trees are average hereditary. The following
propositions prove these claims.

######  Proposition 1.

If $G$ is a tree then $G$ is average hereditary.

###### Proof.

Let $G=(V,E)$ be a tree so we have that $|E|=|V|-1$. Therefore
$d(G)=\frac{2|E|}{|V|}=\frac{2(|V|-1)}{|V|}=2-\frac{2}{|V|}$. Now if we induce
a subgraph $H$ from $G$ then we can have two cases. First, if $H$ is empty
then $d(H)\leq d(G)$. If $H$ is nonempty then we have that $H$ is a forest. So
we have that $|E(H)|\leq|V(H)|-1$, therefore $d(H)\leq 2-\frac{2}{|V(H)|}$ and
as both $V$ and $V(H)$ are finite, we have that $d(H)\leq d(G)$. ∎

######  Proposition 2.

If $G$ is a $k$-regular graph then $G$ is average hereditary.

###### Proof.

Let $G=(V,E)$ be a $k$-regular graph. So $d(G)=k$. Now if we remove any set of
vertices from $G$ to induce a subgraph $H$ then every vertex in $H$ will have
a degree of at most $k$. So the average degree of $H$ is at most $k$.
Therefore $G$ will be average hereditary.

∎

These propositions show that many popular types of graphs such as cycle,
paths, star, claws, complete graphs, and Peterson graph, are all average
hereditary, as we have that regular graphs and trees are average hereditary in
general. Figure 1 shows some examples of average hereditary graphs.

Figure 1: Example of average hereditary graphs

Some non-example of average hereditary graphs would be $K_{7}\cup K_{3}$ or if
we connect $P_{100}$ to a vertex of $K_{5}$. So these non-examples are graphs
which has one region with a much higher edge density and one region with a
much lower edge density. But these examples are much rarer, so the class of
average hereditary graphs is much broader as the class is a superset of many
popular classes of graphs. Figure 2 shows a non-example of average hereditary
graphs.

$P_{100}$ Figure 2: Example of Non-average hereditary graphs

We can see that these average hereditary graphs are graphs which has more
“well” distributed edge density. So we don’t have that one region has a much
higher edge density while another has a much lower edge density than that, as,
if that were the case then removing the region with much lower edge density
would give us a subgraph that has a higher average degree than the original
graph. Now we explore some interesting properties regarding average hereditary
graphs.

##  2 Computing Average Hereditary Property

From the definition computing the average hereditary property seems quite a
difficult task itself. It is of interest to us to find a polynomial time
computable equivalent condition for a graph to be average hereditary. Our next
proposition gives that condition. The notion of maximum average degree has
been an active area of research in graph theory. For a graph $G$, if $H$ is a
subgraph of $G$ such that for all subgraphs $G^{\prime}$ of $G$, the average
degree of $G^{\prime}$ is less than or equal to the average degree of $H$. For
$G$ we denote $\text{{MAD}}(G)$ as the average degree $H$. In other words for
a graph $G$, $\text{{MAD}}(G)$ is the average degree of the densest subgraph
of $G$. The next proposition gives us a relation between $\text{{MAD}}(G)$ and
$d(G)$ for an average hereditary graph.

######  Proposition 3.

A graph $G$ is average hereditary if and only if $d(G)=\text{{MAD}}(G)$.

###### Proof.

Let $G=(V,E)$ be a graph, we know that $\text{{MAD}}(G)\geq d(G)$. Now suppose
$G$ is average hereditary then from the definition $d(H)\leq d(G)$ for all
subgraphs $H$ of $G$. Then if $\text{{MAD}}(G)>d(G)$ we would have that there
exists some subgraph $H$ of $G$ such that $d(H)>d(G)$ which is a
contradiction, therefore $d(G)=\text{{MAD}}(G)$. Conversely, suppose that
$\text{{MAD}}(G)=d(G)$ then from the definition of maximum average degree,
$d(H)\leq\text{{MAD}}(G)=d(G)$ for all subgraphs $H$ of $G$, therefore $G$ is
average hereditary. ∎

In his 1984 paper Goldberg showed that $\text{{MAD}}(G)$ can be computed in
polynomial time [9]. Goldberg reduced computing $\text{{MAD}}(G)$ to a bunch
of network flow problems giving an algorithm that runs in
$O(M(|V|,7+|E|)\log|V|)$ time where $M(n,m)$ is the time required to find the
minimum capacity cut in a network with $n$ vertices and $m$ edges [9]. The
Max-flow min-cut theorem states that the minimum capacity of the cut in a
network is equal to the maximum flow in a network [5, 14, 8, 4]. Now through
this, we have several polynomial time algorithms to find the minimum capacity
cut in a network such as Ford-Fulkerson algorithm [8], Edmonds-Karp algorithm
[7], Dinitz’s algorithm [6], Goldberg-Tarjan algorithm [10] and many others.
Furthermore, as the average degree of any graph can be computed in polynomial
time we can use Goldberg’s algorithm to compute if a given graph is average
hereditary in polynomial time.

##  3 Bound on Chromatic number

Graph coloring is famously NP-complete. Chromatic coloring is the optimization
version of the Graph coloring problem. Chromatic coloring concerns with
computing the chromatic number of a given graph. Unlike the usual graph
coloring problem, which isn’t specifically concerns with the chromatic number
of the graph, the chromatic coloring problem isn’t even known to be in NP.
Chromatic coloring is itself NP-hard, which means no polynomial time algorithm
exists for it unless $\text{{{P}}}=\text{{{NP}}}$. However many upper bounds
exist for the chromatic number of a graph, aiming to reduce the complexity of
the existing coloring algorithms. We introduce a new upper bound for the
chromatic number of a graph in terms of the maximum average degree of the
graph, that is $\chi(G)\leq\text{{MAD}}(G)+1$. As a corollary of this, we
obtain a relationship between the average degree and the chromatic number of
an average hereditary graph. We compare our new upper bound on the chromatic
number with previous bounds found in the literature and show that our bound is
tighter than the previous bounds. To prove this bound we use two Lemmas found
in literature.

######  Lemma 1 ([14]).

Every $k$-chromatic graph has a $k$-critical induced subgraph.

######  Lemma 2 ([14]).

For a critical graph $G$, $\chi(G)-1\leq\delta(G)$.

######  Theorem 1.

For a graph $G$, $\chi(G)\leq\text{{MAD}}(G)+1$.

###### Proof.

Let $G=(V,E)$ be a graph. Let $H\subseteq G$ be a critical induced subgraph of
$G$, then $\chi(H)=\chi(G)$. As $\chi(G)-1\leq\delta(H)$, then we have that
$\chi(G)\leq\delta(H)+1$. So we have that $\chi(G)\leq\delta(H)+1\leq
d(H)+1\leq\text{{MAD}}(G)+1$. Therefore $\chi(G)\leq\text{{MAD}}(G)+1$. ∎

######  Corollary 1.

If $G$ is an average hereditary graph then $\chi(G)\leq d(G)+1$.

###### Proof.

Let $G=(V,E)$ be an average hereditary graph. Then from Proposition 3 we have
that $d(G)=\text{{MAD}}(G)$, and so $\chi(G)\leq\text{{MAD}}(G)+1$ implies
$\chi(G)\leq d(G)+1$. ∎

It is to note that as $\chi(G)\in\mathbb{N}$, $\chi(G)\leq\text{{MAD}}(G)+1$
implies $\chi(G)\leq\lfloor\text{{MAD}}(G)+1\rfloor$ and likewise $\chi(G)\leq
d(G)+1$ implies $\chi(G)\leq\lfloor d(G)+1\rfloor$. The following corollary
uses this to show a case where we know the exact chromatic number of an
average hereditary graph.

######  Corollary 2.

If $G$ is an average hereditary graph and
$\left\lceil\frac{|V|}{|V|-d(G)}\right\rceil=\lfloor d(G)+1\rfloor$, then
$\chi(G)=\omega(G)=\lfloor d(G)+1\rfloor$.

###### Proof.

Let $G=(V,E)$ be an average hereditary graph. From [12] we know that
$\chi(G)\geq\omega(G)\geq\frac{|V|^{2}}{|V|^{2}-2|E|}=\frac{|V|}{|V|-d(G)}$.

From Corollary 1 we have that $\chi(G)\leq d(G)+1$. As
$\chi(G),\omega(G)\in\mathbb{N}$, then $\chi(G)\leq d(G)+1$ implies
$\chi(G)\leq\lfloor d(G)+1\rfloor$ and
$\chi(G)\geq\omega(G)\geq\frac{|V|}{|V|-d(G)}$ implies
$\chi(G)\geq\omega(G)\geq\left\lceil\frac{|V|}{|V|-d(G)}\right\rceil$. So

$\left\lceil\frac{|V|}{|V|-d(G)}\right\rceil\leq\omega(G)\leq\chi(G)\leq\lfloor
d(G)+1\rfloor$

Therefore if $\left\lceil\frac{|V|}{|V|-d(G)}\right\rceil=\lfloor
d(G)+1\rfloor$, then
$\chi(G)=\omega(G)=\left\lceil\frac{|V|}{|V|-d(G)}\right\rceil=\lfloor
d(G)+1\rfloor$. ∎

We now show that our new bound of $\chi(G)\leq\text{{MAD}}(G)+1$ is an
improvement on previous bounds, that is to say, that in most cases our bound
will be tighter than previous bounds found in the literature. We compare our
bound with three previous bounds found in the literature showing that our
bound is in improvement.

It is well known that in general $\chi(G)\leq\Delta(G)+1$. We compare our
bound with this general case bound and show that our bound is an improvement.

######  Proposition 4.

$\lfloor\text{{MAD}}(G)+1\rfloor\leq\Delta(G)+1$

###### Proof.

For a graph $G=(V,E)$ the maximum average degree $\text{{MAD}}(G)$ is less
than or equal to the maximum degree $\Delta(G)$. So

$\text{{MAD}}(G)\leq\Delta(G)\implies\text{{MAD}}(G)+1\leq\Delta(G)+1\implies\lfloor\text{{MAD}}(G)+1\rfloor\leq\Delta(G)+1.$

∎

Therefore this new bound is an improvement on the general case bound of
$\chi(G)\leq\Delta(G)+1$.

Now we compare it to the special case bound given by Brooks in 1941. Brooks
showed that $\chi(G)\leq\Delta(G)$ if $G$ is neither complete nor an odd cycle
[3]. We show that our bound is an improvement on Brooks’s bound when $G$ is
not regular.

######  Proposition 5.

$\lfloor\text{{MAD}}(G)+1\rfloor\leq\Delta(G)$ if not all connected component
of $G$ containing a subgraph of maximum average degree are regular.

###### Proof.

Let $G=(V,E)$ be a graph such that there is some non-regular connected
component of $G$ containing a subgraph of maximum average degree. Let $M$ be
the subgraph of $G$ with the maximum average degree so $\text{{MAD}}(G)=d(M)$
and Let $H$ be the connected component of $G$ containing $M$. Without loss of
generality suppose that there is a unique component $H$ of $G$ such that $H$
contains a graph with the maximum average degree, else if there are multiple
such components of $G$ then we choose the component with the greatest maximum
degree and obtain a graph $G^{\prime}$ by deleting all other such components
of $G$, this way $\Delta(G^{\prime})=\Delta(G)$ and
$\text{{MAD}}(G^{\prime})=\text{{MAD}}(G)$.

We have that $\text{{MAD}}(G)\leq\Delta(G)$, now suppose
$\text{{MAD}}(G)=\Delta(G)$. We know that $d(M)\leq\Delta(H)\leq\Delta(G)$. So
$\text{{MAD}}(G)=\Delta(G)$ implies $\text{{MAD}}(G)=\Delta(H)$. Now if
$\text{{MAD}}(G)=\Delta(H)$, then as $\text{{MAD}}(G)\leq\Delta(M)$, we have
that $d(M)=\text{{MAD}}(G)=\Delta(M)=\Delta(H)$, so all the vertices in $M$
have the same degree in $M$ therefore $M$ would be regular. Now suppose that
$U=H-M\neq\emptyset$, then as $H$ is connected $[M,U]$ is nonempty. Then there
is at least one vertex in $M$ that has one of its incident edges in $[M,U]$,
but as we have that all vertices in $M$ have degree equal to $\Delta(H)$ in
$M$ then $\text{{MAD}}(G)<\Delta(H)$ which is a contradiction. So we have that
$U=H-M=\emptyset$. Therefore $H$ is regular, which is a contradiction as the
connected component of $G$ containing $M$ is not regular, therefore
$\text{{MAD}}(G)<\Delta(G)$. As $\Delta(G)\in\mathbb{N}$, then
$\lfloor\text{{MAD}}(G)\rfloor<\Delta(G)$. As
$\lfloor\text{{MAD}}(G)\rfloor\in\mathbb{N}$,
$\lfloor\text{{MAD}}(G)\rfloor<\Delta(G)\implies\lfloor\text{{MAD}}(G)\rfloor+1\leq\Delta(G)$.
∎

Therefore when not all connected components of $G$ containing a subgraph of
maximum average degree are regular our bound is an improvement on the bound
given by Brooks.

María Soto, André Rossi and Marc Sevaux showed that
$\chi(G)\leq\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor$ if $G$
is simple and connected [13]. They compared their bounds with some previous
bounds found in literature and showed that it was an improvement on those
bounds [13]. We now compare our bound with this bound and show that our bound
is an improvement on their bound as well. We first prove a lemma which we will
use to prove that our bound is an improvement on the bound by María Soto,
André Rossi and Marc Sevaux.

######  Lemma 3.

For a simple and connected graph $G$, $\lfloor
d(G)+1\rfloor\leq\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor$.

###### Proof.

Let $G=(V,E)$ be a simple and connected graph, then
$|V|-1\leq|E|\leq\frac{|V|(|V|-1)}{2}$. If $|V|=0$ or $|V|=1$ then $d(G)=0$ so
this is trivial case. Now we consider when $|V|>1$. We first show that
$d(G)+1=\frac{2|E|}{|V|}+1\leq\frac{3+\sqrt{9+8(|E|-|V|)}}{2}$

We show that the inequality holds for $|V|\leq|E|\leq\frac{|V|(|V|-1)}{2}$. We
will then show for $|E|=|V|-1$; $\lfloor
d(G)+1\rfloor=\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor=2$
where $|V|\geq 2$.

$\frac{2|E|}{|V|}+1\leq\frac{3+\sqrt{9+8(|E|-|V|)}}{2}$
$2|E|^{2}-(|V|+|V|^{2})|E|+(|V|^{3}-|V|^{2})\leq 0$

$\iff\frac{|V|+|V|^{2}-|V|\sqrt{9-6|V|+|V|^{2}}}{4}\leq|E|\leq\frac{|V|+|V|^{2}+|V|\sqrt{9-6|V|+|V|^{2}}}{4}$

We have that $|V|\leq|E|\leq\frac{|V|(|V|-1)}{2}$, so first we show that
$\frac{|V|(|V|-1)}{2}\leq\frac{|V|+|V|^{2}+|V|\sqrt{9-6|V|+|V|^{2}}}{4}$

$\frac{|V|(|V|-1)}{2}\leq\frac{|V|+|V|^{2}+|V|\sqrt{9-6|V|+|V|^{2}}}{4}\iff
9-6|V|+|V|^{2}\leq 9-6|V|+|V|^{2}\iff 0\leq 0$

Now we show that $\frac{|V|+|V|^{2}-|V|\sqrt{9-6|V|+|V|^{2}}}{4}\leq|V|$

$\frac{|V|+|V|^{2}-|V|\sqrt{9-6|V|+|V|^{2}}}{4}\leq|V|\iff 9-6|V|+|V|^{2}\leq
9-6|V|+|V|^{2}\iff 0\leq 0$

So we have that for $|V|\leq|E|\leq\frac{|V|(|V|-1)}{2}$,
$d(G)+1=\frac{2|E|}{|V|}+1\leq\frac{3+\sqrt{9+8(|E|-|V|)}}{2}$.

Now we will then show for $|E|=|V|-1$, $\lfloor
d(G)+1\rfloor=\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor=2$.

For $|E|=|V|-1$,
$\frac{3+\sqrt{9+8(|E|-|V|)}}{2}=\frac{3+\sqrt{9+8(|V|-1-|V|)}}{2}=2$ and
$|E|=|V|-1$, $\lfloor
d(G)+1\rfloor=\lfloor\frac{2|E|}{|V|}\rfloor+1=\lfloor\frac{2|V|-2}{|V|}\rfloor+1$.
as $|V|\in\mathbb{Z}^{+}$ and $|V|$ is finite and $|V|\geq 2$ then
$\lfloor\frac{2|V|-2}{|V|}\rfloor=1$ so $\lfloor d(G)+1\rfloor=2$.

Therefore for $|V|-1\leq|E|\leq\frac{|V|(|V|-1)}{2}$, $\lfloor
d(G)+1\rfloor\leq\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor$.

∎

######  Proposition 6.

$\lfloor\text{{MAD}}(G)+1\rfloor\leq\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor$
if $G$ is simple and connected.

###### Proof.

Let $G=(V,E)$ be a simple and connected graph, and let $M$ be the subgraph of
$G$ with the maximum average degree. We first show that following inequality
holds:

$\left\lfloor\frac{3+\sqrt{9+8(|E(M)|-|V(M)|)}}{2}\right\rfloor\leq\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor.$
(1)

We first prove this by showing that this inequality holds even when we remove
the floor functions. That is,

$\frac{3+\sqrt{9+8(|E(M)|-|V(M)|)}}{2}\leq\frac{3+\sqrt{9+8(|E|-|V|)}}{2}.$
(2)

From (2) we have that, $|E(M)|-|V(M)|\leq|E|-|V|$ that is
$|V|-|V(M)|\leq|E|-|E(M)|$. Let $H=G-M$ then $|V|-|V(M)|=|V(H)|$ and
$|E|-|E(M)|=|E(H)|+|[H,M]|$. Now if $M=G$ then $|V|-|V(M)|=|E|-|E(M)|=0$. Now
if $M\neq G$, so $|V(H)|>0$ and $|E(H)|+|[H,M]|>0$. Then (2) gives
$|V(H)|\leq|E(H)|+|[H,M]|$. Let $S$ be the union of all single vertex
components of $H$, and let $U=H-S$ so $|V(H)|=|V(U)|+|V(S)|$ and
$|E(H)|+|[H,M]|=|E(U)|+|[U,M\cup S]|+|[S,M\cup U]|$. As $S$ is the union of
single vertex components of $H$ and $G$ is connected we have that
$|V(S)|=|[S,M\cup U]|$. So from (2) we get
$|V(H)|\leq|E(H)|+|[H,M]|\iff|V(U)|\leq|E(U)|+|[U,M]|$.

Now suppose that $|V(U)|>|E(U)|+|[U,M]|$. First, as $G$ is connected and $U$
contains no single vertex components then $E(U)\geq|V(U)|-1$. Next as $G$ is
connected $|[U,M]|\geq 1$, so $|V(U)|>|E(U)|+|[U,M]|\implies|V(U)|>|E(U)|+1$
which is equivalent to $|V(U)|-1>|E(U)|$ which is a contradiction. So we have
that $|V(U)|\leq|E(U)|+|[U,M]|$ and therefore (2) holds which implies (1).

Now from Lemma 3 we have that $\lfloor
d(M)+1\rfloor\leq\left\lfloor\frac{3+\sqrt{9+8(|E(M)|-|V(M)|)}}{2}\right\rfloor$,
and as $d(M)=\text{{MAD}}(G)$ we have that
$\lfloor\text{{MAD}}(G)+1\rfloor\leq\left\lfloor\frac{3+\sqrt{9+8(|E(M)|-|V(M)|)}}{2}\right\rfloor\leq\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor$.
∎

Therefore our new bound of $\lfloor\text{{MAD}}(G)+1\rfloor$ is an improvement
on the special case bound of
$\chi(G)\leq\left\lfloor\frac{3+\sqrt{9+8(|E|-|V|)}}{2}\right\rfloor$ if $G$
is simple and connected.

So we have a new bound on the chromatic number of a graph which we showed is
an improvement on previous bounds. The bound is also computable in polynomial
time as $\text{{MAD}}(G)$ can be computed in polynomial time as discussed in
section 2. The bound is also often very close to the actual value of the
chromatic number. Through this bound we found a relationship between the
chromatic number and the average degree of an average hereditary graph, we
also found a case for which we know the exact chromatic number of an average
hereditary graph, this makes the class of average hereditary graphs
interesting to us.

##  4 Construction and Closure

The class of average hereditary graphs itself has some interesting properties.
In this section, we look at some of these properties. First, we show how an
average hereditary graph can be recursively constructed. That is, we provide a
construction method of an average hereditary graph from another smaller
average hereditary graph. Next, we show that the class of average hereditary
graphs is closed under under graph join operation.

###  4.1 Recursive construction

We introduce a recursive construction method for an average hereditary graph.
For this we first introduce the following theorem:

######  Theorem 2.

If $H$ is a nonempty connected average hereditary graph then if $u$ is a
vertex of $H$ with the minimum degree in $H$, and $G$ is a graph obtained from
$H$ by adding a vertex $x$ to $H$ and expanding $u$ by edge $\\{u,x\\}$, then
$G$ is also average hereditary.

In order to prove this theorem we first prove two lemmas.

######  Lemma 4.

If $G$ is an average hereditary graph then $2\delta(G)\geq d(G)$.

###### Proof.

Let $G=(V,E)$ be a nonempty average hereditary graph, if $V=\emptyset$ then
the lemma holds trivially.

Let $u\in V$ s.t. $d(u)=\delta(G)$. Let $H$ be a graph induced from $G$ by
removing $u$, then $d(H)=\frac{\sum_{v\in V}d_{G}(v)-2\delta(G)}{|V|-1}$.

So,

$d(H)=\frac{\sum_{v\in
V}d_{G}(v)-2\delta(G)}{|V|-1}=\frac{|V|d(G)-2\delta(G)}{|V|-1}=d(G)\left(\frac{|V|-\frac{2\delta(G)}{d(G)}}{|V|-1}\right).$

As $G$ is average hereditary $d(H)\leq d(G)$ therefore from the above
expression we have that,

$\frac{2\delta(G)}{d(G)}\geq 1\iff 2\delta(G)\geq d(G).$

∎

Now we prove a smaller result in the next lemma which will be used in the
proof of Theorem 2.

######  Lemma 5.

Expanding any connected $k$-regular graph by any vertex gives an average
hereditary graph.

###### Proof.

Let $G=(V,E)$ be a $k$-regular graph. From Proposition 2 we have that $G$ is
average hereditary. Now let $G^{\prime}$ be the graph obtained from $G$ by
expanding any arbitrary vertex of $G$. We show that $G^{\prime}$ is also
average hereditary.

Let $x$ be the new vertex in $G^{\prime}$ and $u$ be the vertex of $G$ that we
expanded. Let $H$ be an induced subgraph of $G$. We know that we are adding a
vertex with a degree more than $k$ to $G$ to obtain $G^{\prime}$ so we know
that $d(G)<d(G^{\prime})$ as all vertices of $G$ have the same degree in $G$.
Now for $H$ if any of $u$ or $x$ is not in $H$ then $H$ is either a subgraph
or isomorphic to a subgraph of $G$ then $d(H)\leq d(G)<d(G^{\prime})$. Suppose
both $x$ and $u$ are in $H$, now we have two cases. First, suppose we only
have the neighbors of $u$ in $H$. We have that $\forall v\in
N_{G}(u),\;d_{G^{\prime}}(x)=d_{G^{\prime}}(u)=d_{G^{\prime}}(v)=k+1$. Now if
we have the neighbors of $u$ in $H$ then we have at least $k$ less vertices
with degree $k+1$ compared to $G^{\prime}$ so the degree of $H$ cannot be more
than $d(G^{\prime})$. Now suppose we have at least $1$ vertex from outside the
neighborhood of $u$ in $H$, we know that when we remove vertices from
$G^{\prime}$ to induce the subgraph $H$, each vertex we remove has a degree of
at most $k$.

As $G$ and $G^{\prime}$ are connected we introduce a vertex of degree at most
$k-1$ when constructing $H$, which means the degree of $H$ cannot be greater
than $d(G^{\prime})$ as all vertices of $G^{\prime}$ have degree greater than
$k-1$. Therefore $d(H)\leq d(G^{\prime})$, which means $G^{\prime}$ is average
hereditary. ∎

We now use our lemmas to prove Theorem 2

###### Proof of Theorem 2.

Let $H=(V,E)$ be a connected average hereditary graph such that $V$ is
nonempty, and let $u\in V$ such that $d_{H}(u)=\delta(H)$. Let
$G=H\text{exp}(u,x)$, we know $d_{G}(x)=d_{G}(u)=\delta(H)+1$. Therefore we
are increasing the average degree of $H$ in $G$.

$d(G)=\frac{|V|d(H)+2\delta(H)+2}{|V|+1}>d(H)$

Now we show that for any induced subgraph $G_{1}$ of $G$, $d(G_{1})\leq d(G)$.

Let $G_{1}\subseteq G$, if $x\not\in V(G_{1})$ or $u\not\in V(G_{1})$ then
$G_{1}$ is either a subgraph or isomorphic to a subgraph of $H$ then
$d(G_{1})\leq d(H)<d(G)$. So now we look at the case when $x,u\in V(G_{1})$,
we know there exists a graph $H_{1}\in H$ such that
$G_{1}=H_{1}\text{exp}(u,x)$. We know that $d_{H}(u)=\delta(H)\leq d(H)\leq
d(G)$. We have two cases to consider. First if $d_{G}(u)\leq d(H)$ then
$d(G_{1})\leq d(G)$. As the vertex we are adding itself has a degree less than
$d(G)$ so $d(G_{1})$ cannot be greater than $d(G)$. If $d_{G}(u)>d(H)$, we
know that $d_{H}(u)\leq d(H)$ and $d_{G}(u)=d_{H}(u)+1$, so we have that
$0<D=d_{G}(u)-d(H)\leq 1$. Now we consider two cases when $D=1$ and when
$D<1$.

Suppose $D=1$, here $D$ is the largest possible. If $D=1$ then
$d_{G}(u)=d_{H}(u)+1=d(H)+1$, so $d_{H}(u)=d(H)$ as $u$ is the vertex with
minimum degree we have that $H$ is connected regular. From Lemma 5 we have
that $G$ is average hereditary.

Now we consider the case when $0<D<1$. If $0<D<1$ then
$d_{H}(u)<d(H)<d_{G}(u)$. If we induce a proper subgraph $G_{1}$ from $G$ such
that $x,u\in V(G_{1})$ we do so by removing some vertices from $G$ (as
$d(G)\leq d(G)$ so we don’t need to consider that case). Now removing any
vertex from $G$ will reduce the sum of degrees of vertices by at least
$2\delta(H)$. From Lemma 4 we have that $2\delta(H)\geq d(H)$. As
$G_{1}=H_{1}\text{exp}(u,x)$ and we know that $d(H_{1})\leq d(H)$ so any
increase in the average degree of the subgraph caused by removing the vertices
comes from $d_{G_{1}}(x)$, as all the other vertices are from $H_{1}$, and the
average of their degrees without $x$ is less than or equal to the amount of
degrees removed. As $u$ is the vertex of $H$ with the minimum degree and
$d_{H}(u)<d(H)$, we know that there exists $v\in V$ such that $d(H)<d_{H}(v)$.
So we have that there exists $v\in V$ such that $d_{G}(x)=d_{G}(u)\leq
d_{H}(v)\leq d_{G}(v)$.

Now if $v\in V(G_{1})$ then $v\in V(H_{1})$ and $d_{H}(v)\geq d_{G}(x)$ then
if $d(G_{1})>d(G)$ then the increase will caused by the degree of $v$ so then
as $v\in V(H_{1})$, we have that $d(H_{1})>d(H)$ which is a contradiction as
$H$ is average hereditary. If $v\not\in V(G_{1})$ then we have a vertex in $G$
that is in $G_{2}=G-G_{1}$ such that the degree of $v$ is greater than equal
to the degree of $x$ so then $d(G_{1})$ cannot be greater than $d(G)$ as $v$
is not in $G_{1}$ and degree of $v$ raises $d(G)$ higher than $d(G_{1})$.

So the average degree of $G$ cannot be less than the average degree of
$G_{1}$. Therefore $G$ is average hereditary. ∎

So Theorem 2 provides a recursive construction for an average hereditary
graph. We can start from a smaller average hereditary graph and recursively
keep expanding the vertex with the minimum degree (the vertex might change
after each expansion). With this, we can construct a larger average hereditary
graph. This makes the average hereditary property more interesting as not many
graph properties are closed under expansion.

###  4.2 Closure Under Binary Operation

We now look at another interesting property that the class of average
hereditary graphs has. The class of average hereditary graphs is closed under
the graph join operation. That means if we take two average hereditary graphs
and join them the graph we obtain is also average hereditary. The following
Theorem proves this claim.

######  Theorem 3.

The class of average hereditary graphs is closed under the graph Join
operation.

###### Proof.

Let $G=(V,E)$ and $G^{\prime}=(V^{\prime},E^{\prime})$ such that $G$ and
$G^{\prime}$ are average hereditary graphs. Without loss of generality suppose
that $G$ and $G^{\prime}$ are both nonempty. We construct graph $K=G\land
G^{\prime}$ as the join of $G$ and $G^{\prime}$ such that $V(K)=V\cup
V^{\prime}$ and $E(K)=E\cup E^{\prime}\cup\\{\\{v,v^{\prime}\\}|v\in V\text{
and }v^{\prime}\in V^{\prime}\\}$. We show that $K$ is also average
hereditary.

$d(K)=\frac{d(G)|V|+d(G^{\prime})|V^{\prime}|+2|V||V^{\prime}|}{V+V^{\prime}}\geq
d(G)\;\text{ and
}\;d(K)=\frac{d(G)|V|+d(G^{\prime})|V^{\prime}|+2|V||V^{\prime}|}{V+V^{\prime}}\geq
d(G^{\prime}).$

Let $k\subseteq K$, now we have two cases to consider. If $k\subseteq G$ or
$k\subseteq G^{\prime}$ then we have that $d(k)\leq d(K)$ as both $G$ and
$G^{\prime}$ themselves are average hereditary. Now if $k\not\subseteq G$ and
$k\not\subseteq G^{\prime}$ then we have that there exists $H\subseteq G$ and
$H^{\prime}\subseteq G^{\prime}$ such that $k=H\land H^{\prime}$.

Now we know that $d(H)\leq d(G)\leq d(K)$ and $d(H^{\prime})\leq
d(G^{\prime})\leq d(K)$, so if $d(k)>d(K)$ the increase will come from the new
edges added by the join operation, which will be a subset of
$\\{\\{v,v^{\prime}\\}|v\in V\text{ and }v^{\prime}\in V^{\prime}\\}$.

As $k\subseteq K$ every vertex of $k$ that is in $H$ will have less or equal
edges than that vertex will have in $K$ as $|H^{\prime}|\leq|G^{\prime}|$ and
every vertex of $k$ that is in $H^{\prime}$ will have less or equal edges than
that vertex will have in $K$ as $|H|\leq|G|$. So the edges per vertex of every
subgraph of $k$ will be less than or equal to the edges per vertex of $K$.
Therefore $d(k)\leq d(K)$. So $K$ will be average hereditary. ∎

This is an interesting result as it gives another construction for an average
hereditary graph that is by joining two average hereditary graphs. The closure
on binary operations is also interesting algebraically. The following
corollary shows how the class is interesting algebraically.

######  Corollary 3.

The set of all average hereditary graphs is a commutative monoid.

###### Proof.

Let $ADH$ be the set of all average hereditary graphs. To show that this set
is a monoid we first define a binary operation such that the class of average
hereditary graphs is closed under that operation. Theorem 3 just gives us that
operation which is the graph join operation. The class of average hereditary
graphs is closed under the graph join operation. Now we show that graph join
is associative. To show this we show that for graphs $G_{1}=(V_{1},E_{1})$,
$G_{2}=(V_{2},E_{2})$ and $G_{3}=(V_{3},E_{3})$,

$(G_{1}\land G_{2})\land G_{3}=G_{1}\land(G_{2}\land G_{3})$

Let $H=(G_{1}\land G_{2})\land G_{3}=(V(H),E(H))$ and
$H^{\prime}=G_{1}\land(G_{2}\land G_{3})=(V(H^{\prime}),E(H^{\prime}))$.
$V(H)=V(H^{\prime})=V_{1}\cup V_{2}\cup V_{3}$ and
$E(H)=E(H^{\prime})=E_{1}\cup E_{2}\cup E_{3}\cup\\{\\{v_{1},v_{2}\\}|v_{1}\in
V_{1}\text{ and }v_{2}\in V_{2}\\}\cup\\{\\{v_{1},v_{3}\\}|v_{1}\in
V_{1}\text{ and }v_{3}\in V_{3}\\}\cup\\{\\{v_{2},v_{3}\\}|v_{2}\in
V_{2}\text{ and }v_{3}\in V_{3}\\}$.

So we have that $H=H^{\prime}$ which means that $(G_{1}\land G_{2})\land
G_{3}=G_{1}\land(G_{2}\land G_{3})$. Therefore graph join operation is
associative. Now we show that there exists an identity element in the set
$ADH$. This is simple the identity element is $K_{0}=(\emptyset,\emptyset)$.
$K_{0}$ is obviously average hereditary as $d(K_{0})=0$ and the only subgraph
of $K_{0}$ is $K_{0}$ itself. We have that for any graph $G$, $G\land
K_{0}=K_{0}\land G=G$ as for $K_{0}$, $V(K_{0})=\emptyset$ and
$E(K_{0})=\emptyset$. So $K_{0}$ is the identity element in $ADH$. This shows
that $ADH$ is a monoid under the graph join operation. We now show that the
graph join is commutative to show that $ADH$ is a commutative monoid. Let
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$. We will show that $G_{1}\land
G_{2}=G_{2}\land G_{1}$.

Let $K=G_{1}\land G_{2}=(V(K),E(K))$, and $K^{\prime}=G_{2}\land
G_{1}=(V(K^{\prime}),E(K^{\prime}))$. Then $V(K)=V_{1}\cup V_{2}$ and
$E(K)=E_{1}\cup E_{2}\cup\\{\\{v_{1},v_{2}\\}|v_{1}\in V_{1}\text{ and
}v_{2}\in V_{2}\\}$. And $V(K^{\prime})=V_{2}\cup V_{1}=V_{1}\cup V_{2}$ and
$E(K^{\prime})=E_{2}\cup E_{1}\cup\\{\\{v_{2},v_{1}\\}|v_{2}\in V_{2}\text{
and }v_{1}\in V_{1}\\}$.

So we have that $K=K^{\prime}$ which means $G_{1}\land G_{2}=G_{2}\land
G_{1}$. So the graph join operation is commutative. Therefore the set of all
average hereditary graphs makes a commutative monoid under graph join
operation. ∎

This corollary is interesting as it tells us about some algebraic properties
of the class of average hereditary graphs. From this, we can apply other
theorems about commutative monoids to the class of average hereditary graphs.

In this section we looked at some constructions for average hereditary graphs,
we also looked at how the class of average hereditary graphs has some
interesting algebraic properties. This all gives us a few interesting results
about this class of graphs itself.

##  5 NP-Hardness of Graph 3-Coloring in Average Hereditary Graphs

We looked at various properties the class of average hereditary graphs has. We
now explore the effects on the complexity of the graph 3-coloring problem when
we restrict the input to the class of average hereditary graphs. We show that
graph 3-coloring remains NP-Hard when the input is restricted to average
hereditary graphs. This result is interesting as it gives us insight on the
effect of input constraint on the graph 3-coloring problem. This result can
also be used to study the notion of boundary classes and limit class [1, 2].
We use the reduction given by Karp 1972 [11] to prove our result.

######  Lemma 6 ([11]).

3-sat $\leq_{P}$ 3-coloring.

######  Theorem 4.

Graph 3-coloring is NP-hard for the class of average hereditary graphs.

###### Proof.

Let $\phi$ be a boolean expression in 3CNF with $L$ literals and $C$ clauses,
where $L\geq 1$ and $C\geq 1$. Let $G(\phi)$ denote the graph constructed from
$\phi$ by the reduction given by Karp in [11]. From the reduction we have that
$G(\phi)$ has $6C+L+3$ vertices, and $12C+\frac{3}{2}L+3$ edges. We show that
$G(\phi)$ is average hereditary.

$d(G(\phi))=3\left(\frac{8C+L+2}{6C+L+3}\right)$

Now we show that $d(G(\phi))<4$. Suppose that $d(G(\phi))\geq 4$. So we have
that

$\frac{8C+L+2}{6C+L+3}\geq\frac{4}{3}\iff 0\geq\frac{1}{3}L+2$

This is a contradiction as $C,L\in\mathbb{Z}^{+}$. Now for positive integers
$x$, $y$, $a$ and $b$, we know that
$\frac{x-a}{y-b}\leq\frac{x}{y}\iff\frac{a}{b}\geq\frac{x}{y}$. For $G(\phi)$,

$d(G(\phi))=\frac{\sum_{v\in V(G(\phi))}d_{G(\phi)}(v)}{|V(G(\phi))|}$

Now suppose $H$ is some induced subgraph of $G(\phi)$ such that $H=G-U$, for
some $U\subseteq V(G(\phi))$, then for $H$,

$d(H)=\frac{\sum_{v\in V(G(\phi))}d_{G(\phi)}(v)-\sum_{u\in
U}d_{G(\phi)}(u)-|[V(H),\overline{V(H)}]|}{|V(G(\phi))|-|U|}=\frac{\sum_{v\in
V(G(\phi))}d_{G(\phi)}(v)-d}{|V|-|U|}$

As $G(\phi)$ is connected, and $\forall v\in V(G(\phi)),\;d_{G(\phi)}(v)\geq
2$, and no vertex with degree 2 are adjacent to each other, we have that
$d\geq 2(2|U|)$, which implies $\frac{d}{|U|}\geq 4$. So, $\frac{d}{|U|}\geq
4\geq d(G(\phi))\implies d(H)\leq d(G(\phi))$. Therefore $G(\phi)$ is average
hereditary. So we have that for each boolean expression $\phi$ in 3CNF, the
graph constructed $G(\phi)$, by the reduction given by Karp is average
hereditary. So we have that graph 3-coloring is NP-hard in the class of
average hereditary graphs. ∎

##  6 Conclusion

In this paper, we introduced this new class of graph. We initially introduced
this class to obtain a tighter bound on the chromatic number of graphs in this
class. Our initial aim was to find a case where we can bound the chromatic
number of a graph in terms of its average degree. After obtaining our bound
for average hereditary graphs we were able to generalize that bound and obtain
a bound on the chromatic number of any given graph in terms of its maximum
average degree. We then explored the class of average hereditary graphs
further. From that, we see that the class of average hereditary graphs itself
is quite interesting. We looked at many interesting results regarding this
class of graphs. Which includes an equivalent condition to compute if a graph
belongs to this class, methods for constructing Average Hereditary graphs and
computational complexity of graph 3-coloring when input is restricted to this
class.

As the class of Average Hereditary graphs is new and just introduced in this
paper there are a lot of opportunities for future work regarding the class of
average hereditary graphs. This makes this class more interesting.

## Acknowledgments

The first author would like to thank Dr. Hans Raj Tiwary
(https://kam.mff.cuni.cz/$\sim$hansraj/) for providing with his invaluable
expertise and guidance throughout the course of this research and for being a
mentor in general. Many ideas for the direction to take this research also
came from him. The first author would also like to thank Rameez Ragheb
(https://habib.edu.pk/SSE/rameez-ragheb/) for being a mentor throughout the
course of this research and prior. We would also like to thank him for
verifying proofs of several results and helping in working out the algebra for
lemma 3. Also would like to Acknowledge Meesum Ali Qazalbash
(https://www.linkedin.com/in/meesumaliqazalbash/) for looking at the proof and
algebra presented in this paper, verifying the results, and helping in the
algebra for lemma 3. The authors would also like to thank Dr. Yair Caro for
suggesting proposition 3, from this we were able to prove that the average
hereditary property can be computed in polynomial time. This also gave us the
idea to generalize our special case bound on the chromatic number to a general
case bound on the chromatic number in terms of the maximum average degree.

## References

  * [1] V.E. Alekseev, R. Boliac, D.V. Korobitsyn, and V.V. Lozin.  Np-hard graph problems and boundary classes of graphs.  Theoretical Computer Science, 389(1-2):219–236, 2007.
  * [2] Vladimir E. Alekseev.  On easy and hard hereditary classes of graphs with respect to the independent set problem.  Discrete Applied Mathematics, 132(1-3):17–26, 2003.
  * [3] Rowland Leonard Brooks.  On colouring the nodes of a network.  Mathematical Proceedings of the Cambridge Philosophical Society, 37:194–197, 1941.
  * [4] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein.  Introduction to Algorithms, fourth edition.  MIT Press, 2022.
  * [5] Reinhard Diestel.  Reinhard Diestel Graph Theory Electronic Edition 2017. Springer-Verlag Heidelberg, 1997.
  * [6] Yefim Dinitz.  Algorithm for solution of a problem of maximum flow in networks with power estimation.  Soviet Math. Dokl., 11:1277–1280, 01 1970.
  * [7] Jack Edmonds and Richard M. Karp.  Theoretical improvements in algorithmic efficiency for network flow problems.  J. ACM, 19(2):248–264, apr 1972.
  * [8] L. R. Ford and D. R. Fulkerson.  Maximal flow through a network.  Canadian Journal of Mathematics, 8:399–404, 1956.
  * [9] A. V. Goldberg.  Finding a maximum density subgraph.  Technical report, USA, 1984.
  * [10] Andrew V. Goldberg and Robert E. Tarjan.  A new approach to the maximum-flow problem.  J. ACM, 35(4):921–940, oct 1988.
  * [11] Richard Manning Karp.  Reducibility among combinatorial problems.  Proceedings of a symposium on the Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York., 1972.
  * [12] B. R. Myers and R. Liu.  A lower bound on the chromatic number of a graph.  Networks, 1(3):273–277, 1971.
  * [13] Mariia Soto, Andre Rossi, and Marc Sevaux.  Three new upper bounds on the chromatic number.  Discrete Applied Mathematics, 159(18):2281–2289, 2011.
  * [14] Douglas Brent West.  Introduction to Graph Theory. Prentice Hall, 2001.


In case of Y and Ce substituted Nd-based 1:12 phases, promising $\kappa$
values for LSDA treatment are observed. For both NdYFe22Ti2 and NdCeFe22Ti2
cases the calculated value is $\kappa$=1.20. Note that the $\kappa$ value for
the commonly used Nd2Fe14B magnet is reported to be 1.54 [11]. In the
considered benchmark system of this thesis, by considering 50% Nd-lean
quaternaries, a very close magnetic hardness factor with respect to the market
leading hard magnet was reached which is technologically encouraging.

Figure 5.10: Calculated hardness factors $\kappa$ for GGA (black), GGA+U (red)
and LSDA (blue) functionals. The clean compounds are represented by circles
and the nitrogenated compounds considered in the GGA and GGA+U approaches are
depicted as squares. The region colored as dark grey represents soft magnets
($\kappa$ < 0.1), the light grey one semi-hard magnets (0.1 < $\kappa$ < 1.0)
and the white background hard magnets ($\kappa$>1). The magnetic hardness
factor of the most well-known magnets are also shown by horizontal dotted
lines.

##  Chapter 6 Conclusion and Outlook

In conclusion, based on the promising finite temperature phase stability
findings for Nd-lean permanent magnets [35], systematic investigations on the
intrinsic magnetic properties for (Nd,X)Fe12-yTiy compounds have been
performed. As an alternative element to substitute critical Nd, abundant and
inexpensive elements, X= Y and Ce, have been chosen. Since there is no
experimental data for the considered quaternary compounds in the literature,
only the theoretical results for ternary compounds could be compared and a
promising agreement could be seen. This gives a strong confidence in the
calculated magnetic properties of Nd-lean quaternaries.

An accurate description of RE 4f-electrons has critical importance for a
successful prediction of intrinsic magnetic properties. Due to the strong
hybridization of Ce-4f with TM-3d-electrons, in addition to previous works by
Sözen et al. [7, 52, 53, 35], conventional DFT calculations are performed for
Ce-based compounds and yield satisfactory results. However, Nd 4f-electrons
are strongly localized and available DFT exchange-correlation functionals have
difficulties to accurately capture this property. Therefore, as a correction
scheme, the DFT+U approach with Hubbard U=6 eV has been used.

The methodology of this work perfectly predicts the total magnetization trend
of the 1:12 phases, that NdFe11Ti has the highest magnetisation and is
followed by YFe11Ti and CeFe11Ti. Experimentally reported saturation
magnetisation $\mu_{0}M_{S}$ for NdFe11Ti is deviating from 1.38 to 1.70 T
[86, 89, 75, 81] based on the measurement temperature and method. Our DFT
(DFT+U) calculations yield 1.47 (1.28) T, which is a good agreement. In the
case of Y and Ce substitution $\mu_{0}M_{S}$ is found to be 1.49 (1.39) T for
NdYFe22Ti2 and 1.46 (1.35) T for NdCeFe22Ti2 based on DFT (DFT+U). In
addition, for all considered compounds further $\mu_{0}M_{S}$ improvement by
$\sim$0.1 T is achieved after nitrogenation and it is found that the
magnetovolume effect plays a major role rather than chemical effects. Based on
the magnetisation calculations, very high |BH|max values for NdYFe22Ti2 and
NdCeFe22Ti2 were achieved, which are 384 and 365 kJ/m3, and they are higher
than the |BH|max of Sm2Co17B, 294 kJ/m3 [10]. Note that, lower Ti contained
quaternaries, NdYFe23Ti (484 kJ/m3) and NdCeFe23Ti (466 kJ/m3), have close
|BH|max values to the Nd2Fe14B magnet that exhibits 512 kJ/m3 [10]. In
addition, a further increase of |BH|max values around 40 kJ/m3 is calculated
with nitrogenation.

Curie temperatures $T_{C}$ are calculated by the mean-field approximation
(MFA). Systematic overestimation of $T_{C}$ for ferromagnetic (FM) state
calculations is observed. Nevertheless, quantitative agreement of decreasing
$T_{C}$ for increasing Ti concentration and increasing $T_{C}$ after
nitrogenation is captured with respect to experimental data. Miyake et al.
[105] reported that local moment disorder (LMD) calculations yield better
performance for the $T_{C}$ of REFe11Ti compounds. Our LMD calculations agree
with this finding. In the case of YFe11Ti, CeFe11Ti and NdFe11Ti, the LMD-
based $T_{C}$ calculations overestimate the experimental data by 9, 12 and 20
%, respectively. Note that, in the case of FM-based calculations, the margin
of error is around 45% for these ternaries. The LMD calculations yield 595 and
593 K $T_{C}$ values for the Nd-lean quaternaries NdYFe22Ti2 and NdCeFe22Ti2,
respectively. For both cases, theoretical $T_{C}$ is slightly higher than the
experimental $T_{C}$ of Nd2Fe14B, which is 588 K.

In the case of the magnetocrystalline anisotropy constant $K_{1}$, the
generalized gradient approximation (GGA) based exchange-correlation functional
failed for Y and Nd-based compounds. The shortcomings of GGA is also reported
for such compounds by Herper et al. and Ke et al. [75, 85]. Therefore, the
local spin density approximation (LSDA) was further considered and reached a
better agreement with respect to the experiment. Knowing $K_{1}$ and
$\mu_{0}M_{S}$ allows to calculate the magnetic hardness factor $\kappa$,
which relates to the potential of a material to be developed into a permanent
magnet and $\kappa$>1 is desired. Our 50% Nd-lean quaternaries yield a 1.20
theoretical $\kappa$ value which is close to the magnetic hardness factor of
1.54 for Nd2Fe14B.

As a conclusion to this thesis, it was shown that the substitution of critical
RE elements, such as Nd, in compounds of the ThMn12 structure with more
available elements like Ce or Y yields possible alternatives to the RE-TM type
Nd-Fe-B magnets with comparable or only slightly smaller magnetic properties.
These new quarternary (NdX)Fe24-yTiy (X=Y or Ce) compounds can consequently be
considered as an achievable way to produce more affordable magnets with a
smaller amount of critically labeled elements. As an outlook to this work, the
further investigation of other elements, besides Ce and Y, with a combination
of DFT and KKR calculations for the substitution with the Nd-atoms can be
considered. Another possibility would be the expansion to other known magnetic
structures such as the 2:14 or 2:17 phases and research the possible reduction
of RE-elements in these compounds as well. Due to similar $T_{C}$s the
investigated quarternary compounds are very appealing in a technological
perspective as they could be used in almost the same field of applications as
the Nd-Fe-B magnets when slightly lower magnetic properties are still
acceptable.

## References

  * [1] O. Gutfleisch, M. A. Willard, E. Brück, C. H. Chen, S. G. Sankar, and J. P. Liu, “Magnetic materials and devices for the 21st century: Stronger, lighter, and more energy efficient,” Advanced Materials, vol. 23, no. 7, pp. 821–842, 2011.
  * [2] K. P. Skokov and O. Gutfleisch, “Heavy rare earth free, free rare earth and rare earth free magnets - Vision and reality,” Scripta Materialia, vol. 154, pp. 289–294, 2018.
  * [3] I. Poenaru, A. Lixandru, S. Riegg, B. Fayyazi, A. Taubel, K. Güth, R. Gauß, and O. Gutfleisch, “Ce and La as substitutes for Nd in Nd2Fe14B-based melt-spun alloys and hot-deformed magnets: a comparison of structural and magnetic properties,” Journal of Magnetism and Magnetic Materials, vol. 478, pp. 198–205, 2019.
  * [4] J. M. Coey, Magnetism and Magnetic Materials.  Cambridge U.K.: Cambridge University Press, 2009.
  * [5] P. M. Levy and E. W. Lee, Magnetism: An introductory survey.  Pergamon Press, New York, 6 ed., 1973.
  * [6] B. Cullity and C. Graham, Introduction to Magnetic Materials.  Hoboken, New Jersey: Wiley, IEEE Press, 2 ed., 2009.
  * [7] H. I. Sözen, Ab initio phase stabilities of Ce-based hard magnetic materials.  Ph.d. thesis, Ruhr-Universität Bochum, 2019.
  * [8] FZ-Jülich, “https://aiida-fleur.readthedocs.io/en/v1.1.1/user_guide/ workflows/ mae_conv_wc.html.”
  * [9] H. S. Li and J. M. Coey, “Magnetic properties of ternary rare-earth transition-metal compounds,” Handbook of Magnetic Materials, vol. 28, pp. 87–196, 2019.
  * [10] J. M. Coey, “Hard magnetic materials: A perspective,” IEEE Transactions on Magnetics, vol. 47, no. 12, pp. 4671–4681, 2011.
  * [11] R. Skomski and J. M. Coey, “Magnetic anisotropy - How much is enough for a permanent magnet?,” Scripta Materialia, vol. 112, pp. 3–8, 2016.
  * [12] S. M. Abdelbasir and A. E. Shalan, Intriguing Properties and Applications of Functional Magnetic Materials.  IntechOpen, 2019.
  * [13] W. C. Ellis and E. E. Schumacher, “A Survey of Magnetic Materials in Relation to Structure,” Bell System Technical Journal, vol. 14, no. 1, pp. 8–43, 1935.
  * [14] R. A. McCurrie, “The structure and properties of alnico permanent magnet alloys,” Ferromagnetic Materials, vol. 3, pp. 107–109, 111–188, 1982\.
  * [15] É. Trémolet de Lacheisserie, D. Gignoux, and M. Schlenker, Magnetism: Materials and Applications.  New-York: Springer-Verlag, 1 ed., 2005.
  * [16] M. Sugimoto, “The Past, Present, and Future of Ferrites,” Journal of the American Ceramic Society, vol. 82, no. 2, pp. 269–280, 1999.
  * [17] J. M. Coey, “Perspective and Prospects for Rare Earth Permanent Magnets,” Engineering, vol. 6, no. 2, pp. 119–131, 2020.
  * [18] K. J. Strnat and K. D. Hoffer, “YCo5, A Promising New Permanent Magnetic Material,” tech. rep., Technical Report, Air Force Report AFML-TR-65-446, 1966\.
  * [19] M. Sagawa, S. Fujimura, and N. Togawa, “New material for permanent magnets on a base of Nd and Fe,” Journal of Applied Physics, vol. 55, p. 2083, 1984\.
  * [20] J. J. Croat, J. F. Herbst, R. W. Lee, and F. E. Pinkerton, “Pr-Fe and Nd-Fe-based materials: A new class of high-performance permanent magnets (invited),” Journal of Applied Physics, vol. 55, no. 6, pp. 2078–2082, 1984.
  * [21] J. Cui, J. Ormerod, D. Parker, R. Ott, A. Palasyuk, S. Mccall, M. P. Paranthaman, M. S. Kesler, M. A. McGuire, I. C. Nlebedim, C. Pan, and T. Lograsso, “Manufacturing Processes for Permanent Magnets: Part I—Sintering and Casting,” Jom, vol. 74, no. 4, pp. 1279–1295, 2022\.
  * [22] S. Magnets, “https://www.stanfordmagnets.com/development-of-the-ndfeb-magnet-industry.html.”
  * [23] D. J. Cordier, “Mineral Commodity Summaries,” tech. rep., U.S. Geological Survey (USGS), 2022.
  * [24] D. Bauer, D. Diamond, J. Li, M. McKittrick, D. Sandalow, and P. Telleen, “Critical Materials Strategy for Clean Energy Technologies,” US Department of Energy Office of Policy and International Affairs (PI), pp. 1–170, 2011.
  * [25] M. Pellegrini, “Report on Critical Raw Materials for the EU,” tech. rep., 2014\.
  * [26] H. Sepehri-Amin, Y. Une, T. Ohkubo, K. Hono, and M. Sagawa, “Microstructure of fine-grained Nd-Fe-B sintered magnets with high coercivity,” Scripta Materialia, vol. 65, no. 5, pp. 396–399, 2011.
  * [27] K. Hono and H. Sepehri-Amin, “Strategy for high-coercivity Nd-Fe-B magnets,” Scripta Materialia, vol. 67, no. 6, pp. 530–535, 2012.
  * [28] W. F. Li, T. Ohkubo, T. Akiya, H. Kato, and K. Hono, “The role of Cu addition in the coercivity enhancement of sintered Nd-Fe-B permanent magnets,” Journal of Materials Research, vol. 24, no. 2, pp. 413–420, 2009.
  * [29] H. Sepehri-Amin, T. Ohkubo, S. Nagashima, M. Yano, T. Shoji, A. Kato, T. Schrefl, and K. Hono, “High-coercivity ultrafine-grained anisotropic Nd-Fe-B magnets processed by hot deformation and the Nd-Cu grain boundary diffusion process,” Acta Materialia, vol. 61, no. 17, pp. 6622–6634, 2013\.
  * [30] Z. B. Li, B. G. Shen, M. Zhang, F. X. Hu, and J. R. Sun, “Substitution of Ce for Nd in preparing R2Fe14B nanocrystalline magnets,” Journal of Alloys and Compounds, vol. 628, pp. 325–328, 2015.
  * [31] J. Jin, G. Bai, Z. Zhang, and M. Yan, “Coercivity enhancement for Nd-La-Ce-Fe-B sintered magnets by tailoring La and Ce distributions,” Journal of Alloys and Compounds, vol. 763, pp. 854–860, 2018.
  * [32] D. D. Mooij and K. Buschow, “Some Novel Ternary ThMn12-type Compounds,” Journal of the Less-Common Metals, vol. 136, no. 2, pp. 207–215, 1988.
  * [33] K. H. Buschow, “Permanent magnet materials based on tetragonal rare earth compounds of the type RFe12-xMx,” Journal of Magnetism and Magnetic Materials, vol. 100, no. 1-3, pp. 79–89, 1991.
  * [34] A. M. Gabay and G. C. Hadjipanayis, “Recent developments in RFe12-type compounds for permanent magnets,” Scripta Materialia, vol. 154, pp. 284–288, 2018.
  * [35] H. I. Sözen and T. Klüner, “Ab initio phase stabilities of rare-earth lean Nd-based hard magnets,” Journal of Magnetism and Magnetic Materials, vol. 559, pp. 1–20, 2022.
  * [36] Y. Hirayama, Y. K. Takahashi, S. Hirosawa, and K. Hono, “NdFe12Nx hard-magnetic compound with high magnetization and anisotropy field,” Scripta Materialia, vol. 95, no. 1, pp. 70–72, 2015.
  * [37] H. Suzuki, “Metastable phase YFe12 fabricated by rapid quenching method,” AIP Advances, vol. 7, no. 5, pp. 0–7, 2017.
  * [38] Y. Hirayama, Y. K. Takahashi, S. Hirosawa, and K. Hono, “Scripta Materialia Intrinsic hard magnetic properties of Sm (Fe1-x Co x )12 compound with the ThMn12 structure,” Scripta Materialia, vol. 138, pp. 62–65, 2017.
  * [39] P. Hohenberg and W. Kohn, “Inhomogeneous Electron Gas,” Physical Review, vol. 136, no. 3B, pp. B864–B871, 1964.
  * [40] R. G. Parr and W. Yang, Density-Functional Theory of Atoms and Molecules.  Oxford: Oxford University Press, 1989.
  * [41] W. Koch and M. C. Holthausen, Wolfram Koch , Max C . Holthausen A Chemist ’ s Guide to.  Wiley-VCH, 2 ed., 2001.
  * [42] W. Kohn and L. Sham, “Self-Consistent Equations Including Exchange and Correlation Effects,” Physical Review, vol. 140, no. 4A, pp. A1133–A1138, 1965.
  * [43] A. D. Becke, “Perspective: Fifty years of density-functional theory in chemical physics,” Journal of Chemical Physics, vol. 140, no. 18, 2014\.
  * [44] M. Dumaz, R. Boucher, M. A. Marques, and A. H. Romero, “Authorship and citation cultural nature in Density Functional Theory from solid state computational packages,” Scientometrics, vol. 126, pp. 6681–6695, 2021\.
  * [45] M. Born and R. Oppenheimer, “Zur Quantentheorie der Molekeln,” Annalen der Physik, vol. 20, no. 84, pp. 457–484, 1927.
  * [46] J. P. Perdew and K. Schmidt, “Jacob’s ladder of density functional approximations for the exchange-correlation energy,” AIP Conf. Proc., vol. 577, no. 1, pp. 1–20, 2001.
  * [47] E. Awoonor-Williams, “Brief Overview on Density Functional Theory,” 2018.
  * [48] S. H. Vosko, L. Wilk, and M. Nusair, “Accurate spin-dependent electron liquid correlation energies for local spin density calculations: a critical analysis,” Canadian Journal of Physics, vol. 58, no. 8, pp. 1200–1211, 1980.
  * [49] J. P. Perdew, K. Burke, and M. Ernzerhof, “Generalized gradient approximation made simple,” Physical Review Letters, vol. 77, no. 18, pp. 3865–3868, 1996.
  * [50] J. P. Perdew and Y. Wang, “Accurate and simple analytic representation of the electron-gas correlation energy,” Physical Review B, vol. 45, no. 23, pp. 244–249, 1992.
  * [51] J. P. Perdew, J. A. Chevary, S. H. Vosko, K. A. Jackson, M. R. Pederson, D. J. Singh, and C. Fiolhais, “Atoms, molecules, solids, and surfaces: Applications of the generalized gradient approximation for exchange and correlation,” Physical Review B, vol. 46, no. 11, pp. 6671–6687, 1992\.
  * [52] H. I. Sözen, S. Ener, F. Maccari, K. P. Skokov, O. Gutfleisch, F. Körmann, J. Neugebauer, and T. Hickel, “Ab initio phase stabilities of Ce-based hard magnetic materials and comparison with experimental phase diagrams,” Physical Review Materials, vol. 3, no. 8, pp. 1–15, 2019.
  * [53] H. I. Sözen, T. Hickel, and J. Neugebauer, “Impact of magnetism on the phase stability of rare-earth based hard magnetic materials,” Calphad: Computer Coupling of Phase Diagrams and Thermochemistry, vol. 68, no. December 2019, 2020.
  * [54] P. E. Blöchl, “Projector augmented-wave method,” Physical Review B, vol. 50, no. 24, pp. 17953–17979, 1994.
  * [55] G. Kresse and D. Joubert, “From ultrasoft pseudopotentials to the projector augmented-wave method,” Physical Review B - Condensed Matter and Materials Physics, vol. 59, no. 3, pp. 1758–1775, 1999.
  * [56] D. Vanderbilt, “Soft self-consistent pseudopotentials in a generalized eigenvalue formalism,” Rapid Communications, vol. 41, no. 11, pp. 7892–7895, 1990.
  * [57] K. W. Böer and U. W. Pohl, Semiconductor Physics.  Cham: Springer, 2018.
  * [58] U. Von Barth and L. Hedin, “A local exchange-correlation potential for the spin polarized case. I,” Journal of Physics C: Solid State Physics, vol. 5, no. 13, pp. 1629–1642, 1972.
  * [59] G. Bihlmayer, “Density-functional Theory of Magnetism,” in Handbook of Magnetism and Advanced Magnetic Materials (H. Kronmüller and S. Parkin, eds.), Wiley, 2007.
  * [60] A. I. Lichtenstein, V. Anisimov, and J. Zaanen, “Density-functional theory and strong interactions: Orbital ordering in Mott-Hubbard insulators,” Physical Review B, vol. 52, no. 8, pp. 5467–5471, 1995.
  * [61] S. Dudarev and G. Botton, “Electron-energy-loss spectra and the structural stability of nickel oxide: An LSDA+U study,” Physical Review B - Condensed Matter and Materials Physics, vol. 57, no. 3, pp. 1505–1509, 1998\.
  * [62] A. Georges and G. Kotliar, “Hubbard model in infinite dimensions,” Physical Review B, vol. 45, no. 12, pp. 6479–6483, 1992.
  * [63] A. Liechtenstein, M. Katsnelson, V. Antropov, and V. Gubanov, “Local Spin Density Functional Approach to the Theory of Exchange Interactions in Ferromagnetic Metals and Alloys,” Journal of Magnetism and Magnetic Materials, vol. 67, pp. 65–74, 1987.
  * [64] G. Kresse and J. Furthmüller, “Efficiency of ab-initio total energy calculations for metals and semiconductors using a plane-wave basis set,” Computational Materials Science, vol. 6, no. 1, pp. 15–50, 1996.
  * [65] G. Kresse and J. Furthmüller, “Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set,” Physical Review B - Condensed Matter and Materials Physics, vol. 54, no. 16, pp. 11169–11186, 1996.
  * [66] J. Korringa, “On the Calculation of the Energy of a Bloch Wave in a Metal,” Physica, no. 6, pp. 392–400, 1947.
  * [67] W. Kohn and N. Rostoker, “Solution of the schrödinger equation in periodic lattices with an application to metallic lithium,” Physical Review, vol. 94, no. 5, pp. 1111–1120, 1954.
  * [68] H. Akai, “http://kkr.issp.u-tokyo.ac.jp.”
  * [69] H. Shiba, “A Reformulation of the Coherent Potential Approximation and Its Applications,” Progress of Theoretical Physics, vol. 46, no. 1, pp. 77–94, 1971.
  * [70] H. Akai, “Residual resistivity of Ni-Fe, Ni-Cr and other ferromagnetic alloys,” Physica B+C, vol. 86-88, no. 1, pp. 539–540, 1977.
  * [71] A. W. V.L. Moruzzi, J.F. Janak, Calculated Properties of Metals.  Pergamon Press, New York, 1978.
  * [72] J. Jensen and A. R. Mackintosh, “Rare earth magnetism: structures and excitations,” Physics, p. 403, 1991.
  * [73] M. Richter, “Band structure theory of magnetism in 3d-4f compounds,” Journal of Physics D: Applied Physics, vol. 31, no. 9, pp. 1017–1048, 1998.
  * [74] J. K. Lang, P. A. Cox, and Y. Baer, “Study of the 4f and valence band density of states in rare-earth metals. I. Theory of the 4f states,” Journal of Physics F: Metal Physics, vol. 11, no. 1, pp. 113–119, 1981.
  * [75] H. C. Herper, K. Skokov, S. Ener, P. Thunström, L. V. B. Diop, O. Gutfleisch, and O. Eriksson, “Magnetic Properties of NdFe11Ti and YFe11Ti, from Experiment and Theory,” SSRN Electronic Journal, 2022\.
  * [76] N. Drebov, A. Martinez-Limia, L. Kunz, A. Gola, T. Shigematsu, T. Eckl, P. Gumbsch, and C. Elsässer, “Ab initio screening methodology applied to the search for new permanent magnetic materials,” New Journal of Physics, vol. 15, 2013.
  * [77] W. Körner, G. Krugel, and C. Elsässer, “Theoretical screening of intermetallic ThMn12 -type phases for new hard-magnetic compounds with low rare earth content,” Scientific Reports, vol. 6, no. February, pp. 1–9, 2016.
  * [78] I. Dirba, Y. Harashima, H. Sepehri-Amin, T. Ohkubo, T. Miyake, S. Hirosawa, and K. Hono, “Thermal decomposition of ThMn12-type phase and its optimum stabilizing elements in SmFe12-based alloys,” Journal of Alloys and Compounds, vol. 813, p. 152224, 2020.
  * [79] O. Isnard, S. Miraglia, M. Guillot, and D. Fruchart, “Hydrogen effects on the magnetic properties of RFe11Ti compounds,” Journal of Alloys and Compounds, vol. 275-277, pp. 637–641, 1998.
  * [80] I. S. Tereshina, P. Gaczynski, V. S. Rusakov, H. Drulis, S. A. Nikitin, W. Suski, N. V. Tristan, and T. Palewski, “Magnetic anisotropy and Mössbauer effect studies of YFe11Ti and YFe11TiH,” Journal of Physics: Condensed Matter, vol. 13, p. 8161, 2001.
  * [81] M. Akayama, H. Fujii, K. Yamamoto, and K. Tatami, “Physical properties of nitrogenated RFe11Ti intermetallic compounds (R=Ce, Pr and Nd) with ThMn12-type structure,” Journal of Magnetism and Magnetic Materials, vol. 130, no. 1-3, pp. 99–107, 1994.
  * [82] K. Buschow, Electronic and Magnetic Properties of Metals and Ceramics, Part II, Materials Science and Technology Series.  VCH, 3b ed., 1994.
  * [83] O. Isnard, Role of interstitial elements on permanent magnet alloys based on rare earth elements and iron: Synthesis, structural study, spectroscopic analysis in relation to magnetic properties.  Ph.d. thesis, University Grenoble, 1993.
  * [84] Y. Wang, J. Shen, N. X. Chen, and J. L. Wang, “Theoretical investigation on site preference of foreign atoms in rare-earth intermetallics,” Journal of Alloys and Compounds, vol. 319, no. 1-2, pp. 62–73, 2001.
  * [85] L. Ke and D. D. Johnson, “Intrinsic magnetic properties in R(Fe1-xCox)11TiZ (R= Yand Ce;Z= H,C,and N),” Physical Review B, vol. 94, no. 2, pp. 1–9, 2016.
  * [86] Y. C. Yang, X. D. Zhang, S. L. Ge, Q. Pan, L. S. Kong, H. Li, J. L. Yang, B. S. Zhang, Y. F. Ding, and C. T. Ye, “Magnetic and crystallographic properties of novel Fe-rich rare-earth nitrides of the type RTiFe11N1-δ (invited),” Journal of Applied Physics, vol. 70, no. 10, pp. 6001–6005, 1991.
  * [87] Q. Pan, Z.-x. Liu, and Y.-c. Yang, “Structural and magnetic properties of Ce (Fe ,M )${}_{1}2$Nx interstitial compounds, M=Ti, V, Cr, and Mo,” Journal of Applied Physics, vol. 76, pp. 6728–6730, 1994.
  * [88] Y. Hirayama, T. Miyake, and K. Hono, “Rare-Earth Lean Hard Magnet Compound NdFe12N,” Jom, vol. 67, no. 6, pp. 1344–1349, 2015.
  * [89] C. Piquer, F. Grandjean, O. Isnard, V. Pop, and G. J. Long, “A magnetic and Mössbauer spectral study of the spin reorientation in NdFe11Ti and NdFe11TiH,” Journal of Applied Physics, vol. 95, no. 11 I, pp. 6308–6316, 2004.
  * [90] S. Suzuki, T. Kuno, K. Urushibata, K. Kobayashi, N. Sakuma, K. Washio, H. Kishimoto, A. Kato, and A. Manabe, “A (Nd, Zr)(Fe, Co)11.5Ti0.5Nx compound as a permanent magnet material,” AIP Advances, vol. 4, no. 11, pp. 7–12, 2014.
  * [91] S. A. Nikitin, I. S. Tereshina, V. N. Verbetskiǐ, and A. A. Salamova, “Magnetic anisotropy of YFe11Ti and its hydride,” Physics of the Solid State, vol. 40, no. 2, pp. 258–262, 1998.
  * [92] Y. chang Yang, X. dong Zhang, L. shu Kong, Q. Pan, and S. lin Ge, “New potential hard magnetic material - NdTiFe11Nx,” Solid State Communications, vol. 78, no. 4, pp. 317–320, 1991.
  * [93] A. Vishina, O. Eriksson, O. Y. Vekilova, A. Bergman, and H. C. Herper, “Ab-initio study of the electronic structure and magnetic properties of Ce2Fe17,” Journal of Alloys and Compounds, vol. 888, p. 161521, 2021.
  * [94] S. Obbade, D. Fruchart, M. Bououdina, S. Miraglia, J. L. Soubeyroux, and O. Isnard, “About hydrogen insertion in ThMn12 type alloys,” Journal of Alloys and Compounds, vol. 253-254, pp. 298–301, 1997.
  * [95] Q. N. Qi, Y. P. Li, and J. M. Coey, “Gas-phase interstitially modified intermetallics R(Fe11Ti) Z1-delta: II. 3d magnetization of the compounds Y(Fe11Ti) Z1-delta (Z = N, C),” Journal of Physics: Condensed Matter, vol. 4, no. 42, pp. 8209–8220, 1992.
  * [96] W. Mao, J. Yang, B. Cui, B. Cheng, Y. Yang, H. Du, B. Zhang, C. Ye, and J. Yang, “A study on the effect of hydrogen in the compounds with ThMn12-type structure,” Journal of Physics Condensed Matter, vol. 10, no. 12, pp. 2611–2616, 1998.
  * [97] J. Snarski-Adamski and M. Werwiński, “Effect of transition metal doping on magnetic hardness of CeFe12-based compounds,” Journal of Magnetism and Magnetic Materials, vol. 554, no. July, 2022.
  * [98] T. Fukazawa, H. Akai, Y. Harashima, and T. Miyake, “First-principles investigation of Nd(Fe,M)12 (M = K–Br) and Nd(Fe,Cr,Co,Ni,Ge,As)12: Possible enhancers of Curie temperature for NdFe12 magnetic compounds,” Acta Materialia, vol. 226, 2022.
  * [99] Y. Harashima, K. Terakura, H. Kino, S. Ishibashi, and T. Miyake, “Nitrogen as the best interstitial dopant among X= B, C, N, O, and F for strong permanent magnet NdFe11TiX: First-principles study,” Physical Review B - Condensed Matter and Materials Physics, vol. 92, no. 18, pp. 1–13, 2015.
  * [100] R. Skomski, Simple Models of Magnetism.  Oxford University Press on Demand, 2008.
  * [101] J. Fidler, T. Schrefl, S. Hoefinger, and M. Hajduga, “Recent developments in hard magnetic bulk materials,” Journal of Physics Condensed Matter, vol. 16, no. 5, 2004.
  * [102] H. Akai and P. H. Dederichs, “Local moment disorder in ferromagnetic alloys,” Physical Review B, vol. 47, no. 14, pp. 8739–8747, 1993.
  * [103] B. L. Gyorffy, A. J. Pindor, J. Staunton, G. M. Stocks, and H. Winter, “A first-principles theory of ferromagnetic phase transitions in metals,” Journal of Physics F: Metal Physics, vol. 15, no. 6, pp. 1337–1386, 1985.
  * [104] F. Maccari, S. Ener, D. Koch, I. Dirba, K. P. Skokov, E. Bruder, L. Schäfer, and O. Gutfleisch, “Correlating changes of the unit cell parameters and microstructure with magnetic properties in the CeFe11Ti compound,” Journal of Alloys and Compounds, vol. 867, p. 158805, 2021\.
  * [105] T. Miyake, Y. Harashima, T. Fukazawa, and H. Akai, “Understanding and optimization of hard magnetic compounds from first principles,” Science and Technology of Advanced Materials, vol. 22, no. 1, pp. 543–556, 2021\.
  * [106] M. D. Kuz’min, “Shape of temperature dependence of spontaneous magnetization of ferromagnets: Quantitative analysis,” Physical Review Letters, vol. 94, no. 10, pp. 16–19, 2005.
  * [107] F. Körmann, A. Dick, B. Grabowski, B. Hallstedt, T. Hickel, and J. Neugebauer, “Free energy of bcc iron: Integrated ab initio derivation of vibrational, electronic, and magnetic contributions,” Physical Review B - Condensed Matter and Materials Physics, vol. 78, no. 3, pp. 1–4, 2008.
  * [108] L. Bozukov, A. Apostolov, and M. Stoytchev, “A change in magnetic and structural properties of the CeFe11Ti intermetallic compound upon hydrogen absorption,” Journal of Magnetism and Magnetic Materials, vol. 101, no. 1-3, pp. 355–356, 1991.
  * [109] M. Springford and D. Shoenberg, Electrons at the Fermi Surface.  Cambridge U.K.: Cambridge University Press, 1980.
  * [110] J. L. Wang, N. Tang, B. Fuquan, W. H. Wang, W. Q. Wang, G. H. Wu, and F. M. Yang, “Study of the magnetocrystalline anisotropy of RFe11-xCoxTi compounds with R = Y and Er,” Journal of Physics Condensed Matter, vol. 13, no. 8, pp. 1617–1626, 2000.
  * [111] D. Goll, R. Loeffler, R. Stein, U. Pflanz, S. Goeb, R. Karimi, and G. Schneider, “Temperature dependent magnetic properties and application potential of intermetallic Fe11-xCoxTiCe,” Physica Status Solidi - Rapid Research Letters, vol. 8, no. 10, pp. 862–865, 2014.
  * [112] C. Zhou, F. E. Pinkerton, and J. F. Herbst, “Magnetic properties of CeFe 11-xCoxTi with ThMn12 structure,” Journal of Applied Physics, vol. 115, no. 17, p. 17C716, 2014.
  * [113] W. Bouzidi, T. Bartoli, R. Sedek, A. Bouzidi, J. Moscovici, and L. Bessais, “Low-field magnetocaloric effect of NdFe11Ti and SmFe10V2 compounds,” Journal of Materials Science: Materials in Electronics, vol. 32, no. 8, pp. 10579–10586, 2021.
  * [114] S. A. Nikitin, I. S. Tereshina, V. N. Verbetsky, and A. A. Salamova, “Magnetic anisotropy of YFe11Ti single crystal and its hydride,” International Journal of Hydrogen Energy, vol. 24, no. 2, pp. 217–219, 1999\.

## List of Abbreviations

  * RE - Rare-earth

  * TM - Transition metal

  * $m_{tot}$ \- Total magnetic moment

  * $\mu_{0}$ \- Magnetic constant

  * $\mu_{B}$ \- Bohr magneton

  * $H$ \- Magnetic field

  * $H_{a}$ \- Anisotropy field

  * $H_{c}$ \- Coercivity field

  * $H_{d}$ \- Internal magnetic field

  * $M$ \- Magnetization

  * $M_{r}$ \- Remanence magnetization

  * $M_{S}$ \- Magnetization saturation

  * $M(T)$ \- Finite temperature magnetization

  * $m(t)$ \- Reduced magnetization

  * $T_{C}$ \- Curie temperature

  * |BH|max \- Maximum energy product

  * MCA - Magnetocrystalline anisotropy

  * MAE - Magnetocrystalline anisotropy energy

  * $\Delta E_{MAE}$ \- Anisotropy energy

  * $K_{1}$ \- Anisotropy constant 1${}^{\text{st}}$ order

  * $\kappa$ \- Hardness factor

  * HF - Hartree-Fock

  * post-HF - post Hartree-Fock

  * DFT - Density functional theory

  * DFT+U \- Density functional theory with applied Hubbard U correction

  * DMFT - Dynamical mean field theory

  * LDA - Local Density Approximation

  * LSDA - Local Spin Density Approximation

  * GGA - Generalized Gradient Approximation

  * PW91 - Functional by Perdew and Wang

  * PBE - Functional by Perdew, Burke and Ernzerhof

  * PAW - Projector Augmented Wave

  * USPP - Ultrasoft Pseudopotentials

  * VASP - Vienna ab initio Simulation Package

  * KKR - Korringa-Kohn-Rostoker

  * SCF - self-consistent field

  * FM - Ferromagnetic

  * LMD - Local Moment Disorder

  * DLM - Disorder local moment

  * MFA - Mean-field approximation

  * ASA - Atomic sphere approximation

  * CPA - Coherent potential approximation

  * MJW - Moruzzi, Janak and Williams

  * TB-LMTO-ASA - Tight-binding linear-muffin-tin-orbital atomic-sphere-approximation

  * FPLO18 - Full potential local orbital code released in 2018

  * DOS - Density of states

  * XRD - X-Ray diffraction

  * ESM - Extraction sample magnetometer

  * PPMS - Physical property measurement system

  * VSM - Vibrating sample magnetometer

  * bcc - Body centered cubic

## Erklärung

Hiermit versichere ich an Eides statt, dass ich diese Arbeit selbstständig
verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel benutzt
habe. Außerdem versichere ich, dass ich die allgemeinen Prinzipien
wissenschaftlicher Arbeit und Veröffentlichungen, wie sie in den Leitlinien
guter wissenschaftlicher Praxis der Carl von Ossietzky Universität Oldenburg
festgehalten sind, befolgt habe.

——————————–

Stephan Erdmann