# Critical $(P_{5},dart)$-Free Graphs

Wen Xia  College of Computer Science, Nankai University, Tianjin 300071, China
Tianjin Key Laboratory of Network and Data Security Technology, Nankai
University, Tianjin 300071, China  Jorik Jooken  Department of Computer
Science, KU Leuven Campus Kulak-Kortrijk, 8500 Kortrijk, Belgium  Jan
Goedgebeur  Department of Computer Science, KU Leuven Campus Kulak-Kortrijk,
8500 Kortrijk, Belgium  Department of Applied Mathematics, Computer Science
and Statistics, Ghent University, 9000 Ghent, Belgium  Shenwei Huang Email:
<EMAIL_ADDRESS>College of Computer Science, Nankai University,
Tianjin 300071, China  Tianjin Key Laboratory of Network and Data Security
Technology, Nankai University, Tianjin 300071, China

(September 2, 2023)

###### Abstract

Given two graphs $H_{1}$ and $H_{2}$, a graph is $(H_{1},H_{2})$-free if it
contains no induced subgraph isomorphic to $H_{1}$ nor $H_{2}$. Let $P_{t}$ be
the path on $t$ vertices. A dart is the graph obtained from a diamond by
adding a new vertex and making it adjacent to exactly one vertex with degree 3
in the diamond.

In this paper, we show that there are finitely many $k$-vertex-critical
$(P_{5},dart)$-free graphs for $k\geq 1$ To prove these results, we use
induction on $k$ and perform a careful structural analysis via Strong Perfect
Graph Theorem combined with the pigeonhole principle based on the properties
of vertex-critical graphs. Moreover, for $k\in\\{5,6,7\\}$ we characterize all
$k$-vertex-critical $(P_{5},dart)$-free graphs using a computer generation
algorithm. Our results imply the existence of a polynomial-time certifying
algorithm to decide the $k$-colorability of $(P_{5},dart)$-free graphs for
$k\geq 1$ where the certificate is either a $k$-coloring or a $(k+1)$-vertex-
critical induced subgraph.

Keywords. Graph coloring; $k$-critical graphs; Strong perfect graph theorem;
Polynomial-time algorithms.

##  1 Introduction

All graphs in this paper are finite and simple. A _$k$ -coloring_ of a graph
$G$ is a function $\phi:V(G)\longrightarrow\\{1,\ldots,k\\}$ such that
$\phi(u)\neq\phi(v)$ whenever $uv\in E(G)$. Equivalently, a $k$-coloring of
$G$ can be viewed as a partition of $V(G)$ into $k$ stable sets. If a
$k$-coloring exists, we say that $G$ is $k$-colorable. The _chromatic number_
of $G$, denoted by $\chi(G)$, is the minimum number $k$ such that $G$ is
$k$-colorable. A graph $G$ is $k$-chromatic if $\chi(G)=k$. A graph $G$ is
$k$-critical if it is $k$-chromatic and $\chi(G-e)<\chi(G)$ for any edge $e\in
E(G)$. For instance, $K_{2}$ is the only 2-critical graph and odd cycles are
the only 3-critical graphs. A graph is critical if it is $k$-critical for some
integer $k\geq 1$. Vertex-criticality is a weaker notion. A graph $G$ is
$k$-vertex-critical if $\chi(G)=k$ and $\chi(G-v)<k$ for any $v\in V(G)$.

For a fixed $k\geq 3$, it has long been known that determining the
$k$-colorability of a general graph is an NP-complete problem [22]. However,
the situation changes if one restricts the structure of the graphs under
consideration.

Let $\mathcal{H}$ be a set of graphs. A graph $G$ is $\mathcal{H}$-free if it
does not contain any member in $\mathcal{H}$ as an induced subgraph. When
$\mathcal{H}$ consists of a single graph $H$ or two graphs $H_{1}$ and
$H_{2}$, we write $H$-free and $(H_{1},H_{2})$-free instead of $\\{H\\}$-free
and $\\{H_{1},H_{2}\\}$-free, respectively. We say that $G$ is $k$-vertex-
critical $\mathcal{H}$-free if it is $k$-vertex-critical and
$\mathcal{H}$-free. In this paper, we study $k$-vertex-critical $\mathcal{H}$
-free graphs. The following problem arouses our interest: Given a set
$\mathcal{H}$ of graphs and an integer $k\geq 1$, are there finitely many
$k$-vertex-critical $\mathcal{H}$-free graphs? This question is very important
because the finiteness of the set has a fundamental algorithmic implication.

######  Theorem 1 (Folklore).

If the set of all $k$-vertex-critical $\mathcal{H}$-free graphs is finite,
then there is a polynomial-time algorithm to determine whether an
$\mathcal{H}$-free graph is $(k-1)$-colorable. ∎

Let $K_{n}$ be the complete graph on $n$ vertices. Let $P_{t}$ and $C_{t}$
denote the path and the cycle on $t$ vertices, respectively. The complement of
$G$ is denoted by $\overline{G}$. For two graphs $G$ and $H$, we use $G+H$ to
denote the disjoint union of $G$ and $H$. For a positive integer, we use $rG$
to denote the disjoint union of $r$ copies of $G$. For $s,r\geq 1$, let
$K_{r,s}$ be the complete bipartite graph with one part of size $r$ and the
other part of size $s$. Our research is mainly motivated by the following two
theorems.

######  Theorem 2 ([16]).

For any fixed integer $k\geq 5$, there are infinitely many $k$-vertex-critical
$P_{5}$-free graphs.

It is natural to consider which subclasses of $P_{5}$-free graphs have
finitely many $k$-vertex-critical graphs. In 2021, Cameron, Goedgebeur, Huang
and Shi [8] obtained the following dichotomy result.

######  Theorem 3 ([8]).

Let $H$ be a graph of order 4 and $k\geq 5$ be a fixed integer. Then there are
infinitely many k-vertex-critical $(P_{5},H)$-free graphs if and only if $H$
is $2P_{2}$ or $P_{1}+K_{3}$.

This theorem completely solves the finiteness problem of $k$-vertex-critical
$(P_{5},H)$-free graphs for $|H|=4$. In [8], the authors also posed the
natural question of which five-vertex graphs $H$ lead to finitely many
$k$-vertex-critical $(P_{5},H)$-free graphs.

It is known that there are exactly 13 5-vertex-critical $(P_{5},C_{5})$-free
graphs [16]. Recently, Cameron and Hoàng constructed infinite families of
$k$-vertex-critical $(P_{5},C_{5})$-free graphs for $k\geq 6$ [7]. It has been
proven that there are finitely many $k$-vertex-critical $(P_{5},banner)$-free
graphs for $k=5$ [18] and 6 [5] and there are finitely many $k$-vertex-
critical $(P_{5},\overline{P_{5}})$-free graphs for fixed $k$ [10]. Hell and
Huang proved that there are finitely many $k$-vertex-critical
$(P_{6},C_{4})$-free graphs [14]. This was later generalized to
$(P_{t},K_{r,s})$-free graphs in the context of $H$-coloring [21]. This gives
an affirmative answer for $H=K_{2,3}$. In [4], Cai, Goedgebeur and Huang
showed that there are finitely many $k$-vertex-critical $(P_{5},gem)$-free
graphs and finitely many $k$-vertex-critical
$(P_{5},\overline{P_{3}+P_{2}})$-free graphs. Later, Cameron and Hoaǹg [6]
gave a better bound on the order of $k$-vertex-critical $(P_{5},gem)$-free
graphs and determined all such graphs for $k\leq 7$. Moreover, it has been
proven that that there are finitely many 5-vertex-critical $(P_{5},bull)$-free
graphs [17] and finitely many 5-vertex-critical $(P_{5},chair)$-free graphs
[19].

Our contributions. A dart (see Figure 1) is the graph obtained from a diamond
by adding a new vertex and making it adjacent to exactly one vertex with
degree 3 in the diamond. Our main result is as follows.

Figure 1: The dart graph.

######  Theorem 4.

For every fixed integer $k\geq 1$, there are finitely many $k$-vertex-critical
$(P_{5},dart)$-free graphs.

We prove a Ramsey-type statement (see Lemma 4 below) which allows us to prove
our main result by induction on $k$. This is another example of a result that
is proved by induction on $k$ for the finitess problem besides the one in
[10].

We perform a careful structural analysis via Strong Perfect Graph Theorem
combined with the pigeonhole principle based on the properties of vertex-
critical graphs. Moreover, for $k\in\\{5,6,7\\}$ we computationally determine
a list of all $k$-vertex-critical $(P_{5},dart)$-free graphs.

Our results imply the existence of polynomial-time certifying algorithm to
decide the $k$-colorability of $(P_{5},dart)$-free graphs for $k\geq 1$. (An
algorithm is certifying if, along with the answer given by the algorithm, it
also gives a certificate which allows to verify in polynomial time that the
output of the algorithm is indeed correct; in case of $k$-coloring the the
certificate is either a $k$-coloring or a $(k+1)$-vertex-critical induced
subgraph.)

######  Theorem 5.

For every fixed integer $k\geq 1$, there is a polynomial-time certifying
algorithm to decide the $k$-colorability of $(P_{5},dart)$-free graphs.

###### Proof.

Let $G$ be a $(P_{5},dart)$-free graph. We first run the polynomial-time
algorithm for determining whether a $P_{5}$-free graph is $k$-colorable from
[15] for $G$. If the answer is yes, the algorithm outputs a $k$-coloring of
$G$. Otherwise $G$ is not $k$-colorable. In this case, $G$ must contain a
$(k+1)$-vertex-critical $(P_{5},dart)$-free graph as an induced subgraph. For
each $(k+1)$-vertex-critical $(P_{5},dart)$-free graph $H$, it takes
polynomial-time to check whether $G$ contains $H$. Since there are only
finitely many such graphs by Theorem 4, we can do this for every such graph
$H$ and the total running time is still polynomial. ∎

The remainder of the paper is organized as follows. We present some
preliminaries in Section 2 and give structural properties around an induced
$C_{5}$ in a ($P_{5}$,dart)-free graph in Section 3. We show that there are
finitely many $k$-vertex-critical ($P_{5}$,dart)-free graphs for all $k\geq 1$
in Section 4 and computationally determine an exhaustive list of such graphs
for $k\in\\{5,6,7\\}$ in Section 5. Finally, we give a conclusion in Section
6.

##  2 Preliminaries

For general graph theory notation we follow [1]. For $k\geq 4$, an induced
cycle of length $k$ is called a $k$-hole. A $k$-hole is an odd hole
(respectively even hole) if $k$ is odd (respectively even). A $k$-antihole is
the complement of a $k$-hole. Odd and even antiholes are defined analogously.

Let $G=(V,E)$ be a graph. If $uv\in E(G)$, we say that $u$ and $v$ are
neighbors or adjacent, otherwise $u$ and $v$ are nonneighbors or nonadjacent.
The neighborhood of a vertex $v$, denoted by $N_{G}(v)$, is the set of
neighbors of $v$. For a set $X\subseteq V(G)$, let $N_{G}(X)=\cup_{v\in
X}N_{G}(v)\setminus X$. We shall omit the subscript whenever the context is
clear. For $x\in V(G)$ and $S\subseteq V(G)$, we denote by $N_{S}(x)$ the set
of neighbors of $x$ that are in $S$, i.e., $N_{S}(x)=N_{G}(x)\cap S$. For two
sets $X,S\subseteq V(G)$, let $N_{S}(X)=\cup_{v\in X}N_{S}(v)\setminus X$.

For $X,Y\subseteq V(G)$, we say that $X$ is complete (resp. anticomplete) to
$Y$ if every vertex in $X$ is adjacent (resp. nonadjacent) to every vertex in
$Y$. If $X=\\{x\\}$, we write “$x$ is complete (resp. anticomplete) to $Y$”
instead of “$\\{x\\}$ is complete (resp. anticomplete) to $Y$”. If a vertex
$v$ is neither complete nor anticomplete to a set $S$, we say that $v$ is
mixed on $S$. For a vertex $v\in V$ and an edge $xy\in E$, if $v$ is mixed on
$\\{x,y\\}$, we say that $v$ is mixed on $xy$. For a set $H\subseteq V(G)$, if
no vertex in $V(G)\setminus H$ is mixed on $H$, we say that $H$ is a
homogeneous set, otherwise $H$ is a nonhomogeneous set.

A vertex subset $S\subseteq V(G)$ is stable if no two vertices in $S$ are
adjacent. A clique is the complement of a stable set. Two nonadjacent vertices
$u$ and $v$ are said to be comparable if $N(v)\subseteq N(u)$ or
$N(u)\subseteq N(v)$. For an induced subgraph $A$ of $G$, we write $G-A$
instead of $G-V(A)$. For $S\subseteq V$, the subgraph _induced_ by $S$ is
denoted by $G[S]$. We say that a vertex $w$ distinguishes two vertices $u$ and
$v$ if $w$ is adjacent to exactly one of $u$ and $v$.

We proceed with a few useful results that will be used later. The first
folklore property of vertex-critical graph is that such graphs contain no
comparable vertices. A generalization of this property was presented in [8].

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

Let $G$ be a $k$-vertex-critical graph. Then $G$ has no two nonempty disjoint
subsets $X$ and $Y$ of $V(G)$ that satisfy all the following conditions.

  * •

$X$ and $Y$ are anticomplete to each other.

  * •

$\chi(G[X])\leq\chi(G[Y])$.

  * •

Y is complete to $N(X)$.

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

Let $G$ be a 5-vertex-critical $P_{5}$-free graph and $S$ be a homogeneous set
of $V(G)$. For each component $A$ of $G[S]$,

  1. (i)

if $\chi(A)=1$, then $A$ is a $K_{1}$;

  2. (ii)

if $\chi(A)=2$, then $A$ is a $K_{2}$;

  3. (iii)

if $\chi(A)=3$, then $A$ is a $K_{3}$ or a $C_{5}$.

We extend Lemma 2 to all critical graphs, which may be of independent
interest.

######  Lemma 3.

Let $G$ be a $k$-vertex-critical graph and $S$ be a homogeneous set of $V(G)$.
For each component $A$ of $G[S]$, if $\chi(A)=m$ with $m<k$, then $A$ is an
$m$-vertex-critical graph.

###### Proof.

Suppose not. Then there exist some vertex $u\in V(A)$ such that $\chi(A-u)=m$.
Since $G$ is $k$-vertex-critical, $G-u$ is $(k-1)$-colorable. Let $\phi$ be a
$(k-1)$-coloring of $G-u$ and $\phi(A-u)=\\{1,2,\ldots,s\\}$ with $m\leq s\leq
k-1$. Since $A$ is homogeneous, then $\phi(N(A-u))\notin\\{1,2,\ldots,s\\}$.
Let $f$ be an $m$-coloring of $A$ and $f(A)=\\{1,2,\ldots,m\\}$. Let $g(A)=f$
and $g(G-A)=\phi|_{G-A}$. Then $g$ is a $(k-1)$-coloring of $G$. This
contradicts $G$ is $k$-vertex-critical.

Therefore, $A$ is an $m$-vertex-critical graph. ∎

Next, we prove an important lemma, which will be used frequently in the proof
of our results.

######  Lemma 4.

Let $G$ be a $dart$-free graph and $c$ be a fixed integer. Let $S,T$ be two
disjoint subsets of $V(G)$ such that $|S|\leq c$ and $T$ is not complete to
$S$. For every $w_{1},w_{2}\in V(T)$ with $w_{1}w_{2}\notin E(G)$ we have the
following. If every vertex in $S$ is adjacent to at least one of $w_{1}$ and
$w_{2}$, and there exists a vertex $w\in V(G)\setminus{(S\cup T)}$ such that
$w$ is complete to $S\cup T$, then $|T|\leq f(\chi(T))$ where $f$ is a
function.

###### Proof.

Let $N_{0}=S$, $N_{i}=\\{v|v\in T\setminus{\cup_{j=0}^{i-1}N_{j}}$, $v$ has a
nonneighbor in $N_{i-1}\\}$ where $i\geq 1$. Let $u\in N_{i-1}$ and
$v,v^{\prime}\in N_{i}$ with $vv^{\prime}\notin E(G)$.

First, we show that $u$ is adjacent to at least one of $v$ and $v^{\prime}$.
If $i=1$, we are done. Now we consider the case of $i\geq 2$. Suppose that $u$
is adjacent to neither $v$ nor $v^{\prime}$. Let $u^{\prime}\in N_{i-2}$ be
the nonneighbor of $u$. Then $u^{\prime}$ is complete to $v$ and $v^{\prime}$
by the definition of $N_{i}$. Since $w$ is complete to $S\cup T$. Then
$\\{v,v^{\prime},u^{\prime},w,u\\}$ induces a dart. So $u$ is adjacent to at
least one of $v$ and $v^{\prime}$.

Next, we show that each $N_{i}$ is a function of $\chi(T)$ where $i\geq 1$.
Since $\chi(N_{i})\leq\chi(T)$, we can partition $N_{i}$ into at most
$\chi(T)$ stable sets, because $u$ is adjacent to at least one of $v$ and
$v^{\prime}$. Thus, each vertex in $N_{i-1}$ has at most $\chi(T)$
nonneighbors in $N_{i}$. Since $|N_{0}|=|S|\leq c$, we have $|N_{i}|\leq
c({\chi(T))}^{i}$.

Finally, we show that $i\leq 2\chi(T)+1$. Suppose not. By the definition of
$N_{i}$, $N_{i}$ and $N_{j}$ are complete when $|i-j|>1$. Then we take a
vertex $u_{i}\in N_{i}$ where $i$ is even. Now,
$\\{u_{2},u_{4},\ldots,u_{2\chi(T)+2}\\}$ induces a $K_{\chi(T)+1}$, a
contradiction. This shows $i\leq 2\chi(T)+1$.

Therefore, $|T|\leq f(\chi(T))$ where $f$ is a function. ∎

The following theorem tells us there are finitely many 4-vertex-critical
$P_{5}$-free graphs.

######  Theorem 6 ([2, 23]).

If $G=(V,E)$ is a 4-vertex-critical $P_{5}$-free graph, then $|V|\leq 13$.

A property on bipartite graphs is shown as follows.

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

Let $G$ be a connected bipartite graph. If $G$ contains a $2K_{2}$, then $G$
must contain a $P_{5}$.

The clique number of $G$, denoted by $\omega(G)$, is the size of a largest
clique in $G$. A graph $G$ is perfect if $\chi(H)=\omega(H)$ for every induced
subgraph $H$ of $G$. Another result we use is the famous Strong Perfect Graph
Theorem.

######  Theorem 7 (The Strong Perfect Graph Theorem [9]).

A graph is perfect if and only if it contains no odd holes or odd antiholes.

##  3 Structure around 5-hole

Let $G=(V,E)$ be a graph and $H$ be an induced subgraph of $G$. We partition
$V\setminus V(H)$ into subsets with respect to $H$ as follows: for any
$X\subseteq V(H)$, we denote by $S(X)$ the set of vertices in $V\setminus
V(H)$ that have $X$ as their neighborhood among $V(H)$, i.e.,

$S(X)=\\{v\in V\setminus V(H):N_{V(H)}(v)=X\\}.$

For $0\leq m\leq|V(H)|$, we denote by $S_{m}$ the set of vertices in
$V\setminus V(H)$ that have exactly $m$ neighbors in $V(H)$. Note that
$S_{m}=\bigcup_{X\subseteq V(H):|X|=m}S(X)$.

Let $G$ be a $(P_{5},dart)$-free graph and $C=v_{1},v_{2},v_{3},v_{4},v_{5}$
be an induced $C_{5}$ in $G$. We partition $V\setminus C$ with respect to $C$
as follows, where all indices below are modulo five.

$S_{0}=\\{v\in V\backslash V(C):N_{C}(v)=\emptyset\\},$

$S_{2}(i)=\\{v\in V\backslash V(C):N_{C}(v)=\\{v_{i-1},v_{i+1}\\}\\},$

$S_{3}^{1}(i)=\\{v\in V\backslash
V(C):N_{C}(v)=\\{v_{i-1},v_{i},v_{i+1}\\}\\},$

$S_{3}^{2}(i)=\\{v\in V\backslash
V(C):N_{C}(v)=\\{v_{i-2},v_{i},v_{i+2}\\}\\},$

$S_{4}(i)=\\{v\in V\backslash
V(C):N_{C}(v)=\\{v_{i-2},v_{i-1},v_{i+1},v_{i+2}\\}\\},$

$S_{5}=\\{v\in V\backslash V(C):N_{C}(v)=V(C)\\}.$

Let $S_{3}^{1}=\bigcup_{i=1}^{5}S_{3}^{1}(i)$,
$S_{3}^{2}=\bigcup_{i=1}^{5}S_{3}^{2}(i)$ and
$S_{4}=\bigcup_{i=1}^{5}S_{4}(i)$. Since $G$ is $P_{5}$-free, we have that

$V(G)=S_{0}\cup S_{2}\cup S_{3}^{1}\cup S_{3}^{2}\cup S_{4}\cup S_{5}.$

We now prove a number of useful properties of these sets using the fact that
$G$ is $(P_{5},dart)$-free. All properties are proved for $i=1$ due to
symmetry.

  1. (1)

$S_{0}$ is anticomplete to $S_{2}\cup S_{3}^{1}$.

Let $u\in S_{0}$, $v\in S_{2}(1)\cup S_{3}^{1}(1)$. If $uv\in E(G)$, then
$\\{u,v,v_{2},v_{3},v_{4}\\}$ is an induced $P_{5}$.

  2. (2)

For each $1\leq i\leq 5$, $S_{3}^{2}(i)$ is not mixed on any edge of $S_{0}$.

Let $uu^{\prime}$ be an edge of $S_{0}$, and $v\in S_{3}^{2}(1)$. If $uv\in
E(G)$ and $uv^{\prime}\notin E(G)$, then $\\{u^{\prime},u,v,v_{1},v_{2}\\}$ is
an induced $P_{5}$.

  3. (3)

$S_{0}$ is anticomplete to $S_{4}\cup S_{5}$ .

Let $u\in S_{0}$ and $v\in S_{4}(1)\cup S_{5}$. If $uv\in E(G)$, then
$\\{v_{3},v_{4},v_{5},v,u\\}$ is a dart.

  4. (4)

Let $A$ be a component of $S_{0}$, then $A$ is homogeneous and $P_{3}$-free.

By (1)–(3), we have $A$ is homogeneous. Suppose that $A$ contains a
$P_{3}=uvw$. Since $G$ is connected, there must exist some vertex $x\in N(A)$.
By (1)–(3), $x\in S_{3}^{2}(i)$ for some $1\leq i\leq 5$. Then
$\\{u,v,w,x,v_{i}\\}$ is a dart. So, $A$ is $P_{3}$-free.

  5. (5)

For each $1\leq i\leq 5$, $S_{3}^{1}(i)$ is not mixed on any edge of
$S_{2}(i)$.

Let $uu^{\prime}$ be an edge of $S_{2}(1)$ and $v\in S_{3}^{1}(1)$. If
$vu^{\prime}\in E(G)$ and $vu\notin E(G)$, then
$\\{u,u^{\prime},v,v_{2},v_{3}\\}$ is a dart.

  6. (6)

For each $1\leq i\leq 5$, $S_{2}(i)$ is complete to $S_{3}^{1}(i+1)\cup
S_{3}^{1}(i-1)$.

Let $u\in S_{2}(1),v\in S_{3}^{1}(2)$. If $uv\notin E(G)$, then
$\\{v_{1},v,v_{3},v_{2},u\\}$ is a dart. By symmetry, $S_{2}(1)$ is complete
to $S_{3}^{1}(5)$.

  7. (7)

For each $1\leq i\leq 5$, $S_{2}(i)$ is anticomplete to $S_{3}^{1}(i+2)\cup
S_{3}^{1}(i-2)$.

Let $u\in S_{2}(1),v\in S_{3}^{1}(3)$. If $uv\in E(G)$, then
$\\{v_{1},v_{5},u,v,v_{3}\\}$ is an induced $P_{5}$. By symmetry, $S_{2}(1)$
is anticomplete to $S_{3}^{1}(4)$.

  8. (8)

For each $1\leq i\leq 5$, $S_{2}(i)$ is complete to $S_{3}^{2}(i)$.

Let $u\in S_{2}(1)$ and $v\in S_{3}^{2}(1)$. If $uv\notin E(G)$, then
$\\{u,v_{5},v_{1},v,v_{3}\\}$ is an induced $P_{5}$.

  9. (9)

For each $1\leq i\leq 5$, $S_{2}(i)$ is anticomplete to $S_{3}^{2}\setminus
S_{3}^{2}(i)$.

Let $u\in S_{2}(1),v\in S_{3}^{2}(2)$. If $uv\in E(G)$, then
$\\{u,v,v_{4},v_{5},v_{1}\\}$ is a dart. By symmetry, $S_{2}(1)$ is
anticomplete to $S_{3}^{1}(5)$. Let $w\in S_{3}^{2}(3)$. If $uw\in E(G)$, then
$\\{u,w,v_{1},v_{5},v_{3}\\}$ is a dart. By symmetry, $S_{2}(1)$ is
anticomplete to $S_{3}^{1}(4)$.

  10. (10)

For each $1\leq i\leq 5$, $S_{2}(i)$ is anticomplete to $S_{4}(i)$.

Let $u\in S_{2}(1),v\in S_{4}(1)$. If $uv\in E(G)$, then
$\\{u,v,v_{3},v_{2},v_{1}\\}$ is a dart.

  11. (11)

For each $1\leq i\leq 5$, $S_{2}(i)$ is complete to $S_{4}\setminus S_{4}(i)$.

Let $u\in S_{2}(1),v\in S_{4}(2)\cup S_{4}(3)$. If $uv\notin E(G)$, then
$\\{v_{1},v,v_{4},v_{5},u\\}$ is a dart. By symmetry, $S_{2}(1)$ is complete
to $S_{4}(5)\cup S_{4}(4)$.

  12. (12)

For each $1\leq i\leq 5$, $S_{2}(i)$ is complete to $S_{2}(i+1)\cup
S_{2}(i-1)$.

Let $u\in S_{2}(1),v\in S_{2}(2)$. If $uv\notin E(G)$, then
$\\{u,v_{5},v_{1},v,v_{3}\\}$ is an induced $P_{5}$. By symmetry, $S_{2}(1)$
is complete to $S_{2}(5)$.

  13. (13)

For each $1\leq i\leq 5$, $S_{2}(i+2)\cup S_{2}(i-2)$ is not mixed on any edge
of $S_{2}(i)$.

Let $uu^{\prime}$ be an edge of $S_{2}(1)$ and $v\in S_{2}(3)$. If
$vu^{\prime}\in E(G)$ and $vu\notin E(G)$, then
$\\{v_{3},v_{4},v,u^{\prime},u\\}$ is an induced $P_{5}$. By symmetry,
$S_{2}(4)$ is not mixed on any edge of $S_{2}(1)$.

  14. (14)

If $S_{2}\neq\emptyset$, then $S_{5}=\emptyset$. If $S_{5}\neq\emptyset$, then
$S_{2}=\emptyset$.

Suppose that $S_{2}\neq\emptyset$ and $S_{5}\neq\emptyset$. Let $u\in
S_{2}(1)$ and $v\in S_{5}$. If $uv\notin E(G)$, then
$\\{v_{1},v,v_{4},v_{5},u\\}$ is a dart. If $uv\in E(G)$, then
$\\{u,v_{2},v_{1},v,v_{4}\\}$ is a dart.

  15. (15)

Let $A$ be a component of $S_{2}(i)$. Then $A$ is homogeneous and $A$ is
$P_{3}$-free.

By (5)–(14), we have $A$ is a homogeneous set. Suppose that $A$ contains a
$P_{3}=uvw$, then $\\{u,v,w,v_{i-1},v_{i}\\}$ is a dart. So $A$ is
$P_{3}$-free.

  16. (16)

For each $1\leq i\leq 5$, $S_{5}$ is complete to $S_{3}^{2}(i)$.

Let $u\in S_{5}$, $v\in S_{3}^{2}(1)$. If $uv\notin E(G)$, then
$\\{v_{2},u,v_{5},v_{1},v\\}$ is a dart.

  17. (17)

Let $u,u^{\prime}\in S_{5}$ with $uu^{\prime}\notin E(G)$. Then every vertex
in $S_{3}^{1}\cup S_{4}$ is adjacent to at least one of $u$ and $u^{\prime}$.

Let $v\in S_{3}^{1}(1)\cup S_{4}(4)$. If $v$ is adjacent to neither $u$ nor
$u^{\prime}$, then $\\{u,u^{\prime},v_{4},v_{5},v\\}$ is a dart.

  18. (18)

For $1\leq i\leq 5$, $S_{3}^{1}(i)$, $S_{3}^{2}(i)$ and $S_{4}(i)$ is a
clique, respectively.

Let $u,v\in S_{3}^{1}(1)$. If $uv\notin E(G)$, then
$\\{u,v,v_{1},v_{5},v_{4}\\}$ is a dart. So $S_{3}^{1}(1)$ is a clique. Let
$u,v\in S_{3}^{2}(1)$. If $uv\notin E(G)$, then $\\{u,v,v_{4},v_{3},v_{2}\\}$
is a dart. So $S_{3}^{2}(1)$ is a clique. Let $u,v\in S_{4}(1)$. If $uv\notin
E(G)$, then $\\{u,v,v_{3},v_{2},v_{1}\\}$ is a dart. So $S_{4}(1)$ is a
clique.

##  4 The proof of Theorem 4

###### Proof.

We prove the theorem by induction on $k$. If $1\leq k\leq 4$, there are
finitely many $k$-vertex-critical $(P_{5},dart)$-free graphs by Theorem 6. In
the following, we assume that $k\geq 5$ and there are finitely many
$i$-vertex-critical graphs for $i\leq{k-1}$. Now, we consider the case of $k$.

Let $G=(V,E)$ be a $k$-vertex-critical $(P_{5},dart)$-free graph. We show that
$|G|$ is bounded. Let $\mathcal{L}=\\{K_{k},\overline{C_{2k-1}}\\}$. If $G$
has a subgraph isomorphic to a member $L\in\mathcal{L}$, then $|V(G)|=|V(L)|$
by the definition of vertex-critical and so we are done. So, we assume in the
following $G$ has no induced subgraph isomorphic to a member in $\mathcal{L}$.
Then $G$ is imperfect. Since $G$ is $k$-vertex-critical and
$\chi(\overline{C_{2t+1}})\geq k+1$ if $t\geq k$, it follows that $G$ does not
contain $\overline{C_{2t+1}}$ for $t\geq k$. Moreover, since $G$ is
$P_{5}$-free, it does not contain $C_{2t+1}$ for $t\geq 3$. It then follows
from Theorem 7, $G$ must contain some $\overline{C_{2t+1}}$ for $2\leq t\leq
k-2$. To finish the proof, we only need to prove the following two lemmas.

###  4.1 5-hole

######  Lemma 6.

If $G$ contains an induced $C_{5}$, then $G$ has finite order.

###### Proof.

Let $C=v_{1},v_{2},v_{3},v_{4},v_{5}$ be an induced $C_{5}$. We partition
$V(G)$ with respect to $C$.

Since $G$ is $K_{k}$-free, combined with (18), we have $S_{3}^{1}(i)$,
$S_{3}^{2}(i)$ and $S_{4}(i)$ is $K_{k-2}$-free, respectively. Then
$|S_{3}^{1}(i)|\leq k-3$, $|S_{3}^{2}(i)|\leq k-3$ and $|S_{4}(i)|\leq k-3$.
Therefore, $|S_{3}^{1}|\leq 5k-15$, $|S_{3}^{2}|\leq 5k-15$ and $|S_{4}|\leq
5k-15$. Thus, in the following, we only need to bound $S_{0}$, $S_{2}$ and
$S_{5}$.

We first bound $S_{0}$.

######  Claim 1.

Let $A$ be a component of $S_{0}$, then $\chi(A)\leq k-2.$

###### Proof.

Suppose that $\chi(A)\geq k-1$. Since $G$ is connected, there must exist $v\in
N(A)$ and $v\in S_{3}^{2}$ by (1)–(3). Since $A$ is homogeneous, $v$ is
complete to $A$. Then $\chi(G[V(A)\cup\\{v\\}])\geq k$. Since
$G[V(A)\cup\\{v\\}]\subset G$, it contradicts with $G$ is $k$-vertex-critical.
∎

Let $A$ be a component of $G$, we call $A$ a $K_{i}$-component if $A\cong
K_{i}$ where $i\geq 1$.

######  Claim 2.

Each component of $S_{0}$ is a $K_{m}$ where $1\leq m\leq k-2$. For each
$1\leq m\leq k-2$, the number of $K_{m}$-components is not more than
$2^{5k-15}$.

###### Proof.

By (4), $S_{0}$ is a disjoint union of cliques. Combined with Claim 1, it
follows that each component of $S_{0}$ is a $K_{m}$ where $1\leq m\leq k-2$.

Suppose that the number of $K_{1}$-components in $S_{0}$ is more than
$2^{5k-15}\geq 2^{|S_{3}^{2}|}$. The pigeonhole principle shows that there are
two $K_{1}$-components $u,v$ having the same neighborhood in $S_{3}^{2}$.
Since $S_{0}$ is anticomplete to $S_{2}\cup S_{3}^{1}\cup S_{4}\cup S_{5}$.
Then $u,v$ have the same neighborhood in $V(G)$. This contradicts with Lemma
1.

Similarly, we can show that the number of $K_{2}$-components $,\ldots,$
$K_{k-2}$-components is not more than $2^{5k-15}$, respectively. ∎

By Claim 2, it follows that $S_{0}$ is bounded. Next, we bound $S_{2}$ and
$S_{5}$. Note that at least one of $S_{2}$ and $S_{5}$ is an empty set by
(14). In the following, we first assume that $S_{5}\neq\emptyset$. Then
$S_{2}=\emptyset$.

######  Claim 3.

$S_{5}$ is bounded.

###### Proof.

If $S_{5}$ is complete to $S_{3}^{1}\cup S_{4}$, then $S_{5}$ is a homogeneous
set. Since $\chi(S_{5})\leq k-3$, each component of $S_{5}$ is an $m$-vertex-
critical graph with $1\leq m\leq k-3$ by Lemma 3. By the inductive hypothesis,
it follows that there are finitely many $m$-vertex-critical
$(P_{5},dart)$-free graphs with $1\leq m\leq k-3$. By the pigeonhole
principle, the number of each kind of graph is not more than $2$. Therefore,
$S_{5}$ is bounded.

Assume that $S_{5}$ is not complete to $S_{3}^{1}\cup S_{4}$. We have
$|S_{3}^{1}\cup S_{4}|\leq 10k-30$ and there exist $w\in V(C)$ such that $w$
is complete to $S_{3}^{1}\cup S_{4}\cup S_{5}$. By (17), every vertex in
$S_{3}^{1}\cup S_{4}$ is adjacent to at least one of $w_{1}$ and $w_{2}$ where
$w_{1},w_{2}\in S_{5}$ and $w_{1}w_{2}\notin E(G)$. Then $|S_{5}|$ is a
function of $\chi(S_{5})$ by Lemma 4. Since $\chi(S_{5})\leq k-3$, it follows
that $S_{5}$ is bounded. ∎

Thus, $|G|$ is bounded if $S_{5}\neq\emptyset$. Next, we assume that
$S_{2}\neq\emptyset$. Then $S_{5}=\emptyset$ by (14).

######  Claim 4.

Each component of $S_{2}(i)$ is a $K_{m}$ where $1\leq m\leq k-2$. For each
$1\leq m\leq k-2$, the number of $K_{m}$-components is not more than
$2^{k-2}+1$.

###### Proof.

By (15), $S_{2}(i)$ is a disjoint union of cliques. If $S_{2}(i)$ contains a
$K_{k-1}$, then $G$ contains a $K_{k}$, a contradiction. So each component of
$S_{2}(i)$ is a $K_{m}$ where $1\leq m\leq k-2$.

Suppose that the number of $K_{1}$-components in $G[S_{2}(1)]$ is more than
$2^{k-2}+1\geq 2\cdot 2^{|S_{3}^{1}(1)|}+1$. By the pigeonhole principle,
there are $y_{1},y_{2},y_{3}$ having the same neighborhood in $S_{3}^{1}(1)$.
For any $y_{i}\neq y_{j}$ with $i,j\in\\{1,2,3\\}$, since $y_{i}$ and $y_{j}$
are not comparable, there must exist
$y_{i}^{\prime}\in{N(y_{i})}\setminus{N(y_{j})}$,
$y_{j}^{\prime}\in{N(y_{j})}\setminus{N(y_{i})}$. By (5)–(13),
$y_{i}^{\prime},y_{j}^{\prime}\in S_{2}(3)\cup S_{2}(4)$.

If $y_{i}^{\prime},y_{j}^{\prime}\in S_{2}(3)$, then
$y_{i}^{\prime}y_{j}^{\prime}\in E(G)$. For otherwise
$\\{y_{i}^{\prime},y_{i},v_{5},y_{j},y_{j}^{\prime}\\}$ is an induced $P_{5}$.
Then $\\{y_{i}^{\prime},y_{j}^{\prime},y_{j},v_{2},v_{1}\\}$ is a dart, a
contradiction. By symmetry, $y_{i}^{\prime},y_{j}^{\prime}\notin S_{2}(4)$. In
the following, by symmetry, we assume that $y_{i}^{\prime}\in S_{2}(3)$,
$y_{j}^{\prime}\in S_{2}(4)$. Then $y_{i}^{\prime}y_{j}^{\prime}\in E(G)$,
otherwise $\\{y_{j},y_{j}^{\prime},v_{3},v_{4},y_{i}^{\prime}\\}$ is an
induced $P_{5}$. Let $y_{l}\neq y_{i},y_{j}$ with $1\leq l\leq 3$. Then
$y_{l}y_{i}^{\prime}\notin E(G)$, otherwise
$\\{y_{i},y_{i}^{\prime},y_{l},v_{2},v_{1}\\}$ is a dart. By symmetry,
$y_{l}y_{j}^{\prime}\notin E(G)$. Since $y_{i}$ and $y_{l}$ are not
comparable, there must exist $y_{l}^{\prime}\in{N(y_{l})}\setminus{N(y_{i})}$.
Then $y_{l}^{\prime}\in S_{2}(4)$, $y_{j}y_{l}^{\prime}\notin E(G)$ and
$y_{l}y_{j}^{\prime}\notin E(G)$. Then $y_{l}^{\prime}y_{j}^{\prime}\in E(G)$,
otherwise $\\{y_{l},y_{l}^{\prime},v_{3},y_{j}^{\prime},y_{j}\\}$ is an
induced $P_{5}$. Then $\\{y_{j},y_{j}^{\prime},y_{l}^{\prime},v_{5},v_{1}\\}$
is a dart, a contradiction.

Similarly, we can show that the number of $K_{2}$-components $,\dots,$
$K_{k-2}$-components is not more than $2^{k-2}+1$, respectively. ∎

Therefore, $|G|$ is bounded if $S_{2}\neq\emptyset$. This completes the proof
of Lemma 6. ∎

###  4.2 $(2t+1)$-antihole

######  Lemma 7.

If $G$ contains an induced $\overline{C_{2t+1}}$ for $3\leq t\leq k-2$, then
$G$ has finite order.

###### Proof.

Let $C=v_{1},v_{2},\ldots,v_{2t+1}$ be an induced $\overline{C_{2t+1}}$ such
that $v_{i}v_{j}\in E(G)$ if and only if $|i-j|>1$. All indices are modulo
$2t+1$. We partition $V(G)$ with respect to $C$. In the following, we shall
write $S_{2}(v_{i},v_{i+1})$ for $S_{2}(\\{v_{i},v_{i+1}\\})$,
$S_{3}(v_{i},v_{i+1},v_{i+3})$ for $S_{3}(\\{v_{i},v_{i+1},v_{i+3}\\})$, etc.

######  Claim 5.

$S_{m}=\emptyset$ for $1\leq m\leq t$.

###### Proof.

Let $u\in S_{m}$ for some $1\leq m\leq t$. Since $u$ has at most $t$ neighbors
on $C$, there exists an index $i$ such that $u$ is adjacent to neither
$v_{i-t}$ nor $v_{i+t}$.

If $u$ is mixed on
$\\{v_{i-t+2},v_{i-t+3},\ldots,v_{i},v_{i+1},\ldots,v_{i+t-2}\\}$. Then there
exist $j,s\in\\{i-t+2,i-t+3,\ldots,i,i+1,\ldots,i+t-2\\}$ with $|j-s|\geq 2$
such that $u$ distinguishes $v_{j}$ and $v_{s}$. Then
$\\{v_{i-t},v_{i+t},v_{j},v_{s},u\\}$ induces a dart.

If $u$ is complete to
$\\{v_{i-t+2},v_{i-t+3},\ldots,v_{i},v_{i+1},\ldots,v_{i+t-2}\\}$, then $u$ is
anticomplete to $\\{v_{i-t+1},v_{i+t-1}\\}$. For otherwise $u$ would be
complete to $\\{v_{i-t+1},v_{i-t+2},\ldots,v_{i+t-1}\\}$ which contradicts the
assumption that $u$ has at most $t$ neighbors on $C$. Then
$\\{v_{i-t+1},v_{i+t},v_{i+t-1},v_{i},u\\}$ induces a dart.

Now assume that $u$ is anticomplete to
$V(C)\setminus\\{v_{i-t+1},v_{i+t-1}\\}$. By symmetry, we assume that $u$ is
adjacent to $v_{i-t+1}$. Then $\\{u,v_{i-t+1},v_{i+t},v_{i-t+2},v_{i-t}\\}$ is
an induced $P_{5}$.

Therefore, $S_{m}=\emptyset$, for $1\leq m\leq t$. ∎

######  Claim 6.

$S_{0}=\emptyset$.

###### Proof.

Suppose not. Let $u\in S_{0}$. By Claim 5 and the connectivity of $G$, $u$ has
a neighbor $u^{\prime}\in S_{i}$ for some $t+1\leq i\leq 2t+1$. Then there
exists an index $i$ such that $u^{\prime}$ is adjacent to $v_{i-t}$, $v_{i+t}$
and some vertex $v_{j}$ where $j\in\\{i-t+2,\ldots,i,i+1,\ldots,i+t-2\\}$. Now
$\\{v_{i-t},v_{i+t},v_{j},u^{\prime},u\\}$ induces a dart. This proves
$S_{0}=\emptyset$. ∎

######  Claim 7.

For every $X\subseteq C$ with $t+1\leq|X|\leq 2t$, $S(X)$ is a clique.

###### Proof.

Let $X\subseteq C$ be an arbitrary set with $t+1\leq|X|\leq 2t$. Since
$t+1\leq|X|\leq 2t$, there exists an index $i\in C$ such that $v_{i}\in X$ but
$v_{i+1}\notin X$, and $v_{j}\in X$ where $v_{j}\in
V(C)\setminus\\{v_{i-2},v_{i-1},\ldots,v_{i+2}\\}$. If $S(X)$ contains two
non-adjacent vertices $u$ and $u^{\prime}$, then
$\\{u,u^{\prime},v_{i},v_{j},v_{i+1}\\}$ induces a dart. Therefore, $S(X)$ is
a clique. ∎

Since $G$ is $K_{k}$-free, by Claim 7, it follows that $|S(X)|\leq k-3$ for
$X\subseteq C$ with $t+1\leq|X|\leq 2t$. Therefore, $|S_{t+1}\cup\ldots\cup
S_{2t}|\leq(k-3)(\tbinom{2t+1}{t+1}+\dots+\tbinom{2t+1}{2t})$. In the
following, we bound $S_{2t+1}$.

######  Claim 8.

Let $u,u^{\prime}\in S_{2t+1}$ with $uu^{\prime}\notin E(G)$. Then every
vertex in $S_{t+1}\cup\ldots\cup S_{2t}$ is adjacent to at least one of $u$
and $u^{\prime}$.

###### Proof.

Let $v\in S_{m}$ with $t+1\leq m\leq 2t$. Then there exist two vertices
$v_{i},v_{j}\in V(C)$ with $|i-j|\geq 2$ such that $v$ distinguishes $v_{i}$
and $v_{j}$. If $v$ is adjacent to neither $u$ nor $u^{\prime}$, then
$\\{u,u^{\prime},v_{i},v_{j},v\\}$ induces a dart. ∎

######  Claim 9.

$S_{2t+1}$ is bounded.

###### Proof.

If $S_{2t+1}$ is complete to $S_{t+1}\cup\ldots\cup S_{2t}$, then $S_{2t+1}$
is a homogeneous set. Since $\chi(S_{2t+1})\leq k-t-1$, each component of
$S_{2t+1}$ is an $m$-vertex-critical graph with $1\leq m\leq k-4$ by Lemma 3.
By the inductive hypothesis, it follows that there are finitely many
$m$-vertex-critical$(P_{5},dart)$-free graph for $1\leq m\leq k-4$. By the
pigeonhole principle, the number of each kind of graph is not more than
$2^{|S_{t+1}\cup\ldots\cup S_{2t}|}$. Therefore, $S_{2t+1}$ is bounded.

Now assume that $S_{2t+1}$ is not complete to $S_{t+1}\cup\ldots\cup S_{2t}$.
We have $|S_{t+1}\cup\ldots\cup
S_{2t}|\leq(k-3)(\tbinom{2t+1}{t+1}+\dots+\tbinom{2t+1}{2t})$ and there exists
$w\in V(C)$ such that $w$ is complete to $S_{t+1}\cup\ldots\cup S_{2t}\cup
S_{2t+1}$. By Claim 9, every vertex in $S_{t+1}\cup\ldots\cup S_{2t}$ is
adjacent to at least one of $w_{1}$ and $w_{2}$ where $w_{1},w_{2}\in
S_{2t+1}$ and $w_{1}w_{2}\notin E(G)$. Then $|S_{2t+1}|$ is a function of
$\chi(S_{2t+1})$ by Lemma 4. Since $\chi(S_{2t+1})\leq k-t-1$, it follows that
$S_{2t+1}$ is bounded. ∎

This completes the proof of Lemma 7. ∎

By Lemma 6–Lemma 7, it follows that Theorem 4 holds. ∎

##  5 Complete characterization for $k\in\\{5,6,7\\}$

In Section 4, we proved that there are finitely many $k$-vertex-critical
$(P_{5},dart)$-free graphs by showing the existence of an upper bound for the
order of such graphs for every integer $k\geq 1$. These bounds are not
necessarily sharp. In the current section, we show sharp upper bounds for
$k\in\\{5,6,7\\}$ by computationally determining an exhaustive list of all
$k$-vertex-critical $(P_{5},dart)$-free graphs.

We created two independent implementations of the algorithm from Goedgebeur
and Schaudt [13], which we extended for the $(P_{5},dart)$-free case. The
source code of these implementations can be downloaded from [12] and [20]. The
algorithm expects three parameters as an input: an integer $k\geq 1$, a set of
graphs $\mathcal{H}$ and a graph $I$. It generates all $k$-vertex-critical
$\mathcal{H}$-free graphs that contain $I$ as an induced subgraph. The
pseudocode is given in Algorithm 1. The algorithm is not guaranteed to
terminate (e.g. there could be infinitely many such graphs). However, if the
algorithm terminates, it is guaranteed that the generated graphs are
exhaustive. The algorithm works by recursively extending a graph with one
vertex and adding edges between this new vertex and already existing vertices.
In each step of the recursion, the algorithm uses powerful pruning rules that
restrict the ways in which the edges are added. These pruning rules allow the
algorithm to terminate some branches of the recursion and are the reason why
the algorithm itself can terminate in some cases. For example, a graph which
is not $(k-1)$-colorable cannot appear as a proper induced subgraph of a
$k$-vertex-critical graph, so the algorithm does not need to extend such
graphs. In general, the pruning rules that are used by the algorithm are much
more sophisticated than this. We refer the interested reader to [13] for
further details about the correctness of the algorithm and the different
pruning rules.

Algorithm 1 Extend(An integer $k$, A set of graphs $\mathcal{H}$, A graph $I$)

1: if $I$ is $\mathcal{H}$-free AND not generated before then

2: if $I$ is not $(k-1)$-colorable then

3: if $I$ is a $k$-vertex-critical graph then

4: output $I$

5: end if

6: else

7: for every graph $I^{\prime}$ obtained by adding a new vertex $u$ to $I$ and
edges between $u$ and vertices in $V(I)$ in all possible ways that are
permitted by the pruning rules do

8: Extend($k$,$\mathcal{H}$,$I^{\prime}$)

9: end for

10: end if

11: end if

We now prove the following characterization theorem:

######  Theorem 8.

There are exactly 184 5-vertex-critical graphs and the largest such graphs
have order 13. There are exactly 18,029 6-vertex-critical graphs and the
largest such graphs have order 16. There are exactly 6,367,701 7-vertex-
critical graphs and the largest such graphs have order 19.

###### Proof.

We saw in Section 4 that every $k$-vertex-critical $(P_{5},dart)$-free graph
is either $K_{k}$, $\overline{C_{2k-1}}$ or contains $C_{5}$ as an induced
subgraph or contains $\overline{C_{2t+1}}$ as an induced subgraph for some
$2\leq t\leq k-2$. If Algorithm 1 is called with the parameters
$k\in\\{5,6,7\\}$, $\mathcal{H}=\\{P_{5},dart\\}$ and $I$ one of these graphs,
the algorithm terminates in less than a second for $k=5$, less than a minute
for $k=6$ and a few hours for $k=7$ (for all choices of $k$ and $I$). The
counts of these graphs are reported in Table 1. The results of the two
independent implementations of this algorithm (cf. [12] and [20]) are in
complete agreement with each other. ∎

Table 1 gives an overview of the number of $k$-critical and $k$-vertex-
critical $(P_{5},dart)$-free graphs for $k\in\\{5,6,7\\}$. A graph $G$ is
$k$-critical $(P_{5},dart)$-free if it is $k$-chromatic, $(P_{5},dart)$-free
and every $(P_{5},dart)$-free proper subgraph of $G$ is $(k-1)$-colorable. The
graphs from Table 1 can be obtained from the meta-directory of the House of
Graphs [3] at https://houseofgraphs.org/meta-directory/critical-h-free.
Moreover, the $k$-critical graphs from Table 1 can also be inspected in the
searchable database of the House of Graphs [3] by searching for the keywords
“critical (P5,dart)-free”. The 5-critical $(P_{5},dart)$-free graphs are shown
in Figure 2.

Vertices | 5 | 6 | 7 | 8 | 9 | 10 | 11 | Total
---|---|---|---|---|---|---|---|---
5-critical | 1 |  | 1 | 1 | 7 | 1 |  |
5-vertex-critical | 1 |  | 1 | 6 | 172 | 1 |  |
6-critical |  | 1 |  | 1 | 1 | 6 | 33 |
6-vertex-critical |  | 1 |  | 1 | 6 | 171 | 17,834 |
7-critical |  |  | 1 |  | 1 | 1 | 6 |
7-vertex-critical |  |  | 1 |  | 1 | 6 | 171 |
Vertices | 12 | 13 | 14 | 15 | 16 | 19 |  |
5-critical |  | 3 |  |  |  |  |  | 14
5-vertex-critical |  | 3 |  |  |  |  |  | 184
6-critical | 2 | 1 |  |  | 13 |  |  | 58
6-vertex-critical | 2 | 1 |  |  | 13 |  |  | 18,029
7-critical | 28 | 250 | 6 | 2 | 1 | 35 |  | 331
7-vertex-critical | 17,834 | 6,349,644 | 6 | 2 | 1 | 35 |  | 6,367,701
Table 1: The number of $k$-critical and $k$-vertex-critical
$(P_{5},dart)$-free graphs (for $k\in\\{5,6,7\\}$).

Figure 2: All 14 5-critical $(P_{5},dart)$-free graphs.

##  6 Conclusion

In this paper, we have proved that there are finitely many $k$-vertex-critical
$(P_{5},dart)$-free graphs for $k\geq 1$ and computationally determined an
exhaustive list of such graphs for $k\in\\{5,6,7\\}$. Our results gave an
affirmative answer to the problem posed in [8] for $H=dart$. In the future, it
is natural to investigate the finiteness of the set of $k$-vertex-critical
$(P_{5},H)$-free graphs for other graphs $H$ of order 5, see [7].

### Acknowledgements

The research of Jan Goedgebeur was supported by Internal Funds of KU Leuven.
Jorik Jooken is supported by a Postdoctoral Fellowship of the Research
Foundation Flanders (FWO). Shenwei Huang is supported by National Natural
Science Foundation of China (12171256).

## References

  * [1] J. A. Bondy and U. S. R. Murty.  Graph Theory.  Springer, 2008.
  * [2] D. Bruce, C. T. Hoàng and J. Sawada.  A certifying algorithm for 3-colorability of $P_{5}$-free graphs.  In Proceedings of 20th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 5878, pages 594–604, 2009.
  * [3] K. Coolsaet, S. D’hondt and J. Goedgebeur.  House of Graphs 2.0: A database of interesting graphs and more.  Discrete Appl. Mathematics, 325:97–107, 2023. Available at https://houseofgraphs.org
  * [4] Q. Cai, J. Goedgebeur and S. Huang.  Some results on $k$-critical $P_{5}$-free graphs.  Discrete Appl. Mathematics, 334:91–100, 2023.
  * [5] Q. Cai, S. Huang, T. Li and Y. Shi.  Vertex-critical ($P_{5}$,banner)-free graph.  In Yijia Chen, Xiaotie Deng, and Mei Lu, editors, Frontiers in Algorithmics -13th International Workshop, FAW 2019, Sanya, China, April 29-May 3, 2019, Proceedings, volume 11458 of Lecture Notes in Computer Science, pages 111–120, 2019.
  * [6] B. Cameron and C. T. Hoàng.  A refinement on the structure of vertex-critical $({P}_{5},gem)$-free graphs.  Theoretical Computer Science, 961:113936, 2023.
  * [7] B. Cameron and C. T. Hoàng.  Infinite families of $k$-vertex-critical ($P_{5},C_{5}$)-free graphs.  arXiv:2306.03376v1 [math.CO].
  * [8] K. Cameron, J. Goedgebeur, S. Huang and Y. Shi.  $k$-critical graphs in $P_{5}$-free graphs.  Theoretical Computer Science, 864:80–91, 2021.
  * [9] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas.  The strong perfect graph theorem.  Annals of Mathematics, 164:51–229, 2006.
  * [10] H. S. Dhaliwal, A. M. Hamel, C. T. Hoàng, F. Maffray, T. J. D. McConnell and S. A. Panait.  On color-critical (${P}_{5}$, co-${P_{5}}$)-free graphs.  Discrete Appl. Mathematics, 216:142–148, 2017.
  * [11] J. L. Fouquet.  A decomposition for a class of $(P_{5},\overline{P_{5}})$-free graphs.  Discrete Math., 121:75–83, 1993.
  * [12] J. Goedgebeur.  Homepage of generator for $k$-critical $\mathcal{H}$-free graphs: https://caagt.ugent.be/criticalpfree/.
  * [13] J. Goedgebeur and O. Schaudt.  Exhaustive generation of $k$-critical $\mathcal{H}$-free graphs.  J. Graph Theory, 87:188–207, 2018.
  * [14] P. Hell and S. Huang.  Complexity of coloring graphs without paths and cycles.  Discrete Appl. Mathematics, 216:211–232, 2017.
  * [15] C. T. Hoàng, M. Kamiński, V. V. Lozin, J. Sawada and X. Shu.  Deciding $k$-colorability of $P_{5}$-free graphs in polynomial time.  Algorithmica, 57:74–81, 2010.
  * [16] C. T. Hoàng, B. Moore, D. Recoskiez, J. Sawada and M. Vatshelle.  Constructions of $k$-critical ${P_{5}}$-free graphs.  Discrete Appl. Mathematics, 182:91–98, 2015.
  * [17] S. Huang, J. Li, and W. Xia.  Critical ($P_{5},bull$)-free graphs.  Discrete Appl. Mathematics, 334:15–25, 2023.
  * [18] S. Huang, T. Li and Y. Shi.  Critical ($P_{6}$,banner)-free graphs.  Discrete Appl. Mathematics, 258:143–151, 2019.
  * [19] S. Huang and Z. Li.  Vertex-critical ($P_{5},chair$)-free graphs.  Discrete Appl. Mathematics, 341:9–15, 2023.
  * [20] J. Jooken.  GitHub page containing generator for $k$-vertex-critical $\mathcal{H}$-free graphs: https://github.com/JorikJooken/kVertexCriticalGraphs.
  * [21] M. Kamiński and A. Pstrucha.  Certifying coloring algorithms for graphs without long induced paths.  Discrete Appl. Mathematics, 261:258–267, 2019.
  * [22] R. M. Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heigts, N.Y., 1972), pages 85–103, 1972.
  * [23] F. Maffray and G. Morel.  On 3-colorable $P_{5}$-free graphs.  SIAM J. Discrete Math., 26:1682–1708, 2012.