[a]Juliana Stachurska

# Going Big for Phase III of the Project 8 Neutrino Mass Experiment

###### Abstract

Project 8 is a next generation experiment aiming to directly measure the
neutrino mass using the tritium endpoint method with a targeted sensitivity of
40 meV. Having established a new measuring technique, Cyclotron Radiation
Emission Spectroscopy (CRES), the next development phase will demonstrate CRES
on a large source volume, culminating in a pilot-scale CRES experiment with
atomic tritium. A promising option is a mode-filtered, cylindrical, resonant
cavity in which cyclotron radiation from magnetically trapped beta electrons
only couples to the lowest eigenmode, maximizing effective volume and
minimizing signal complexity. Recent progress in the experiment design,
including a small scale cavity CRES proof-of-concept apparatus to demonstrate
CRES in cavities and its scalability to large volumes are described.

##  1 Direct Neutrino Mass Measurement with Project 8

The unknown absolute neutrino mass scale is one of the outstanding puzzles of
both particle physics and cosmology. Laboratory measurements of the tritium
beta decay spectrum endpoint region offer a direct and model-independent way
to measure the electron-weighted effective neutrino mass $m_{\beta}$, defined
as $m_{\beta}^{2}=\sum_{i}|U_{ei}|^{2}m_{i}^{2}$. Project 8 is a proposed
experiment using the tritium endpoint method and targeting a sensitivity of
$40\mathrm{\,meV}$, covering the entire mass range allowed in the inverted
mass ordering. Project 8 established Cyclotron Radiation Emission Spectroscopy
(CRES) [1], a non-destructive technique to measure electron energies [2] via

$f_{c}=\frac{1}{2\pi}\frac{e\langle B\rangle}{m_{e}+E/c^{2}},$ (1)

where $f_{c}$ is the frequency of cyclotron radiation emitted by electrons
with energy $E$ in a magnetic field $B$. Recently, the first CRES-based
neutrino mass upper limit was extracted from the tritium decay spectrum [3].
The next phase will establish atomic tritium production, cooling and trapping
– see [4] on recent progress on the atomic source –, and scale CRES to large
volumes.

##  2 A Cavity-Based CRES Experiment

Figure 1: Project 8 cavity concept with cavity (orange), multipole magnet for
atom trapping and pinch coils for electron trapping (red) and solenoid magnet
to induce cyclotron motion (blue). Electrons couple to the TE011 mode (grey),
read out from the center. The electron trapping field is shown on the left.

The initial phases of Project 8 detected CRES in a magnetic field with
strength of $\sim 1$ T, corresponding to a cyclotron frequency of $\sim 26$
GHz for electron energies of $\sim 18.6$ keV, close to the tritium endpoint,
using a WR-42 waveguide to guide the RF signal from the gas cell and the
electrons to the amplifier. The final Project 8 experiment will monitor a
large quantity of electrons released from atomic tritium beta decay, and thus
calls for a large detector volume. The low-field seeking hyperfine states of
atomic tritium will be confined by a combination of magnetic field walls and
gravity. Dipolar spin-flip leads to losses from the trap and requires CRES
fields much lower than $1$ T. However, the Larmor power of the emitted
cyclotron radiation depends on the frequency as $P\propto f_{c}^{2}$. Cavities
naturally provide large volumes at low resonant frequencies, while the Purcell
enhancement [5] can compensate for the lower radiated powers. The final
Project 8 experiment is currently being designed to use cavities with resonant
frequency of $325$ MHz as the detector volume. The design needs to be
compatible with atomic tritium operations, such as injecting a beam of atomic
tritium into it, as well as the introduction of calibration electrons. The
atomic tritium will be confined by a combination of magnetic fields and
gravity, necessitating a tall structure and a closely fitting magnet array
around the cavity. The chosen axial field of strength $11$ mT corresponds to
an electron cyclotron frequency of $f_{c}=325$ MHz at the tritium endpoint.
The electron is trapped axially by higher magnetic field walls from pinch
coils. Figure 1 shows the concept of a cavity CRES experiment. The mode used
is a TE011 mode, to which the readout is designed to achieve an appropriate
loaded $Q$, or, a resonance bandwidth covering the electron energy and pitch
angle range of interest. To maximize volume at the given frequency, the cavity
is 11 m tall at a diameter of 1.1 m.

##  3 The Cavity CRES Apparatus

Figure 2: Motion of axially trapped electrons in the cavity for large and
small pitch angles, and the resulting signal structure. Electrons with smaller
pitch angles will experience a higher magnetic field, leading to a higher
cyclotron frequency. The effect can be corrected by detecting the lower
sideband, a result of the pitch-angle dependent axial motion.

The first demonstration of the cavity-CRES viability will be at a field of $1$
T and a cyclotron frequency of $26$ GHz. This allows for the re-use of RF
equipment, software, as well as a $1$ T MRI magnet with excellent field
uniformity for better time and cost efficiency. The cavity will be read out
with a WR-42 waveguide. Two sources of CRES electrons will be used: an
electron gun, with electrons Mott-scattering inside the cavity on Helium gas,
and conversion electrons from 83mKr. The design of the cavity is open-ended,
and has the length-to-diameter ratio of $L/D=10$ of the final cavity concept.
The cavity CRES apparatus will establish cavities as CRES detectors, verifying
simulated signal structure and volume and pitch angle acceptance. To achieve
the desired energy resolution of $0.3$ eV, individual electrons’ experienced
magnetic fields need to be known with high precision. As noted in Equation 1,
the cyclotron frequency is a function of the average magnetic field the
electron experiences. Electrons with high pitch angles $\theta\approx
90^{\circ}$ have momenta almost orthogonal to the axial trapping field. They
will be able to move only in regions where the field is close to its lowest
value and experience $\langle B\rangle\approx B_{\mathrm{min}}$. Electrons
with lower pitch angles will be able to climb higher up the magnetic trapping
walls, leading to $\langle B\rangle>B_{\mathrm{min}}$, and thus to a higher
$f_{c}$. However, the axial frequency $f_{a}$ depends on the pitch angle and
the shape of the trapping field. The sidebands appearing at $f_{c}\pm
nf_{a},\,n=1,2,3,...$ can be used to correct for the higher average magnetic
field experienced. As $f_{c}$ increases with decreasing pitch angle, we will
use the lower sidebands for the field correction, which will stay within the
cavity bandwidth. The detection and reconstruction concept is illustrated in
Figure 2. The demonstrator is designed to trap and reconstruct electrons with
pitch angles $\geq 88^{\circ}$. In addition to establishing the electron gun
as a calibration device, 83mKr conversion electron lines will be measured.

##  4 Low-frequency CRES Detection

Development of the CRES technique to the lower magnetic fields needed for
atomic tritium trapping poses its own set of challenges due to the low
collected powers and the field homogeneity and stability requirements over
large volumes. We are designing a demonstrator for low-frequency and low-power
CRES detection around $1$ GHz, where the collected power will be on the order
of $10^{-18}$ W. While $1$ T magnets providing homogenous fields over a
significant volume are readily available commercially, this is not true at
much lower fields. The solenoid magnet providing the CRES field at $\sim 35$
mT will be custom-designed. With the successful operation of the low-frequency
CRES demonstrator, cavities will be established as large-volume CRES
detectors. This must include the demonstration of high resolution at low
power, necessitating the creation of a highly uniform, stable low magnetic
field with a custom magnet. Following the demonstrator’s success, the Phase-
III pilot atomic tritium experiment can be built with a cavity detector at a
resonant frequency of $325$ MHz, providing an $11$ m3 volume for low-density
atomic tritium gas. At a projected sensitivity of
$m_{\beta}<100\mathrm{\,meV}$ after one year of data taking, the pilot atomic
tritium neutrino mass experiment will be world-leading.

## References

  * [1] B. Monreal and J.A. Formaggio, _Relativistic cyclotron radiation detection of tritium decay electrons as a new technique for measuring the neutrino mass_ , _Physical Review D_ 80 (2009) .
  * [2] Project 8 collaboration, _Single electron detection and spectroscopy via relativistic cyclotron radiation_ , _Phys. Rev. Lett._ 114 (2015) 162501 [1408.5362].
  * [3] Project 8 collaboration, _Tritium Beta Spectrum Measurement and Neutrino Mass Limit from Cyclotron Radiation Emission Spectroscopy_ , _Phys. Rev. Lett._ 131 (2023) 102502 [2212.05048].
  * [4] L. Thorne for the Project 8 Collaboration, _Building an atomic source for the Project 8 experiment_ , in _XVIII International Conference on Topics in Astroparticle and Underground Physics (TAUP2023)_ , Proceedings of Science (2023).
  * [5] E.M. Purcell, _Proceedings of the american physical society_ , _Phys. Rev._ 69 (1946) 674.


# Minimal obstructions to $C_{5}$-coloring in hereditary graph classes

Jan GOEDGEBEUR111Department of Computer Science, KU Leuven Campus Kulak-
Kortrijk, 8500 Kortrijk, Belgium 222Department of Applied Mathematics,
Computer Science and Statistics, Ghent University, 9000 Ghent, Belgium , Jorik
JOOKEN11footnotemark: 1 , Karolina OKRASA333Warsaw University of Technology,
Poland ,
Paweł RZĄŻEWSKI444Warsaw University of Technology and University of Warsaw,
Poland , and Oliver SCHAUDT555University of Cologne, Germany 666E-mail
addresses<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

For graphs $G$ and $H$, an $H$-coloring of $G$ is an edge-preserving mapping
from $V(G)$ to $V(H)$. Note that if $H$ is the triangle, then $H$-colorings
are equivalent to $3$-colorings. In this paper we are interested in the case
that $H$ is the five-vertex cycle $C_{5}$.

A minimal obstruction to $C_{5}$-coloring is a graph that does not have a
$C_{5}$-coloring, but every proper induced subgraph thereof has a
$C_{5}$-coloring. In this paper we are interested in minimal obstructions to
$C_{5}$-coloring in $F$-free graphs, i.e., graphs that exclude some fixed
graph $F$ as an induced subgraph. Let $P_{t}$ denote the path on $t$ vertices,
and let $S_{a,b,c}$ denote the graph obtained from paths
$P_{a+1},P_{b+1},P_{c+1}$ by identifying one of their endvertices.

We show that there is only a finite number of minimal obstructions to
$C_{5}$-coloring among $F$-free graphs, where
$F\in\\{P_{8},S_{2,2,1},S_{3,1,1}\\}$ and explicitly determine all such
obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl.
Math. 261, 2019] who proved that there is only a finite number of $P_{7}$-free
minimal obstructions to $C_{5}$-coloring, and of Dębski et al. [ISAAC 2022
Proc.] who showed that the triangle is the unique $S_{2,1,1}$-free minimal
obstruction to $C_{5}$-coloring.

We complement our results with a construction of an infinite family of minimal
obstructions to $C_{5}$-coloring, which are simultaneously $P_{13}$-free and
$S_{2,2,2}$-free. We also discuss infinite families of $F$-free minimal
obstructions to $H$-coloring for other graphs $H$.

Keywords: graph homomorphism, critical graphs, hereditary graph classes

MSC 2020: 05C15, 05C85, 68W05, 68R10

##  1 Introduction

Out of a great number of interesting and elegant graph problems, the notion of
graph coloring is, arguably, among the most popular and well-studied ones, not
only from combinatorial, but also from algorithmic point of view. For an
integer $k\geq 1$, a _$k$ -coloring_ of a graph $G$ is a function
$c:V(G)\to\\{1,\ldots,k\\}$ such that for every edge $uv\in E(G)$ it holds
that $c(u)\neq c(v)$. For a fixed integer $k\geq 1$, the $k$-Coloring problem
is a computational problem in which an instance is a graph $G$ and we ask
whether there exists a $k$-coloring of $G$.

The $k$-Coloring problem is known to be polynomial-time solvable if $k\leq 2$
and NP-complete for larger values of $k$. Still, even if $k\geq 3$, it is
often possible to obtain polynomial-time algorithms that solve $k$-Coloring if
we somehow restrict the class of input instances, for example, to perfect
graphs [15, 16], bounded-treewidth graphs [2] or intersection graphs of
geometric objects [13].

Observe that these example classes are _hereditary_ , i.e., closed under
deleting vertices. Such a property is very useful in algorithm design, as it
combines well with standard algorithmic techniques, like branching or
divide-&-conquer. Therefore, if we want to study some computational problem in
a restricted graph class $\mathcal{G}$, choosing $\mathcal{G}$ to be
hereditary appears to be reasonable. For a fixed graph ${F}$, we say that a
graph $G$ is _$F$ -free_ if it does not contain $F$ as an induced subgraph. If
$\mathcal{F}$ is a family of graphs, we say that a graph $G$ is _$\mathcal{F}$
-free_ if $G$ is $F$-free for every $F\in\mathcal{F}$. Each hereditary class
of graphs can be characterized by a (possibly infinite) family $\mathcal{F}$
of forbidden induced subgraphs.

##### Coloring hereditary graph classes.

As a first step towards understanding the complexity of $k$-Coloring in
hereditary classes it is natural to consider classes defined by a single
induced subgraph $F$. If $F$ contains a cycle or a vertex of degree at least
3, it follows from the classical results by Emden-Weinert [11], Holyer [21],
and Leven and Galil [25] that for every $k\geq 3$, $k$-Coloring remains NP-
complete when restricted to $F$-free graphs. Thus we are left with the case
that $F$ is a _linear forest_ , i.e., every component of $F$ is a path.

However, if $F$ is a linear forest, the situation becomes more complicated.
For simplicity, let us focus on the case when $F$ is connected, i.e., $F$ is a
path on $t$ vertices, denoted by $P_{t}$. Then, $k$-Coloring is polynomial-
time-solvable in $P_{t}$-free graphs if $t\leq 5$, or if
$(k,t)\in\\{(3,6),(3,7),(4,6)\\}$ [22, 31, 3, 19]. On the other hand, for any
$k\geq 4$, the $k$-Coloring problem is NP-complete in $P_{t}$-free graphs for
all other values of $t$ [22]. The complexity of the remaining cases, i.e.,
$3$-Coloring of $P_{t}$-free graphs where $t\geq 8$, remains unknown: we do
not know polynomial-time algorithms nor any hardness proofs. The general
belief is that all these cases are in fact tractable, which is supported by
the existence of a quasipolynomial-time algorithm for $3$-Coloring in
$P_{t}$-free graphs, for every fixed $t$ [30]. For the summary of the results
on the complexity of $k$-Coloring $P_{t}$-free graphs see Figure 1. Let us
remark that there are also some results for disconnected forbidden linear
forests [24, 8].

##### Minimal obstructions to $k$-coloring.

One can look at $k$-Coloring from another, purely combinatorial perspective.
Instead of asking whether a graph $G$ admits a $k$-coloring, we can ask
whether it contains a _dual object_ , i.e., some structure that forces the
chromatic number to be at least $k+1$. For example, $2$-Coloring can be
equivalently expressed as a question whether a graph contains an odd cycle. As
another example, $k$-Coloring restricted to perfect graphs is equivalent to
the question of the existence of a $(k+1)$-clique, i.e., the complete graph on
$k+1$ vertices, denoted by $K_{k+1}$.

In other words, odd cycles are _minimal non-2-colorable graphs_ and
$(k+1)$-cliques are _minimal non- $k$-colorable perfect graphs_ (where
minimality is defined with respect to the induced subgraph relation).
Formally, if a graph $G$ is not $k$-colorable, but every proper induced
subgraph of it is $k$-colorable, we say that $G$ is _vertex- $(k+1)$-critical_
or is a _minimal obstruction to $k$-coloring_. We denote by
$\mathsf{Obstructions}(k)$ the set of all minimal obstructions to
$k$-coloring. Note that $\mathsf{Obstructions}(k)$ naturally forms a family of
dual objects—a graph is $k$-colorable if and only if it does not contain any
graph from $\mathsf{Obstructions}(k)$ as an induced subgraph.

Suppose that, for some $k$, there is a polynomial-time algorithm
$\mathsf{Alg}_{k}$ that takes as an input a graph $G$ and answers whether it
contains any graph from $\mathsf{Obstructions}(k)$ as an induced subgraph
(i.e., whether $G$ is _not_ $\mathsf{Obstructions}(k)$-free). From the
discussion above it follows that the existence of $\mathsf{Alg}_{k}$ yields a
polynomial-time algorithm for $k$-Coloring. Thus it is unlikely that
$\mathsf{Alg}_{k}$ exists for any $k\geq 3$. However, it is still possible
when we restrict the input graphs to a certain class $\mathcal{G}$ (like
perfect graphs in the example above). Recall that we are interested in the
case that $\mathcal{G}=F\text{-free}$, where $F$ is a path. Let us denote such
a restriction $\mathsf{Alg}_{k}$ to $F$-free graphs by $\mathsf{Alg}_{k,F}$.

Note that the existence of $\mathsf{Alg}_{k,F}$ is trivial if
$(\mathsf{Obstructions}(k)\cap F\text{-free})$ is finite; indeed, brute force
works in this case. This line of arguments allows us to further refine cases
that are polynomial-time solvable: into pairs $(k,F)$, where
$(\mathsf{Obstructions}(k)\cap F\text{-free})$ is finite, and the others.
Recall that the algorithm for $k$-Coloring obtained for the former ones is
able to produce a _negative certificate_ : a small (constant-size) witness
that the input graph is _not_ $k$-colorable. We refer the reader to the survey
of McConnell et al. [27] for more information about certifying algorithms.

It turns out that we can fully characterize all pairs $(k,F)$ for which
$\mathsf{Obstructions}(k)\cap F\text{-free}$ is finite. It is well-known that
$P_{4}$-free graphs (also known as _cographs_) are perfect and thus the only
minimal obstruction to $k$-coloring is the $(k+1)$-clique. Bruce et al. [4]
proved that there is a finite number of minimal obstructions to 3-coloring
among $P_{5}$-free graphs. The result was later extended by Chudnovsky et al.
[6] who showed that the family of $P_{6}$-free minimal obstructions to
3-coloring is is also finite, and that this is no longer true among
$P_{7}$-free graphs (and thus for $P_{t}$-free graphs for every $t\geq 7$). If
the number of colors is larger, things get more difficult faster: Hoàng et al.
[20] showed that for each $k\geq 4$ there exists an infinite family of
$P_{5}$-free minimal obstructions to $k$-coloring. See also Figure 1.

Figure 1: The complexity of $k$-Coloring $P_{t}$-free graphs.

#####  $H$-coloring $F$-free graphs and minimal obstructions to $H$-colorings.

Graph colorings can be seen as a special case of _graph homomorphisms_. For
graphs $G$ and $H$, an _$H$ -coloring_ of $G$ is a function $c:V(G)\to V(H)$
such that for every edge $uv\in E(G)$ it holds that $c(u)c(v)\in E(H)$. The
graph $H$ is usually called the _target graph_. It is straightforward to
verify that homomorphisms from $G$ to the $k$-clique, are in one-to-one
correspondence to $k$-colorings of $G$. For this reason one often refers to
the vertices of $H$ as _colors_.

For a fixed graph $H$, by $H$-Coloring we denote the computational problem
that takes as an input a graph $G$ and asks whether $G$ admits a homomorphism
to $H$. The complexity dichotomy for $H$-Coloring was proven by Hell and
Nešetřil [17]: the problem is polynomial-time solvable if $H$ is bipartite,
and NP-complete otherwise.

The complexity landscape of $H$-Coloring in $F$-free graphs for non-complete
target graphs is far from being fully understood. Chudnovsky et al. [7] proved
that if $H$ is an odd cycle on at least 5 vertices, then $H$-Coloring is
polynomial-time solvable in $P_{9}$-free graphs; they also showed a number of
hardness results for more general variants of the homomorphism problem. Feder
and Hell [12] and Dębski et al. [10] studied the case when $H$ is an _odd
wheel_ , i.e., an odd cycle with universal vertex added. The most general
algorithmic results were provided by Okrasa and Rzążewski [29] who showed that

  1. (OR1)

if $H$ does not contain $C_{4}$ as a subgraph, then $H$-Coloring can be solved
in quasipolynomial time in $P_{t}$-free graphs for any fixed $t$ (note that a
better running time here would also mean progress for $3$-Coloring
$P_{t}$-free graphs),

  2. (OR2)

if $H$ is of girth at least 5, then $H$-Coloring can be solved in
subexponential time in $F$-free graphs, where $F$ is any fixed _subdivided
claw_ , i.e., any graph obtained from the three-leaf star by subdividing
edges.

While these are not polynomial-time algorithms, no NP-hardness proofs for
these cases are known either. To complete the picture, from [29] it also
follows that if $H$ is a so-called _projective core_ that contains $C_{4}$ as
a subgraph, then there exists a $t$ such that $H$-Coloring is NP-complete in
$P_{t}$-free graphs (and thus also in graphs excluding some fixed subdivided
claw). Furthermore, the hardness reductions even exclude any subexponential-
time algorithms for these cases, assuming the Exponential Time Hypothesis
(ETH). Let us skip the definition of a projective core, as it is quite
technical and not really relevant for this paper. However, it is worth
pointing out that almost all graphs are projective cores [26, 18].

Since we are interested in a finer classification of polynomial-time-solvable
cases, we should be looking at pairs $(H,F)$ of graphs such that the
$H$-Coloring problem is _not_ known to be NP-complete in $F$-free graphs. From
the discussion above it follows that there are two natural families of such
pairs to consider:

  1. (i)

when $H$ does not contain $C_{4}$ as a subgraph and $F$ is a path,

  2. (ii)

when $H$ is of girth at least 5 and $F$ is a subdivided claw.

It is straightforward to generalize the notion of minimal obstructions to the
setting of $H$-colorings. A graph $G$ is called a _minimal obstruction to
$H$-coloring_ if there is no $H$-coloring of $G$, but every proper induced
subgraph of $G$ can be $H$-colored.

The area of minimal obstructions to $H$-coloring is rather unexplored. In the
setting of (i), Kamiński and Pstrucha [23] showed that for any $t\geq 5$,
there are finitely many minimal obstructions to $C_{t-2}$-coloring among
$P_{t}$-free graphs.777While in [23] the authors consider minimality with
respect to the _subgraph_ relation, it is not hard to observe that bounded
number of subgraph-minimal obstructions is equivalent to the bounded number of
induced-subgraph-minimal obstructions. In particular, the family of
$P_{7}$-free minimal obstructions to $C_{5}$-coloring is finite. In the
setting of (ii), Dębski et al. [10] showed that the triangle is the only
minimal obstruction to $C_{5}$-coloring among graphs that exclude the _fork_ ,
i.e., the graph obtained from the three-leaf star by subdividing one edge
once.

##### Our contribution.

As our first result, we show the following strengthening of the result of
Kamiński and Pstrucha.

######  Theorem 1.1.

There are 19 minimal obstructions to $C_{5}$-coloring among $P_{8}$-free
graphs.

Let us sketch the proof of Theorem 1.1. Note that $K_{3}$ is a minimal
obstruction for $C_{5}$-coloring, so from now on we focus on graphs that are
$\\{P_{8},K_{3}\\}$-free. For $i\in\\{1,2,3,4\\}$, by $Q_{i}$ we denote the
graph obtained from two copies of $C_{5}$ by identifying an $i$-vertex subpath
of one cycle with an $i$-vertex subpath of the other one, see Figure 2. In the
proof we separately consider minimal obstructions that contain some $Q_{i}$ as
an induced subgraph, and those that are $\\{Q_{1},Q_{2},Q_{3},Q_{4}\\}$-free.

Figure 2: Graphs $Q_{1},Q_{2},Q_{3}$, and $Q_{4}$ (left to right).

The intuition behind this is as follows. Notice that if $G$ contains an
induced 5-vertex cycle, the vertices of this cycle must be mapped to the
vertices of $C_{5}$ bijectively, respecting the ordering along the cycle.
Consequently, if $G$ contains some $Q_{i}$, the colorings of the vertices in
$Q_{i}$ are somehow restricted. Combining several $Q_{i}$’s we might impose
some contradictory constraints and thus build a graph that is not
$C_{5}$-colorable. However, as each $Q_{i}$ already contains quite long
induced paths, we might hope that by combining several $Q_{i}$ we are either
forced to create an induced $P_{8}$ (if we add only few edges between
different $Q_{i}$’s) or $K_{3}$ (if we add too many such edges). Thus the
possibilities of building non-$C_{5}$-colorable graphs using this approach are
somehow limited. It turns out that this intuition is correct: there are 18
graphs that are $\\{P_{8},K_{3}\\}$-free and contain $Q_{i}$, for some
$i\in\\{1,2,3,4\\}$, as an induced subgraph. Together with $K_{3}$, they are
shown in Figure 3. This part of the proof is computer-aided.

Figure 3: All $P_{8}$-free minimal obstructions to $C_{5}$-coloring. The
graphs in the first row are $P_{6}$-free. The graphs in the second row are
$P_{7}$-free, but not $P_{6}$-free. All other graphs are $P_{8}$-free, but not
$P_{7}$-free.

For the second step, we assume that our graph does not contain any $Q_{i}$,
i.e., we consider graphs that are
$\\{P_{8},K_{3},Q_{1},Q_{2},Q_{3},Q_{4}\\}$-free. We show that such graphs are
always $C_{5}$-colorable. Consequently, each minimal obstruction to
$C_{5}$-coloring (and, in general, every graph that is not $C_{5}$-colorable)
was discovered in step 1.

Before we discuss the second result, let us introduce the notation for
subdivided claws. For integers $a,b,c\geq 1$, by $S_{a,b,c}$ we denote the
graph obtained from the three-leaf star by subdividing each edge,
respectively, $a-1$, $b-1$, and $c-1$ times. Equivalently, $S_{a,b,c}$ is
obtained from three paths $P_{a+1},P_{b+1},P_{c+1}$ by identifying one of
their endpoints.

Figure 4: All $S_{2,2,1}$-free and all $S_{3,1,1}$-free minimal obstructions
to $C_{5}$-coloring. The graphs in the first row are both $S_{2,2,1}$-free and
$S_{3,1,1}$-free, whereas the first three graphs in the second row are
$S_{3,1,1}$-free, but not $S_{2,2,1}$-free and the last graph in the second
row is $S_{2,2,1}$-free, but not $S_{3,1,1}$-free.

As our second result we show the following extension of the result of Dębski
et al. [10].

######  Theorem 1.2.

There are 3 minimal obstructions to $C_{5}$-coloring among $S_{2,2,1}$-free
graphs, and 5 minimal obstructions to $C_{5}$-coloring among $S_{3,1,1}$-free
graphs.

These graphs are shown in Figure 4. The proof is similar to the proof of
Theorem 1.1. First, we consider minimal obstructions that contain an induced
$C_{5}$ and, using the computer search, we show that there is only a finite
number of them. Then, we show that graphs that exclude $K_{3}$ (as it is a
minimal obstruction by itself), $C_{5}$, and also one of
$S_{2,2,1},S_{3,1,1}$, are either bipartite or are “blown-up cycles” – in both
cases $C_{5}$-colorability is straightforward to show.

We complement these results with a construction of an infinite family of
minimal obstructions to $C_{5}$-coloring.

######  Theorem 1.3.

There is an infinite family of minimal obstructions to $C_{5}$-coloring, which
simultaneously exclude $P_{13}$, $S_{2,2,2}$, $S_{5,5,1}$, $S_{11,1,1}$, and
$S_{8,2,1}$ as an induced subgraph.

The construction from Theorem 1.3 is obtained by generalizing the infinite
family of $P_{7}$-free minimal obstructions to 3-coloring, provided by
Chudnovsky et al. [6]. The idea can be further generalized. Let the odd girth
of $H$ be the length of a shortest odd cycle in $H$ (and keep it undefined for
bipartite graphs).

######  Theorem 1.4.

Let $q\geq 3$ be odd, and let $H$ be a graph of odd girth $q$ that does not
contain $C_{4}$ as a subgraph. There is an infinite family of minimal
obstructions to $H$-coloring that are
$\\{P_{3q-1},S_{2,2,2},S_{\nicefrac{{3(q-1)}}{{2}},\nicefrac{{3(q-1)}}{{2}},1}\\}$-free.

Note that Theorem 1.4 gives a bound for every graph $H$ that was discussed in
(OR1) and (OR2). An astute reader might notice that applying Theorem 1.4 for
$H=C_{5}$, i.e., $q=5$, yields a family of obstructions that are in particular
$P_{14}$-free and $S_{6,6,1}$-free, which does not match the bounds from
Theorem 1.3. Indeed, obtaining the refined result from Theorem 1.3 requires
some additional work, which again uses a mixture of combinatorial observations
and computer search.

##### Organization of the paper.

In Section 2 we introduce some notation and preliminary observations. In
Section 3 we explain the algorithm that is later used to generate minimal
obstructions. In Section 4 we prove Theorem 1.1. In Section 5 we prove Theorem
1.2. In Section 6 we provide constructions of infinite families of graphs that
are then used to prove Theorems 1.3 and 1.4. Finally, in the Appendix, we
discuss implementation details of our algorithms and how they were tested for
correctness.

##  2 Preliminaries

For an integer $n\geq 1$ we denote by $[n]$ the set $\\{1,\ldots,n\\}$, and by
$[n]_{0}$ the set $[n]\cup\\{0\\}$. For a graph $G=(V,E)$ and a vertex set
$U\subseteq V$, the graph $G[U]$ denotes the subgraph of $G$ induced by $U$.
The graph $G-U$ denotes $G[V(G)\setminus U]$. The set $N_{G}(u)$ denotes the
neighborhood of vertex $u$ in the graph $G$. For $U\subseteq V(G)$ we define
$N_{G}(U)=\bigcup_{u\in U}N_{G}(u)\setminus U$. If the graph $G$ is clear from
the context, we omit the subscript and write $N(u)$ and $N(U)$.

If there exists an $H$-coloring of $G$, we denote this fact by $G\to H$. It is
straightforward to verify that if $G\to H$, then $\textsf{odd-
girth}(G)\geq\textsf{odd-girth}(H)$. In particular, $K_{3}$ has no
$C_{5}$-coloring and is actually a minimal obstruction to $C_{5}$-coloring.
Consequently, every other minimal obstruction to $C_{5}$-coloring is
$K_{3}$-free.

For any two graphs $G$ and $H$ such that $G$ is $H$-colorable, the graph
$\mathsf{hull}(G,H)$ denotes the graph with vertex set $V(G)$ and edge set
$\\{uv:u,v\in V(G)\text{ and for every }H\text{-coloring }c$ $\text{ of
}G\text{, we have }c(u)c(v)\in E(H)\\}$. Note that $\mathsf{hull}(G,H)$ is a
supergraph of $G$ that is $H$-colorable and that for every induced subgraph
$G^{\prime}$ of $G$ we have $E(\mathsf{hull}(G^{\prime},H))\subseteq
E(\mathsf{hull}(G,H))$. Note that $\mathsf{hull}(G,H)$ might contain some
induced subgraphs that do not appear in $G$.

##  3 Generating $F$-free minimal obstructions to $H$-coloring

In this section we describe an algorithm that can be used to generate all
$F$-free minimal obstructions to $H$-coloring. We emphasize that this approach
is robust in the sense that it does not assume that $H=C_{5}$ and $F$ is a
path or a subdivided claw, as needed for Theorems 1.1 and 1.2.

Throughout the section graphs $H$ and $F$ are fixed. We will use the term
_minimal obstruction_ for _minimal obstruction to $H$-coloring_. The algorithm
takes as an input “the current candidate graph” $I$ that it tries to extend to
a minimal obstruction by adding a new vertex $x$ and some edges between $x$
and $V(I)$. In particular, the algorithm can be used to generate all $F$-free
minimal obstructions by choosing $I$ as the single-vertex graph. This
algorithm is similar to the algorithm for $k$-Coloring by [14], but we
formulate it in a more general way. In case there are infinitely many minimal
obstructions, the generation algorithm will never terminate. If there are only
finitely many minimal obstructions, then the algorithm might still not
terminate, since the prunning rules might not be strong enough. However, if
the algorithm terminates, it is guaranteed that there are only finitely many
minimal obstructions and that the algorithm outputs all of them.

Let us explain the algorithm, see also the pseudocode in Algorithm 1. It
starts from a graph $I$ and recursively expands this graph by adding a vertex
and edges between this new vertex and existing vertices in each recursive
step. The expansion is based on expansion rules that aim at reducing the
search space while ensuring that no minimal obstructions are lost in this
operation. For example, if an expansion leads to a graph $I^{\prime}$ that is
not $F$-free, the recursion can be stopped, because all further expansions of
$I^{\prime}$ will not be $F$-free either (note that we do not add any edges
inside $V(I)$ and that the class of $F$-free graphs is hereditary). Another
way to restrict the search space is based on Lemma 3.1. This lemma and its
proof follow Lemma 5 from [6] concerning $k$-Coloring, but generalizing it to
$H$-Coloring required some adjustments.

######  Lemma 3.1.

Let $G=(V,E)$ be a minimal obstruction to $H$-coloring and let $U$ and $W$ be
two non-empty disjoint vertex subsets of $G$. Let $J:=\mathsf{hull}(G-U,H)$.
If there exists a homomorphism $\phi$ from $G[U]$ to $J[W]$, then there exists
a vertex $u\in U$ for which $N_{G}(u)\setminus U\nsubseteq N_{J}(\phi(u))$.

###### Proof.

Suppose that $N_{G}(u)\setminus U\subseteq N_{J}(\phi(u))$ for all $u\in U$.
Recall that $J$ admits an $H$-coloring, fix one and call it $c$. Hence, for
each $u\in U$ and each $v\in N_{J}(\phi(u))$ there is an edge
$c(\phi(u))c(v)\in E(H)$. Extend $c$ so that its domain is $V(G)$ by mapping
any $u\in U$ to $c(\phi(u))$. We now show that $c$ is an $H$-coloring of $G$.
For contradiction, suppose there is an edge $uv\in V(G)$, so that
$c(u)c(v)\notin E(H)$. By symmetry, assume that $u\in U$, as $c$ restricted to
$J$ is an $H$-coloring.

If $v\in I$, then $c(u)c(v)=c(\phi(u))c(\phi(v))\in E(H)$ as, again, $c$
restricted to $J$ is an $H$-coloring. Thus assume that $v\in N_{G}(u)\setminus
U$. Since $N_{G}(u)\setminus U\subseteq N_{J}(\phi(u))$, we obtain
$c(u)c(v)=c(\phi(u))c(v)\in E(H)$. This is a contradiction that $G$ is an
obstruction to $H$-coloring. ∎

As isomorphism is a special type of a homomorphism, Lemma 3.1 immediately
yields the following corollary.

######  Corollary 3.2.

Let $G$ be an $H$-colorable graph that is an induced subgraph of a minimal
obstruction $G^{\prime}$. Let $U,W\subseteq V(G)$ be two non-empty disjoint
vertex subsets and let $J:=\mathsf{hull}(G-U,H)$. If there exists an
isomorphism $\phi:G[U]\rightarrow J[W]$ such that $N_{G}(u)\setminus
U\subseteq N_{J}(\phi(u))$ for all $u\in U$, then there exists a vertex $x\in
V(G^{\prime})\setminus V(G)$ such that $x$ is adjacent to some vertex $u\in
U$, but $x$ is not adjacent to $\phi(u)$ in $\mathsf{hull}(G^{\prime}-U,H)$
(and thus also not adjacent to $\phi(u)$ in
$\mathsf{hull}(G^{\prime}[V(G)\cup\\{x\\}\setminus U],H)$).

Actually, we will only use the restricted version of Corollary 3.2. In what
follows we use the notation and assumptions of the Corollary. In case that
$|U|=|W|=1$, say $U=\\{u\\}$ and $W=\\{w\\}$, we call the pair $(u,w)$
comparable vertices. In case that $G[U]$ and $J[W]$ are both isomorphic to
$K_{2}$ and, say, $U=\\{u,u^{\prime}\\}$ and $W=\\{w,w^{\prime}\\}$, we call
the pair $(uu^{\prime},ww^{\prime})$ comparable edges. The algorithm
concentrates on finding comparable vertices and edges for computational
reasons.

Constants : target graph $H$, forbidden graph $F$

Input : current graph $I$

Output : exhaustive list of $F$-free minimal obstructions to $H$-coloring

1 if  _$I$ is $F$-free and not generated before_ then

2 if  _$I$ is not $H$-colorable_ then

3 if  _$I$ is a minimal obstruction to $H$-coloring_ then output $I$

4

5

6else

7 if  _$I$ contains comparable vertices $(u,v)$_ then

8 foreach  _graph $I^{\prime}$ obtained from $I$ by adding a new vertex $x$
and edges between $x$ and vertices in $V(I)$ in all possible ways, such that
$ux\in E(I^{\prime})$, but $vx\notin E(\mathsf{hull}(I^{\prime}-u,H))$_ do

9 Expand(_$I^{\prime}$_)

10

11 else if  _$I$ contains comparable edges $(uv,u^{\prime}v^{\prime})$_ then

12 foreach  _graph $I^{\prime}$ obtained from $I$ by adding a new vertex $x$
and edges between $x$ and vertices in $V(I)$ in all possible ways, such that
$rx\in E(I^{\prime})$, but $r^{\prime}x\notin
E(\mathsf{hull}(I^{\prime}-\\{u,v\\},H)))$ for some $r\in\\{u,v\\}$_ do

13 Expand(_$I^{\prime}$_)

14

15 else

16 foreach  _graph $I^{\prime}$ obtained from $I$ by adding a new vertex $x$
and edges between $x$ and vertices in $V(I)$ in all possible ways_ do

17 Expand(_$I^{\prime}$_)

18

19

Algorithm 1 Expand

We refer the interested reader to the Appendix for additional details about
the efficient implementation of this algorithm, independent correctness
verifications and sanity checks.

##  4 Minimal obstructions to $C_{5}$-coloring with no long paths

In this section we still only discuss $C_{5}$-colorings, thus we will keep
writing _minimal obstructions_ for _minimal obstructions for
$C_{5}$-coloring_.

The algorithm from Section 3 was implemented for $H=C_{5}$ (the source code is
made publicly available at [1]). We used the algorithm, combined with some
purely combinatorial observations, to generate an exhaustive list of
$P_{t}$-free minimal obstructions, where $t\leq 8$; see also Figure 3 and
Table 1. The minimal obstructions can also be obtained from the database of
interesting graphs at the House of Graphs [9] by searching for the keywords
“minimal obstruction to C5-coloring”.

$n$\$t$ | 6 | 7 | 8
---|---|---|---
3 | 1 | 1 | 1
4 | 0 | 0 | 0
5 | 0 | 0 | 0
6 | 0 | 0 | 0
7 | 0 | 0 | 0
8 | 3 | 4 | 4
9 | 0 | 0 | 1
10 | 0 | 0 | 1
11 | 0 | 0 | 0
12 | 0 | 0 | 0
13 | 0 | 1 | 12
Total | 4 | 6 | 19
Table 1: The number of $P_{t}$-free minimal obstructions for $C_{5}$-coloring.

###  4.1 $P_{t}$-free minimal obstructions for $t\in\\{6,7\\}$

As a warm-up, let us reprove the result of Kamiński and Pstrucha [23] (in a
slightly stronger form, as they did not provide the explicit list of minimal
obstructions). It will also serve as a demonstration of the way how Algorithm
1 is intended to be used.

An exhaustive list for $t\leq 6$ can be obtained by running the algorithm from
Section 3 with parameters $(I=K_{1},H=C_{5},F=P_{6})$.888Let us remark that it
is a simple exercise to find this list by hand. This leads to the following
observation.

######  Observation 4.1.

There are four minimal obstructions for $C_{5}$-coloring among $P_{6}$-free
graphs. All of these obstructions, except for the triangle $K_{3}$, are
$P_{6}$-free and not $P_{5}$-free.

Unfortunately, the same simple strategy already fails for $t=7$. Indeed, the
algorithm as presented in Section 3 does not terminate after running for
several hours after calling it with parameters $(I=K_{1},H=C_{5},F=P_{7})$.
However, with relatively small adjustments, the algorithm is able to produce
an exhaustive list of minimal obstructions in a few seconds.

The first adjustment has to do with the order in which the expansion rules are
used. Note that the order in which the algorithm checks whether it can find
comparable vertices and comparable edges does not affect the correctness of
the algorithm, but it might affect whether the algorithm terminates or not.
For example, it could happen that by expanding in order to get rid of a pair
of comparable vertices, a new pair of comparable vertices is introduced (and
this could continue indefinitely). By applying a different expansion rule
first, this can be avoided sometimes. For $F=P_{7}$, the algorithm was run by
first looking for comparable vertices and then for comparable edges, except
when $|V(I)|=10$, in which case the algorithm first looks for comparable edges
and then for comparable vertices.

The second adjustment is based on the following observation.

######  Observation 4.2.

Every $P_{7}$-free minimal obstruction to $C_{5}$-coloring, except for the
graph $K_{3}$, contains the cycle $C_{5}$ or the cycle $C_{7}$ as an induced
subgraph.

###### Proof.

Let $G$ be $P_{7}$-free minimal obstruction such that $G\neq K_{3}$. Note that
$G$ is not bipartite, as every $K_{2}$-coloring (i.e., 2-coloring) of $G$ is
also a $C_{5}$-coloring of $G$. Hence, $G$ contains an odd cycle as an induced
subgraph. Let $C$ be the shortest such cycle, and let $k=|V(C)|$. Note that
$k>3$. Indeed, $C_{3}=K_{3}$ is not $C_{5}$-colorable, so by minimality, $G$
cannot contain it as a proper subgraph, and $G$ is not a triangle itself by
assumption. On the other hand, any induced cycle on at least $8$ vertices
contains $P_{7}$ as an induced subgraph. Thus $k\in\\{5,7\\}$. ∎

By Observation 4.2, the set of $P_{7}$-free minimal obstructions can be
partitioned into three subsets:

  1. (i)

the triangle $K_{3}$,

  2. (ii)

minimal obstructions that are $P_{7}$-free but contain $C_{5}$ as an induced
subgraph,

  3. (iii)

minimal obstructions that are $P_{7}$-free but contain $C_{7}$ as an induced
subgraph.

Thus, running the algorithm for $(I=C_{5},H=C_{5},F=P_{7})$ and
$(I=C_{7},H=C_{5},F=P_{7})$, respectively, we can generate the families (ii)
and (iii). This yields the following result; recall that the finiteness of the
family of minimal obstructions was already shown by Kamiński and Pstrucha
[23].

######  Observation 4.3.

There are six $P_{7}$-free minimal obstructions to $C_{5}$-coloring. Two of
these obstructions are $P_{7}$-free, but not $P_{6}$-free.

###  4.2 $P_{8}$-free minimal obstructions

This section is devoted to the proof of Theorem 1.1, which we restate below
(see also Figure 3).

See 1.1

Similarly to the $P_{7}$-free case, the proof uses the algorithm from Section
3, but this time it requires a lot more purely combinatorial insight. For
$i\in[4]$, let $Q_{i}$ be the graph obtained from two disjoint copies of
$C_{5}$ by identifying $i$ pairs of consecutive corresponding vertices of the
cycles (see Figure 2).

Let $G$ be a $P_{8}$-free minimal obstruction; we aim to understand the
structure of $G$ and show that is must be one of 19 graphs in Figure 3. We
split the reasoning into two cases: first, we assume that $G$ contains
$Q_{i}$, for some $i\in[4]$, as an induced subgraph. Then, in the second case,
we assume that $G$ is $\\{Q_{1},Q_{2},Q_{3},Q_{4}\\}$-free.

#### Case 1: $G$ contains $Q_{i}$ for some $i\in[4]$ as an induced subgraph

We deal with this case using the algorithm from Section 3. The algorithm
terminates in a few minutes when it is called with the parameters
$(I=Q_{i},H=C_{5},F=P_{8})$ for all $i\in[4]$. All minimal obstructions
obtained this way are listed in Figure 3.

#### Case 2: $G$ does not contain $Q_{i}$ for any $i\in[4]$

Note that as $K_{3}$ is a minimal obstruction, from now on we will assume that
$G$ is $\\{P_{8},K_{3},Q_{1},Q_{2},Q_{3},Q_{4}\\}$-free. We aim to show that
all such graphs are $C_{5}$-colorable, i.e., the list obtained in Case 1, plus
the triangle, is exhaustive.

######  Lemma 4.4.

Let $G$ be a $\\{P_{8},K_{3},Q_{1},Q_{2},Q_{3},Q_{4}\\}$-free graph. Then $G$
is $C_{5}$-colorable.

###### Proof.

Without loss of generality we can assume that $G$ is connected, as otherwise
we can treat each component separately. Clearly, if $G$ is bipartite, then
$G\to C_{5}$, thus we can assume that $G$ contains an odd cycle. Consider a
shortest such cycle in $G$; note that it is induced. As $G$ is
$\\{P_{8},K_{3}\\}$-free, we observe that this cycle has either five or seven
vertices.

Thus, we distinguish two cases: either $G$ contains an induced $C_{5}$ or $G$
contains an induced $C_{7}$ and is $C_{5}$-free.

##### Case 2A: $G$ has an induced $C_{5}$.

Fix an induced copy of $C_{5}$ in $G$ and denote its consecutive vertices by
$c_{1},\ldots,c_{5}$. All computations on indices are performed modulo 5. We
also denote $C=\\{c_{1},\ldots,c_{5}\\}$. Let
$A_{i}=N(c_{i})\setminus\\{c_{i-1},c_{i+1}\\}$, and let
$A=N(C)=\bigcup_{i=1}^{5}A_{i}$.

######  Claim 4.4.1.

For each $v\in A$ there exists a unique $i\in[5]$ such that $v\in A_{i}$.
Moreover, for every $i\in[5]$ and every $v\in A_{i}$, we have that $N(v)\cap
A\subseteq A_{i-1}\cup A_{i+1}$.

_Proof of Claim._ First, we observe that if $v\in A_{i}\cap A_{i+1}$ for some
$i\in[5]$, then $v,c_{i},c_{i+1}$ is a triangle in $G$, a contradiction.
Similarly, if $v\in A_{i}\cap A_{i+2}$, then the set $C\cup\\{v\\}$ induces a
copy of $Q_{4}$ in $G$, a contradiction. This proves the first statement of
the claim.

For the second statement, consider $v\in A_{i}$ and $u\in N(v)\cap A$. If
$u\in A_{i}$, then $v,u,c_{i}$ is again a triangle in $G$, a contradiction. On
the other hand, if $u\in A_{i+2}$ (or, by symmetry, $u\in A_{i-2}$), then
$C\cup\\{v,u\\}$ induces a copy of $Q_{3}$ in $G$, a contradiction.
$\blacksquare$

By the claim above we obtain in particular that $(A_{1},\ldots,A_{5})$ is a
partition of $A$. Let $B=N(C\cup A)$ and $T=N(C\cup A\cup B)$. In other words,
$B$ (resp. $T$) contains vertices at distance exactly 2 (resp. 3) from $C$.

We note that $V(G)=C\cup A\cup B\cup T$. Suppose otherwise. By connectivity of
$G$, there is $v_{1}\notin C\cup A\cup B\cup T$ with a neighbor $v_{2}\in T$.
Let $v_{3}$ be a neighbor of $v_{2}$ in $B$, $v_{4}$ be a neighbor of $v_{3}$
in $A$, and $c_{i}$ be the unique neighbor of $v_{4}$ in $C$. Then
$(v_{1},v_{2},v_{3},v_{4},c_{i},c_{i+1},c_{i+2},c_{i+3})$ is an induced
$P_{8}$ in $G$, a contradiction.

######  Claim 4.4.2.

The set $T$ is independent.

_Proof of Claim._ For contradiction assume otherwise, and let $u,v\in T$ be
adjacent. By the definition of $T$, there exists $v_{1}\in B\cap N(v)$ and
$v_{2}\in A\cap N(v_{1})$. Let $c_{i}$ be the unique neighbor of $v_{2}$ in
$C$. As $G$ is triangle-free, $uv_{1}\notin E(G)$. Thus
$(u,v,v_{1},v_{2},c_{i},c_{i+1},c_{i+2},c_{i+3})$ is an induced $P_{8}$, a
contradiction. $\blacksquare$

######  Claim 4.4.3.

For each $v\in B$ there exists a unique $i\in[5]$ such that $N(v)\cap
A\subseteq A_{i-1}\cup A_{i+1}$.

_Proof of Claim._ Observe that if there exists $i\in[5]$, $u\in A_{i}\cap
N(v)$ and $u^{\prime}\in A_{i+1}\cap N(v)$, then either $v,u,u^{\prime}$ is a
triangle or $C\cup\\{v,u,u^{\prime}\\}$ induces $Q_{2}$ in $G$, a
contradiction. Thus $N(v)\cap A$ intersects at most two sets $A_{i},A_{j}$ for
some distinct $i,j\in[5]$, and, moreover, $|i-j|\neq 1$. The claim follows.
$\blacksquare$

For each $i\in[5]$ define $B_{i}=\\{v\in B\leavevmode\nobreak\
|\leavevmode\nobreak\ N(v)\cap A\subseteq A_{i}\\}$ and
$B_{i-1,i+1}=B_{i+1,i-1}=\\{v\in B\leavevmode\nobreak\ |\leavevmode\nobreak\
N(v)\cap A_{i-1}\neq\emptyset,N(v)\cap A_{i+1}\neq\emptyset\\}$. Let
$\mathcal{B}=\\{B_{i}\\}_{i\in[5]}\cup\\{B_{i-1,i+1}\\}_{i\in[5]}$.

######  Claim 4.4.4.

For each $i\in[5]$ the set $B_{i}\cup B_{i,i-2}\cup B_{i,i+2}$ is independent.

_Proof of Claim._ If $u,v\in B_{i}\cup B_{i,i-2}\cup B_{i,i+2}$, then there
exist $u^{\prime}$ and $v^{\prime}$ in $A_{i}$ such that
$uu^{\prime},vv^{\prime}\in E(G)$. If now $uv\in E(G)$, then either
$u,v,u^{\prime}$ is a triangle in $G$ (if $u^{\prime}=v^{\prime}$) or
$C\cup\\{u,v,u^{\prime},v^{\prime}\\}$ induces a copy of $Q_{1}$ in $G$, in
both cases we reach a contradiction. Thus $B_{i}\cup B_{i,i-2}\cup B_{i,i+2}$
is an independent set. $\blacksquare$

######  Claim 4.4.5.

Every $t\in T$ has neighbors in at most one of the sets in $\mathcal{B}$.

_Proof of Claim._ First, suppose that $t$ has a neighbor $b_{1}$ in $B_{i}$
for $i\in[5]$, by symmetry we can assume that $i=1$. For contradiction suppose
that $b^{\prime}$ is a neighbor of $t$ in $B\setminus B_{1}$, and let $a_{1}$
be a neighbor of $b_{1}$ in $A_{1}$. As $G$ is triangle-free, we have
$b_{1}b^{\prime}\notin E(G)$. Now if $a_{1}b^{\prime}\notin E(G)$, then
$(b^{\prime},t,b_{1},a_{1},c_{1},c_{2},c_{3},c_{4})$ is an induced $P_{8}$ in
$G$. So assume that $a_{1}b^{\prime}\in E(G)$. In particular, $b^{\prime}\in
B_{1,3}$ or $b^{\prime}\in B_{1,4}$. By symmetry assume the former and let
$a_{3}\in N(b^{\prime})\cap A_{3}$. Then
$(b_{1},t,b^{\prime},a_{3},c_{3},c_{4},c_{5},c_{1})$ is an induced $P_{8}$ in
$G$. In both cases we reach a contradiction.

So from now on we assume that $t$ has no neighbor in $\bigcup_{i=1}^{5}B_{i}$.
By symmetry assume that there is $b_{2,5}\in B_{2,5}\cap N(t)$ and let
$a_{i}\in N(b_{2,5})\cap A_{i}$ for $i\in\\{2,5\\}$. Suppose that $A_{3}\cup
A_{4}\neq\emptyset$, say $a_{4}\in A_{4}$ (the case with $A_{3}\neq\emptyset$
is symmetric). By Claim 4.4.1 we observe that $a_{2}a_{4}\notin E(G)$. This
means that $(t,b_{2,5},a_{2},c_{2},c_{1},c_{5},c_{4},a_{4})$ is an induced
$P_{8}$ in $G$, a contradiction.

Thus $A_{3}\cup A_{4}=\emptyset$, so in particular $B_{1,3}\cup B_{2,4}\cup
B_{1,4}\cup B_{3,5}=\emptyset$. This means that
$B=B_{2,5}\cup\bigcup_{i=1}^{5}B_{i}$, so indeed $t$ has no neighbors in $B$
outside $B_{2,5}$. $\blacksquare$

We obtain the following.

######  Claim 4.4.6.

If $h:G-T\to C_{5}$ is a homomorphism, in which for every
$\widetilde{B}\in\mathcal{B}$ there is $i\in[5]$ such that
$h(\widetilde{B})=i$, then $h$ can be extended to a homomorphism from $G$ to
$C_{5}$.

_Proof of Claim._ Note that by Claim 4.4.5 for every $t\in T$ there is
$i\in[5]$ such that all neighbors of $t$ are mapped to $i$. Then we can map
such $t$ to $i+1$; this will not create any wrongly mapped edge as $T$ is
independent by Claim 4.4.2. $\blacksquare$

##### Subcase 2A.1: There exists $i\in[5]$ and $b_{i}\in B_{i},b_{i+2}\in
B_{i+2}$ such that $b_{i}b_{i+2}\in E(G)$.

By symmetry assume that $i=1$. For $i\in\\{1,3\\}$, let $a_{i}$ be a vertex in
$N(b_{i})\cap A_{i}$. If $A_{4}\cup A_{5}\neq\emptyset$, say, there is
$a_{4}\in A_{4}$, then $(a_{4},c_{4},c_{3},c_{2},c_{1},a_{1},b_{1},b_{3})$ is
an induced $P_{8}$ in $G$, a contradiction. Thus $A_{4}=A_{5}=\emptyset$.
Consequently, $B=B_{1}\cup B_{2}\cup B_{3}\cup B_{1,3}$.

######  Claim 4.4.7.

There are no edges between $B_{2}$ and $B_{1,3}\cup B_{1}\cup B_{3}$.

_Proof of Claim._ Assume otherwise, and let $b_{2}b$ be an edge such that
$b_{2}\in B_{2}$ and $b\in B_{1,3}\cup B_{1}\cup B_{3}$. Let $a_{2}\in
A_{2}\cap N(b_{2})$.

If $b\in B_{1}$ (or $b\in B_{3}$ by symmetry), then there is
$a^{\prime}_{1}\in N(b)\cap A_{1}$. But this means that
$(b_{2},b,a_{1}^{\prime},c_{1},c_{5},c_{4},c_{3},a_{3})$ induces $P_{8}$ in
$G$, a contradiction. Thus $b\in B_{1,3}$. Choose any $a^{\prime}_{3}\in
A_{3}\cap N(b)$, $a^{\prime}_{1}\in A_{1}\cap N(b)$, if possible selecting
$a^{\prime}_{1}$ and $a^{\prime}_{3}$ to be the neighbors of, respectively,
$b_{1}$ and $b_{3}$.

Assume that $a^{\prime}_{1}\in N(b_{1})$ and $a^{\prime}_{3}\in N(b_{3})$. If
$a^{\prime}_{1}a_{2}\notin E(G)$ (or, by symmetry, $a^{\prime}_{3}a_{2}\notin
E(G)$) then $(a^{\prime}_{1},b,b_{2},a_{2},c_{2},c_{3},c_{4},c_{5})$ is an
induced $P_{8}$ in $G$, a contradiction. Thus
$a^{\prime}_{1}a_{2},a^{\prime}_{3}a_{2}\in E(G)$. But now
$\\{a^{\prime}_{1},b,a^{\prime}_{3},b_{3},b_{1},a_{2}\\}$ induces $Q_{4}$ in
$G$, a contradiction. Now, if $a^{\prime}_{1}\notin N(b_{1})$ or
$a^{\prime}_{3}\notin N(b_{3})$, by symmetry we assume that the first one
holds. Then $(a^{\prime}_{1},c_{1},a_{1},b_{1},b_{3},a_{3},c_{3},c_{4})$ is an
induced $P_{8}$ in $G$ a contradiction. $\blacksquare$

Now it is straightforward to verify that the function $h:V(G)\setminus
T\to[5]$ defined as

$\displaystyle h(x)=\begin{cases}i&\textrm{if }x=c_{i}\textrm{ for
}i\in[5]\textrm{ or }x\in B_{i}\textrm{ for }i=1,\\\ i+1&\textrm{if }x\in
A_{i}\textrm{ for }i\in[3],\\\ i+2&\textrm{if }x\in B_{i}\textrm{ for
}i\in\\{2,3\\},\\\ 3&\textrm{if }x\in B_{1,3},\end{cases}$

is a homomorphism from $G-T$ to $C_{5}$. Thus, by Claim 4.4.6, we have $G\to
C_{5}$ (see Figure 5 (left)).

##### Subcase 2A.2: For each $i\in[5]$ the set $B_{i}\cup B_{i+2}$ is
independent, but there exists $j\in[5]$ and $b_{j}\in B_{j},b\in
B_{j-1,j+2}\cup B_{j+1,j-2}$ such that $b_{j}b\in E(G)$.

By symmetry assume that $j=1$ and $b\in B_{j+1,j-2}=B_{2,4}$. Let $a_{1}\in
N(b_{1})\cap A_{1}$ and for $i\in\\{2,4\\}$ let $a_{i}\in N(b)\cap A_{i}$. If
$A_{5}\neq\emptyset$, say, there is $a_{5}\in A_{5}$, then
$(a_{5},c_{5},c_{4},c_{3},c_{2},a_{2},b,b_{1})$ is an induced $P_{8}$ in $G$,
a contradiction. Thus $A_{5}=\emptyset$.

######  Claim 4.4.8.

$A_{3}=\emptyset$ and $B_{4,1}=\emptyset$.

_Proof of Claim._ Assume that there is $a_{3}\in A_{3}$. Note that depending
on whether $a_{3}a_{4}$ is an edge of $G$ or not, either
$(b_{1},b,a_{4},a_{3},c_{3},c_{2},c_{1},c_{5})$ or
$(c_{1},a_{1},b_{1},b,a_{4},c_{4},c_{3},a_{3})$ is an induced $P_{8}$ in $G$.
Thus $A_{3}=\emptyset$.

Now assume that there is $b_{4,1}\in B_{4,1}$. Choose any $a^{\prime}_{1}\in
A_{1}\cap N(b_{4,1})$, $a^{\prime}_{4}\in A_{4}\cap N(b_{4,1})$, if possible
selecting $a^{\prime}_{1}$ and $a^{\prime}_{4}$ to be the neighbors of,
respectively, $b_{1}$ and $b$.

If $a^{\prime}_{1}\in N(b_{1})$ and $a^{\prime}_{1}a_{2}\notin E(G)$, then
$(c_{4},c_{3},c_{2},a_{2},b,b_{1},a^{\prime}_{1},b_{1,4})$ induces $P_{8}$. If
$a^{\prime}_{1}\in N(b_{1})$ and $a^{\prime}_{1}a_{2}\in E(G)$, then either
$\\{a_{1}^{\prime},a_{2},b,a^{\prime}_{4},b_{4,1},b_{1}\\}$ induces $Q_{4}$ or
$(c_{1},c_{2},a_{2},b,a_{4},c_{4},$ $a^{\prime}_{4},b_{1,4})$ induces $P_{8}$,
depending on whether $a^{\prime}_{4}\in N(b)$ or not (recall that
$bb_{4,1}\notin E(G)$ by Claim 4.4.4).

Thus we can assume that $a^{\prime}_{1}\notin N(b_{1})$. Then
$(a_{1}^{\prime},c_{1},a_{1},b_{1},b,a_{4},c_{4},c_{3})$ induces $P_{8}$.
Since in every case we reach a contradiction, the claim follows.
$\blacksquare$

From the fact that $A_{5}=A_{3}=B_{4,1}=\emptyset$ we obtain that $B=B_{1}\cup
B_{2}\cup B_{4}\cup B_{2,4}$. Now it is straightforward to verify that the
function $h:V(G)\setminus T\to[5]$ defined as

$\displaystyle h(x)=\begin{cases}i&\textrm{if }x=c_{i}\textrm{ for
}i\in[5]\textrm{ or }x\in B_{i-2,i}\textrm{ for }i=4,\\\ i+1&\textrm{if }x\in
A_{i}\textrm{ for }i\in\\{1,2,4\\},\\\ i+2&\textrm{if }x\in B_{i}\textrm{ for
}i\in\\{1,2,4\\},\end{cases}$

is a homomorphism from $G-T$ to $C_{5}$. Thus, by Claim 4.4.6, we have $G\to
C_{5}$ (see Figure 5 (right)).

Figure 5: $C_{5}$-coloring of $G$ defined as in Subcase A1 (left) and Subcase
A2 (right). Colors correspond to vertices/sets being mapped to specific
vertices of $C_{5}$. All sets represented by the circles are independent. Two
sets are joined by a gray line if there may be edges between them.

##### Subcase 2A.3: For each $i\in[5]$ there is no edge between $B_{i}$ and
the set $B_{i-2}\cup B_{i-1,i+2}\cup B_{i+2}\cup B_{i+1,i-2}$.

Now we define $h:V(G)\setminus T\to[5]$ as follows (see Figure 6).

$\displaystyle h(x)=\begin{cases}i&\textrm{if }x=c_{i}\textrm{ or }x\in
B_{i}\textrm{ for }i\in[5],\\\ i+1&\textrm{if }x\in A_{i}\textrm{ or }x\in
B_{i-1,i+1}\textrm{ for }i\in[5].\end{cases}$

Clearly, $h$ is a homomorphism from $G-T$ to $C_{5}$. Thus, by Claim 4.4.6,
$G\to C_{5}$. The lemma follows.

Figure 6: $C_{5}$-coloring of $G$ defined as in Subcase A3.

##### Case 2B: $G$ is $C_{5}$-free.

Since $G$ is not bipartite, $G$ contains $C_{7}$ as an induced subgraph. Let
$C$ be the vertex set of some induced $C_{7}$ in $G$, denote the consecutive
vertices as $c_{1},\ldots,c_{7}$. Again, all operations on indices are
performed modulo 7. Let $A=N(C)$. For $i\in[7]$ let $A_{i}=\\{v\in
A\leavevmode\nobreak\ |\leavevmode\nobreak\ N(v)\cap C=\\{c_{i}\\}\\}$,
$A_{i-1,i+1}=A_{i+1,i-1}=\\{v\in A\leavevmode\nobreak\ |\leavevmode\nobreak\
N(v)\cap C=\\{c_{i-1},c_{i+1}\\}\\}$,
$\mathcal{A}=\\{A_{i}\\}_{i\in[7]}\cup\\{A_{i-1,i+1}\\}_{i\in[7]}$. Clearly,
since $G$ is triangle-free, each set in $\mathcal{A}$ is independent.

######  Claim 4.4.9.

$\mathcal{A}$ is a partition of $A$.

_Proof of Claim._ Consider a vertex $v\in A$. If $v$ has more than two
neighbors in $C$, we either create a triangle or an induced $C_{5}$, a
contradiction. Moreover, because of that, if $v\in A$ has exactly two
neighbors in $C$, they must be of the form $c_{i-1},c_{i+1}$ for some
$i\in[7]$. $\blacksquare$

######  Claim 4.4.10.

For every $i\in[7]$ and every $v\in A_{i-1,i+1}$ we have $N(v)\cap A\subseteq
A_{i-2,i}\cup A_{i,i+2}\cup A_{i}\cup A_{i-2}\cup A_{i+2}$.

_Proof of Claim._ Recall that for each $i\in[7]$ the set $A_{i-1,i+1}$ is
independent. By symmetry consider $i=1$. Thus we need to show that $N(v)\cap
A\subseteq A_{6,1}\cup A_{1,3}\cup A_{1}\cup A_{6}\cup A_{3}$. First, note
that if there exists $u\in A_{2,4}$ (or, by symmetry, $u\in A_{5,7}$) such
that $vu\in E(G)$, then $u,v,c_{2}$ is a triangle in $G$. Second, if there
exists $u\in A_{3,5}$ (or, by symmetry, $u\in A_{4,6}$) such that $vu\in
E(G)$, then $\\{u,v,c_{7},c_{6},c_{5}\\}$ induces $C_{5}$ in $G$. Third, if
there exists $u\in A_{2}$ (or, by symmetry, $u\in A_{7}$) such that $vu\in
E(G)$, then $u,v,c_{2}$ is a triangle in $G$. Fourth, if there is $u\in A_{4}$
(or, by symmetry, $u\in A_{5}$) such that $vu\in E(G)$, then
$\\{u,v,c_{2},c_{3},c_{4}\\}$ is a $C_{5}$ in $G$. In each case we reach a
contradiction. $\blacksquare$

######  Claim 4.4.11.

For each $i\in[7]$ and each $v\in A_{i}$ we either have $N(v)\cap A\subseteq
A_{i-3}\cup A_{i-1,i+1}\cup A_{i-3,i-1}$ or $N(v)\cap A\subseteq A_{i+3}\cup
A_{i-1,i+1}\cup A_{i+1,i+3}$.

_Proof of Claim._ By symmetry assume $i=1$, and thus we have to show that
$N(v)\cap A\subseteq A_{5}\cup A_{7,2}\cup A_{5,7}$ or $N(v)\cap A\subseteq
A_{4}\cup A_{7,2}\cup A_{2,4}$. Clearly, $N(v)\cap A_{1}=N(v)\cap
A_{1,3}=N(v)\cap A_{6,1}=\emptyset$, since $G$ is triangle-free.

Note that if there exists $u\in A_{2}$ (or, by symmetry, $u\in A_{7}$) such
that $vu\in E(G)$, then $(u,v,c_{1},c_{7},c_{6},c_{5},c_{4},c_{3})$ is an
induced $P_{8}$ in $G$, a contradiction. Moreover, if there exists $u\in
A_{3}$ (or, by symmetry, $u\in A_{6}$) such that $vu\in E(G)$, then
$\\{u,v,c_{1},c_{2},c_{3}\\}$ induces $C_{5}$ in $G$, a contradiction. And if
there is $u\in A_{3,5}$ (or, by symmetry, $u\in A_{4,6}$) such that $vu\in
E(G)$, then $\\{v,u,c_{3},c_{2},c_{1}\\}$ induces $C_{5}$ in $G$, a
contradiction.

Last, assume that there exists $u\in N(v)\cap(A_{5}\cup A_{5,7})$. We need to
show that $u$ has no neighbors in $A_{4}\cup A_{2,4}$; by symmetry this will
conclude the proof of claim. If there is $w\in N(v)\cap(A_{4}\cup A_{2,4})$,
then $\\{u,v,w,c_{4},c_{5}\\}$ induces $C_{5}$ in $G$, a contradiction.
$\blacksquare$

Thus for every $i\in[7]$ we can further partition $A_{i}$ into
$A^{-}_{i}=\\{v\in A_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\
N(v)\cap(A_{i+3}\cup A_{i+1,i+3})=\emptyset\\}$, and $A^{+}_{i}=\\{v\in
A_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ N(v)\cap(A_{i+3}\cup
A_{i+1,i+3})\neq\emptyset\\}$. Let $B=V(G)\setminus(C\cup A)$.

######  Claim 4.4.12.

The set $B$ is independent, and for each $v\in B$ there is $i\in[7]$ such that
$N(v)\subseteq A_{i-2,i}\cup A_{i,i+2}$.

_Proof of Claim._ Let $v\in B$. First, we note that for every $i\in[7]$ we
have $N(v)\cap A_{i}=\emptyset$. Indeed, otherwise there exists $v^{\prime}\in
N(v)\cap A_{i}$ and
$(v,v^{\prime},c_{i},c_{i+1},c_{i+2},c_{i+3},c_{i-3},c_{i-2})$ is a $P_{8}$ in
$G$, a contradiction.

Next, note that $N(v)\cap A\neq\emptyset$. Otherwise, as $G$ is connected,
there is $i\in[7]$, $a\in A_{i-1,i+1}$, and an induced path
$(v,v_{1},\ldots,v_{p},a)$ in $G-C$ for some $p\geq 1$. Then
$(v,v_{1},\ldots,v_{p},a,c_{i+1},c_{i+2},$ $c_{i+3},c_{i-3},c_{i-2})$ is an
induced path on at least 8 vertices, a contradiction.

Therefore, we can assume that there exists $i\in[7]$ and $v^{\prime}\in
A_{i-2,i}\cap N(v)$. Without loss of generality, let $i=1$. If now there is
$u\in B\cap N(v)$, then clearly $uv^{\prime}\notin E(G)$, as $G$ is triangle-
free. Then $(u,v,v^{\prime},c_{1},c_{2},c_{3},c_{4},c_{5})$ is a $P_{8}$ in
$G$, a contradiction. We conclude that $B$ is independent.

Now suppose that $v$ has a neighbor $u\in A_{j,j+2}$ for some
$j\notin\\{1,4,6\\}$. If $j=7$ (or, by symmetry, $j=5$), then
$\\{v,v^{\prime},c_{1},c_{7},u\\}$ induces a $C_{5}$ in $G$, a contradiction.
On the other hand, if $j=2$ (or, by symmetry, $j=3$), then
$\\{v^{\prime},v,u,c_{2},c_{1}\\}$ is a $C_{5}$ in $G$, a contradiction.

Last, suppose that $v$ has neighbors $u\in A_{4,6}$ and $u^{\prime}\in
A_{1,3}$. Then $\\{u,v,u^{\prime},c_{3},c_{4}\\}$ is an induced $C_{5}$, a
contradiction. $\blacksquare$

We can define now a function $h:V(G)\setminus B\to[5]$:

$\displaystyle h(x)=\begin{cases}i&\textrm{if }x\in\\{c_{i}\\}\cup
A_{i-1,i+1}\textrm{ for }i\in[5],\\\ i+1&\textrm{if }x\in A^{+}_{i}\textrm{
for }i\in\\{0,...,4\\}\\\ i-1&\textrm{if }x\in A^{-}_{i}\textrm{ for
}i\in\\{2,...,6\\},\\\ 1&\textrm{if }x\in\\{c_{6}\\}\cup A^{+}_{5}\cup
A_{5,7}\cup A^{-}_{7},\\\ 2&\textrm{if }x\in\\{c_{7}\\}\cup A^{-}_{1}\cup
A_{6,1}\cup A^{+}_{6}.\end{cases}$

It is now straightforward to verify that $h$ is a homomorphism from $G-B$ to
$C_{5}$. Moreover, for each $i\in[7]$ the set $A_{i-1,i+1}$ is mapped by $h$
to precisely one vertex of $C_{5}$. Thus, analogously as in Claim 4.4.6, $h$
can be extended to a homomorphism from $G$ to $C_{5}$. This concludes the
proof of the lemma. ∎

Figure 7: $C_{5}$-coloring of $G$ defined as in Case 2B.

##  5 Minimal obstructions to $C_{5}$-coloring with no long subdivided claws

This section is devoted to the proof of Theorem 1.2.

See 1.2

The minimal obstructions are shown in Figure 4 and can also be obtained from
the database of interesting graphs at the House of Graphs [9] by searching for
the keywords “S221-free minimal obstruction to C5-coloring” and “S311-free
minimal obstruction to C5-coloring”, respectively. As in this section the
target graph is always $C_{5}$, we will keep writing _minimal obstructions_
for _minimal obstructions to $C_{5}$-coloring_. We proceed similarly as in the
proof of Theorem 1.1. Let $G$ be an $S_{2,2,1}$-free (respectively,
$S_{3,1,1}$-free) minimal obstruction. We again consider two cases.

#### Case 1: $G$ contains $C_{5}$ as an induced subgraph.

This case is solved using the algorithm from Section 3. The algorithm is
called with the parameters $(I=C_{5},H=C_{5},F=S_{2,2,1})$ and then with
parameters $(I=C_{5},H=C_{5},F=S_{3,1,1})$. Both calls terminate, returning a
finite list of minimal obstructions.

#### Case 2: $G$ does not contain $C_{5}$ as an induced subgraph.

Similarly as in the proof of Theorem 1.1, note that $K_{3}$ is a minimal
$\\{F,C_{5}\\}$-free obstruction for $F\in\\{S_{2,2,1},S_{3,1,1}\\}$. Thus,
from now on, we assume that $G$ is $K_{3}$-free and prove that there are no
more minimal obstructions satisfying this case, i.e., the following result.

######  Lemma 5.1.

Let $F\in\\{S_{2,2,1},S_{3,1,1}\\}$ and let $G$ be a
$\\{F,C_{5},K_{3}\\}$-free graph. Then $G$ is $C_{5}$-colorable.

###### Proof.

We can assume that $G$ is connected, as otherwise we can consider each of its
connected components separately. Clearly, if $G$ is bipartite, then the lemma
holds, thus we can assume that there is an odd cycle $C$ of minimal length in
$G$. Let $t\geq 7$ be the number of vertices of $C$, i.e., $C=C_{t}$. Denote
by $c_{0},c_{2},\ldots,c_{t-1}$ the consecutive vertices of $C$. Since $t$ is
minimal, $C$ must be an induced cycle.

Note that every $v\in V(G)\cap(N(C)\cup C)$ has precisely two neighbors
$c_{i-1},c_{i+1}$ on $C$ for some $i\in[t-1]_{0}$ (we compute the indices
modulo $t$). Indeed, if $v$ has one neighbor on $C$, say $c_{i}$, then
$\\{c_{i-2},c_{i-1},c_{i},c_{i+1},c_{i+2},v\\}$ induces $S_{2,2,1}$ in $G$,
and $\\{c_{i-3},c_{i-2},c_{i-1},c_{i},c_{i+1},v\\}$ induces $S_{3,1,1}$ in
$G$, contradicting the fact that $G$ is $F$-free. On the other hand, if $v$
has two neighbors $c_{i},c_{j}$ such that $|i-j|\neq 2$ (in particular if
$|N(v)\cap C|\geq 3$), then either $v,c_{i},c_{i+1},\ldots,c_{j-1},c_{j}$ or
$v,c_{j},c_{j+1},\ldots,c_{i-1},c_{i}$ is an odd cycle on less than $t$
vertices, a contradiction with the minimality of $C$.

Now observe that $V(G)=N(C)\cup C$. Indeed, otherwise, since $G$ is connected,
there is a vertex $v\in N(c_{i-1})\cup N(c_{i+1})$, and a vertex $u\in
N(v)\setminus(N(C)\cup C)$. But then
$\\{c_{i-2},c_{i-1},v,c_{i+1},c_{i+2},u\\}$ induces $S_{2,2,1}$ in $G$, and
$\\{c_{i-3},c_{i-2},c_{i-1},v,c_{i+1},u\\}$ induces $S_{3,1,1}$ in $G$, again
contradicting the fact that $G$ is $F$-free.

Thus, we can partition the vertices of $G$ into sets
$A_{1,3},A_{2,4},\ldots,A_{t-2,1},A_{t-1,2}$ so that for each $v\in
A_{i-1,i+1}$ we have $N(v)\cap C=\\{c_{i-1},c_{i+1}\\}$. Note that for every
$i\in[t-1]_{0}$ and every $v\in A_{i-1,i+1}$ we have $N(v)\subseteq
A_{i-2,i}\cup A_{i,i+2}$. Indeed, otherwise we would again obtain a shorter
odd cycle in $G$, a contradiction.

Now it is straightforward to verify that a function $h:V(G)\to V(C_{5})$
defined as:

$\displaystyle h(v)=\begin{cases}i&\textrm{ if }i\in\\{0,1,2\\}\textrm{ and
}v\in A_{i-1,i+1},\\\ 4&\textrm{ if }i\geq 3\textrm{ is odd and }v\in
A_{i-1,i+1},\\\ 5&\textrm{ if }i\geq 3\textrm{ is even and }v\in
A_{i-1,i+1},\end{cases}$

is a $C_{5}$-coloring of $G$. ∎

Combining the cases, we obtain the statement of Theorem 1.2.

##  6 An infinite family of minimal obstructions

In this section we construct infinite families of graphs that will be later
used to prove Theorems 1.3 and 1.4. The construction is a generalization of
the one designed for $3$-Coloring [6]; the authors attribute it to Pokrovskiy.

###  6.1 The construction

For every odd $q\geq 3$ and every $p\geq 1$, let $G_{q,p}$ be the graph on
vertex set $[qp-3]_{0}$ (all arithmetic operations on $[qp-3]_{0}$ here are
done modulo $qp-2$), such that for every $i\in[qp-3]_{0}$ it holds that

$N(i)=\\{{i-1},{i+1}\\}\cup\\{{i+qj-1}\leavevmode\nobreak\
|\leavevmode\nobreak\ j\in[p-1]\\}.$

To simplify the arguments, we partition the vertex set of $G_{q,p}$ into $q$
sets $V_{s}=\\{i\leavevmode\nobreak\ |\leavevmode\nobreak\ i=s\mod q\\}$,
where $s\in[q-1]_{0}$. For a vertex $i\in V(G_{q,p})$ and $s\in[q-1]_{0}$, we
say that $i$ is of _type $s$_, if $i\in V_{s}$. If we say that $i$ is of the
type $s$ for some $s\geq q$, it means that $i$ is of type $s\mod q$. If
$i,j\in V(G_{q,p})$, we say that $(i,j)$ is _of type_ $(s_{i},s_{j})$ if $i$
is of type $s_{i}$ and $j$ is of type $s_{j}$.

The following observation follows immediately from the definition of
$E(G_{q,p})$.

######  Observation 6.1.

Let $q\geq 3$ be odd, and let $ij\in E(G_{q,p})$ be such that $i\in V_{s}$ for
some $s\in[q-1]_{0}$. If $i<j$, then $j\in V_{s-1}$, or $j=i+1$, or $i=0$ and
$j=qp-3$. Analogously, if $j>i$, then $j\in V_{s+1}$, or $j=i-1$, or $i=qp-3$
and $j=0$.

Thus, from Observation 6.1, it follows that $ij$ for $i<j$ is an edge of
$G_{q,p}$ if and only if

  * •

$(i,j)$ is of type $(s,s-1)$, for some $s\in[q-1]_{0}$, or

  * •

$i\in[qp-3]_{0}$ and $j=i+1$, or

  * •

$i={0}$ and $j={qp-3}$.

We now show that graphs $G_{q,p}$ are minimal obstructions to $H$-coloring for
a rich family of graphs $H$.

######  Lemma 6.2.

Let $q\geq 3$ be an odd integer, and let $H$ be graph of odd girth $q$ that
does not contain $C_{4}$ as a subgraph. For every $p\geq 1$ the graph
$G_{q,p}$ is a minimal obstruction to $H$-coloring.

###### Proof.

To show that $G_{q,p}$ is a minimal obstruction to $H$-coloring, we need to
show that (i) there is no homomorphism from $G_{q,p}$ to $H$, and that (ii)
for each $v\in V(H)$ there is a homomorphism from $G_{q,p}-v$ to $H$.

To see (i), assume that there exists a homomorphism $h$ from $G_{q,p}$ to $H$.

######  Claim 6.2.1.

For each $j\in\\{q,\ldots,qp-3\\}$ we have $h(j)=h(j-q)$.

_Proof of Claim._ From the construction of $G_{q,p}$ it follows that each set
of $q$ consecutive vertices $\\{i,i+1,\ldots,i+q-1\\}$ of $G_{q,p}$ induces an
odd cycle of length $q$. This implies that their images
$(h(i),h(i+1),\ldots,h(i+q-1))$ form a closed walk of length $q$ in $H$. As
the odd girth of $H$ is $q$, we conclude that
$\\{h(i),h(i+1),\ldots,h(i+q-1)\\}$ must induce an odd cycle of length $q$ in
$H$. In particular, they must be mapped by $h$ to the distinct vertices of
$H$.

Assume the claim does not hold, and choose the smallest $j\geq q$ for which
$h(j)\neq h(j-q)$. Since $j-q,j-q+1$, and $j-1$ belong to a set of $q$
consecutive vertices of $G$, by the previous paragraph, $h(j-q),h(j-q+1)$, and
$h(j-1)$ are three pairwise distinct vertices. But if now $h(j)$ and $h(j-q)$
are not mapped to the same vertex of $H$, vertices $h(j-q),h(j-q+1),h(j-1)$,
and $h(j)$ form a (not-necessarily induced) $C_{4}$ in $H$, a contradiction.
$\blacksquare$

The claim guarantees that for every $s\in[q-1]_{0}$, all the vertices that
belong to $V_{s}$ are mapped to the same vertex of $H$, say $a_{s}$. By the
fact that $h$ is a homomorphism, the set $\\{a_{0},a_{1},\ldots,a_{q-1}\\}$
induces a $q$-cycle in $H$. But now, since $0(qp-3)\in E(G_{q,p})$, we have
that $h(0)h(qp-3)=a_{0}a_{q-3}\in E(H)$, a contradiction with the fact that
the odd girth of $H$ is $q$.

It remains to show (ii), i.e., for each $v\in V(G_{q,p})$ there is a
homomorphism from $G_{q,p}-v$ to $H$. By symmetry of $G_{q,p}$, it is enough
to consider the case when $v=qp-3$. As the odd girth of $H$ is $q$, there
exists a $q$-cycle with consecutive vertices $a_{0},\ldots,a_{q-1}$ in $H$. We
claim that $h:V(G_{q,p})\to V(H)$ defined as $h(i)=a_{i\mod q}$ for every
$i\in V(G_{q,p})$ is a homomorphism. Indeed, take an edge $ij$ of $G$ and
without loss of generality assume that $i<j$. Then by Observation 6.1, we have
either $h(i)h(j)=a_{i}a_{i-1\mod q}\in E(H)$, or $h(i)h(j)=a_{i}a_{i+1\mod
q}\in E(H)$. ∎

###  6.2 Excluded induced subgraphs of $G_{q,p}$

Now let us show an auxiliary lemma that will be helpful in analyzing induced
subgraphs that (do not) appear in $G_{q,p}$. In particular, it implies that in
order to prove that for each $p$, the graph $G_{q,p}$ is $F$-free for some
graph $F$, it is sufficient to show that this statement holds for some small
values of $p$.

######  Lemma 6.3.

Let $q$ be a fixed constant and $F$ be a graph. Let $p\geq|V(F)|+2$. If
$G_{q,p-1}$ is $F$-free, then $G_{q,p}$ is $F$-free.

###### Proof.

Assume otherwise, and let $U\subseteq V(G_{q,p})$ induce a copy of $F$ in
$G_{q,p}$, in particular $|V(F)|=|U|$. Since $|V(F)|<qp-2$, we can assume
without loss of generality that the vertex ${qp-3}$ does not belong to $U$.
Since $|V(G_{q,p})|=qp-2>q(|V(F)|+1)$, there exist $q+1$ consecutive vertices
$\ell,\ldots,{\ell+q}$ that do not belong to $U$. Define $R=\\{j\in
U\leavevmode\nobreak\ |\leavevmode\nobreak\ j>\ell+q\\}$,
$R^{\prime}=\\{{j-q}\leavevmode\nobreak\ |\leavevmode\nobreak\ j\in R\\}$, and
let $L=U\setminus R$.

Now consider $U^{\prime}=L\cup R^{\prime}$, and note that $\ell\notin
U^{\prime}$. It is straightforward to verify that $U^{\prime}\subseteq
V(G_{q,p-1})$. We will show that $U^{\prime}$ induces a copy of $F$ in
$V(G_{q,p-1})$. Since this is a contradiction with our assumption, we then
conclude that $G_{q,p}$ is $F$-free.

Let $i,j\in U^{\prime}$, let $s\in[q-1]_{0}$ be such that $i\in V_{s}$. Assume
without loss of generality that $i<j$. Note that it is enough to show that

  * •

if $i,j<\ell$, then $ij\in E(G_{q,p-1})$ if and only if $ij\in E(G_{q,p})$,

  * •

if $i,j>\ell$, then $ij\in E(G_{q,p-1})$ if and only if $(i+q)(j+q)\in
E(G_{q,p})$,

  * •

if $i<\ell<j$, then $ij\in E(G_{q,p-1})$ if and only if $i(j+q)\in
E(G_{q,p})$.

The first item is straightforward.

For the second item, by Observation 6.1 we have that $ij\in E(G_{q,p-1})$ if
and only if $j=i+1$ or $j\in V_{s-1}$. The first is equivalent to
$j+q=(i+q)+1$, the latter is equivalent to ${j+q}\in V_{s-1}$. Hence again
using Observation 6.1 we obtain that $ij\in E(G_{q,p-1})$ if and only if
$({i+q})({j+q})\in E(G_{q,p})$.

For the last item, note that $i<\ell<j$ implies $i\in L$ and $j\in
R^{\prime}$. If $ij\in E(G_{q,p-1})$, then by Observation 6.1, either $j=i+1$
or $v_{j}\in V_{s-1}$. Since $i<\ell<j$, the first case is not possible. In
the second case, if $v_{j}\in V_{s-1}$, then ${j+q}\in V_{s-1}$, so
$i({j+q})\in E(G_{q,p})$. On the other hand, if $i({j+q})\in E(G_{q,p})$,
then, since $i<\ell<j$, it cannot happen that $j+q=i+1$. If ${j+q}\in V_{s-1}$
then $j\in V_{s-1}$, so we conclude that $ij\in E(G_{q,p-1})$. That concludes
the proof. ∎

The power of Lemma 6.3 is that in order to show that $G_{q,p}$ is $F$-free for
_every_ $p$, it is sufficient to prove it for a finite (and small) set of
graphs. This is encapsulated in the following, immediate corollary.

######  Corollary 6.4.

Let $q$ be a fixed constant and $F$ be a graph. If $G_{q,p}$ is $F$-free for
every $p\leq|V(F)|+1$, then $G_{q,p}$ is $F$-free for every $p$.

Consequently, for every fixed $q$ and $F$, Corollary 6.4 reduces the problem
of showing that $G_{q,p}$ is $F$-free to a constant-size task that can be
tackled with a computer.

###  6.3 Proof of Theorem 1.4 and Theorem 1.3

Now let us analyze what induced paths and subdivided claws appear in
$G_{q,p}$. We start with showing that for every odd $q\geq 3$ and every $p\geq
1$ the graph $G_{q,p}$ is $qK_{2}$-free, i.e., they exclude an induced
matching on $q$ edges. Here, an induced matching is a set of edges that are
not only pairwise disjoint, but also non-adjacent.

######  Lemma 6.5.

Let $q\geq 3$ be an odd integer. For every $p\geq 1$ the graph $G_{q,p}$ is
$qK_{2}$-free.

###### Proof.

Let $M$ be a set of edges of $G_{q,p}$ that induce a matching. We aim to show
that $|M|\leq q-1$.

######  Claim 6.5.1.

For each $s\in[q-1]_{0}$, the set $M$ contains at most one edge of type
$(s,s+1)$ or $(s+1,s)$.

_Proof of Claim._ Let $ij$ and ${i^{\prime}}{j^{\prime}}$ be some distinct
edges in $M$ for $i<j$ and $i^{\prime}<j^{\prime}$.

First, assume that $(i,j)$ and $(i^{\prime},j^{\prime})$ are of the same type
$(a,b)$. By symmetry we can assume that $i<i^{\prime}$ (since they belong to
$M$, we cannot have $i=i^{\prime}$). Observe that if $(a,b)=(s,s+1)$, then in
particular $j=i+1$ and $j^{\prime}=i^{\prime}+1$ and thus $j<i^{\prime}$.
However, as $(j,i^{\prime})$ is of type $(s+1,s)$, we conclude $ji^{\prime}$
is an edge of $G_{q,p}$, so $M$ is not an induced matching, a contradiction.
If, on the other hand, $(a,b)=(s+1,s)$, then $(i,j^{\prime})$ is of type
$(s+1,s)$. Thus $ij^{\prime}$ is an edge of $G_{q,p}$, which again leads to a
contradiction.

Now, let $ij,i^{\prime}j^{\prime}$ be the edges in $M$, such that $(i,j)$ is
of type $(s,s+1)$ and $(i^{\prime},j^{\prime})$ is of type $(s+1,s)$. This
means that $(j,j^{\prime})$ is of the type $(s+1,s)$, that $(i,i^{\prime})$ is
of type $(s,s+1)$, and that $j=i+1$. Thus, either $i<j<i^{\prime}<j^{\prime}$
or $i^{\prime}<i<j<j^{\prime}$, or $i^{\prime}<j^{\prime}<i<j$. But then, in
the first two cases, there is the edge $jj^{\prime}$ in $G_{q,p}$, and in the
last case we have the edge $i^{\prime}i$, a contradiction with $M$ being an
induced matching. $\blacksquare$

Note that there is at most one edge in $G_{q,p}$ of type $(0,q-3)$, namely
$0(qp-3)$, thus there is at most one edge in $M$ of type $(0,q-3)$. If the
edge $0(pq-3)$ belongs to $M$, then, since $M$ is an induced matching, no edge
of the type $(0,q-1)$, $(q-1,0)$, $(0,1)$, nor $(1,0)$ belongs to $M$. Thus,
by 6.5.1, $|M|\leq q-1$.

Therefore, we can assume that the edge $0(pq-3)$ does not belong to $M$. In
this case, for every $s\in[q-1]_{0}$, the only possible types of an edge in
$G_{q,p}$ that have $s$ on the first coordinate are $(s,s+1)$ and $(s,s-1)$,
and for $t\in\\{s+1,s-1\\}$ there is at most one edge of type $(s,t)$ or
$(t,s)$. This in particular means that $|M|\leq q$.

######  Claim 6.5.2.

Let $s\in[q-1]_{0}$, and let $ij,i^{\prime}j^{\prime}$ be the edges in $M$
such that $i<j$ and $i^{\prime}<j^{\prime}$. If $(i,j)$ is of type $(s,s+1)$
or $(s+1,s)$, and $(i^{\prime},j^{\prime})$ is of type $(s+1,s+2)$ or
$(s+2,s+1)$, then $i<i^{\prime}$.

_Proof of Claim._ Assume otherwise, i.e., that $i^{\prime}<i$. If
$(i^{\prime},j^{\prime})$ is of type $(s+1,s+2)$, then we must have
$j^{\prime}=i^{\prime}+1$, thus $i^{\prime}<j^{\prime}<i<j$. Therefore there
is an edge $i^{\prime}i$ (if $(i,j)$ is of type $(s+1,s+2)$) or an edge
$i^{\prime}j$ (if $(i,j)$ is of type $(s+2,s+1)$), in both cases a
contradiction.

Now consider the case when $(i^{\prime},j^{\prime})$ is of type $(s+2,s+1)$.
In that case, however, either there is an edge $i^{\prime}i$ (if $(i,j)$ is of
type $(s+1,s+2)$) or an edge $i^{\prime}j$ (if $(i,j)$ is of type
$(s+2,s+1)$), again a contradiction. $\blacksquare$

Suppose that $|M|=q$. This means that for every $s\in[q-1]_{0}$ there is an
edge $ij$ in $M$ such that $(i,j)$ is of type $(s,s+1)$ or $(s+1,s)$. Let
$ij\in M$, where $i<j$, be such that $i$ is smallest possible (i.e., $ij$ is
the “first” edge of $M$). Let the type of $(i,j)$ be $(s,s+1)$ or $(s+1,s)$.
Let $i^{\prime}j^{\prime}$, where $i^{\prime}<j^{\prime}$, be the edge of $M$
such that $(i^{\prime},j^{\prime})$ is of type $(s-1,s)$ or $(s,s-1)$; it
exists by our assumption. By Claim 6.5.2, we conclude that $i^{\prime}<i$,
which contradicts the choice of $ij$. Thus $|M|<q$, which concludes the proof.
∎

Let us remark that Lemma 6.5 is best possible, i.e., if $p$ is large enough,
then $G_{q,p}$ contains $(q-1)K_{2}$ as an induced subgraph. We do not prove
it, as later, in Lemma 6.8, we will show a stronger result. Let us turn our
attention to induced paths and subdivided claws that do not appear in
$G_{q,p}$.

######  Lemma 6.6.

Let $q\geq 3$ be an odd integer. For every $p\geq 1$ the graph $G_{q,p}$ is
$\\{P_{3q-1},S_{2,2,2},$
$S_{\nicefrac{{3(q-1)}}{{2}},\nicefrac{{3(q-1)}}{{2}},1}\\}$-free.

###### Proof.

Notice that an induced path with consecutive vertices
$p_{0},p_{1},\ldots,p_{3q-2}$ contains $qK_{2}$ as an induced subgraph (with
vertex set $\\{p_{i}p_{i+1}\leavevmode\nobreak\ |\leavevmode\nobreak\ i=0\mod
3\\}$). Similarly, $S_{\nicefrac{{3(q-1)}}{{2}},\nicefrac{{3(q-1)}}{{2}},1}$
contains $qK_{2}$ is an induced subgraph; see Figure 8. Thus the fact that
$G_{q,p}$ is
$\\{P_{3q-1},S_{\nicefrac{{3(q-1)}}{{2}},\nicefrac{{3(q-1)}}{{2}},1}\\}$-free
follows directly from Lemma 6.5.

Figure 8: If a graph contains
$S_{\nicefrac{{3(q-1)}}{{2}},\nicefrac{{3(q-1)}}{{2}},1}$ as an induced
subgraph, then it also contains $qK_{2}$.

Now let us argue that $G_{q,p}$ is also $S_{2,2,2}$-free. The case $q=3$
requires slightly different arguments that he case $q\geq 5$. However, thanks
to Corollary 6.4, in order to show that for every $p$, the graph $G_{3,p}$ is
$S_{2,2,2}$-free, it is sufficient to verify this for $p\leq 8$. We confirmed
this using exhaustive computer search.

So from now on assume that $q\geq 5$. For contradiction suppose that $G_{q,p}$
has an induced subgraph $T$ isomorphic to $S_{2,2,2}$. By symmetry of
$G_{q,p}$ we can assume that 2 is the unique vertex of $T$ of degree 3, let
$i<j<k$ be the neighbors of 2 in $T$, and let $i^{\prime},j^{\prime}$ and
$k^{\prime}$ be their respective neighbors of degree 1 in $T$. By the
definition of $G_{q,p}$, either $i=1$, or $i,j,k>2$.

Consider the case $i=1$. If $(2,j)$ and $(2,k)$ are both of type $(2,1)$, then
either $(1,j^{\prime})$ is of type $(1,0)$ or $(1,2)$. In the first case there
is an edge $ij^{\prime}$, in the second case $j^{\prime}\leq j+1<k$ and thus
there is an edge $j^{\prime}k$, thus we reach a contradiction. Thus $(2,j)$ is
of type $(2,3)$ and $(2,k)$ is of type $(2,1)$. But in that case
$k^{\prime}>j$, and either $(1,k^{\prime})$ is of type $(1,0)$ and
$ik^{\prime}$ is an edge of $G_{q,p}$, or $(3,k^{\prime})$ is of type $(3,2)$
and $jk^{\prime}$ is an edge of $G_{q,p}$, again a contradiction.

Thus we can assume that $i,j,k>2$, in particular $(2,j)$ and $(2,k)$ are of
type $(2,1)$. If $(2,i)$ is also of type $(2,1)$, then $(j^{\prime},j)$ is
either of type $(2,1)$, or of type $(0,1)$. In the first case, $j^{\prime}\leq
j+1<k$ and there is an edge $j^{\prime}k$ in $G_{q,p}$. In the second case,
$j^{\prime}\geq j-1>i$ and as $(i,j^{\prime})$ is of type $(1,0)$, thus
$i^{\prime}j$ is an edge of $G_{q,p}$, in both cases we reach a contradiction.

It remains to consider the case when $(2,i)$ is of type $(2,3)$, i.e.,
$i^{\prime}=i+1=3<j,j^{\prime},k,k^{\prime}$. Then, $(k,k^{\prime})$ is either
of type $(1,2)$, or of type $(1,0)$. In the first case,
$(i^{\prime},k^{\prime})$ is of type $(3,2)$, and thus $i^{\prime}k^{\prime}$
is an edge of $G_{q,p}$. In the second case we have $k^{\prime}\geq k-1>j$ and
$(j,k^{\prime})$ is of type $(1,0)$, thus $jk^{\prime}$ is an edge of
$G_{q,p}$, a contradiction. ∎

Now, as an immediate consequence of Lemma 6.2 and Lemma 6.6, we obtain Theorem
1.4, which we restate below.

See 1.4

Note that for $H=C_{5}$, i.e., for $q=5$, Theorem 1.4 shows that the
constructed graphs are in particular $P_{14}$-free and $S_{6,6,1}$-free. It
turns out that they are actually $P_{13}$-free and $S_{5,5,1}$-free (and also
exclude some other subdivided claws). Here we will make use of Corollary 6.4,
combined with computer search.

Let us start with analyzing the length of a longest induced path in $G_{5,p}$.
Thus we are interested in applying Corollary 6.4 to the case $q=5$ and
$F=P_{13}$. Actually, we can even exclude $F=P_{10}+P_{2}$, i.e., the graph
with two components: one isomorphic to $P_{10}$ and the other isomorphic to
$P_{2}$. Note that $(P_{10}+P_{2})$-free graphs are in particular
$P_{13}$-free. Furthermore, the graph $G_{5,p}$ excludes the following
subdivided claws: $S_{5,5,1}$, $S_{11,1,1}$, and $S_{8,2,1}$. These results,
together with Lemma 6.2, give us Theorem 1.3.

See 1.3

###  6.4 Longest induced paths in $G_{q,p}$

Theorem 1.3, and the fact that from the result of Chudnovsky et al. [6] it
follows that for every $p$, the graph $G_{3,p}$ is $P_{7}$-free (while Lemma
6.6 only gives $P_{8}$-freeness), suggest that the bound on the length of a
longest induced path given by Theorem 1.4 is not optimal also in the other
cases. This evidence suggests the following conjecture.

######  Conjecture 6.7.

Let $q\geq 3$ be odd. For every $p\geq 1$, the graph $G_{q,p}$ is
$P_{3q-2}$-free.

We conclude this section by showing that the bound from Conjecture 6.7, if
true, is best possible.

######  Lemma 6.8.

Let $q\geq 3$ be odd. If $p\geq 2q+1$, then $G_{q,p}$ contains $P_{3q-3}$ as
an induced subgraph.

###### Proof.

Let $q$ and $p$ be as in the statement of the lemma. We will define a sequence
of $3q-3$ vertices

$P=(a_{0},a_{1},a_{2},a_{3},\ldots,a_{3q-4})$

that induce a path in $G_{q,p}$. For $j\in[2]_{0}$ let
$Q_{j}=\\{i\leavevmode\nobreak\ |\leavevmode\nobreak\ i=j\mod
3,i\in[3q-4]\\}$. Let $a_{0}=0$, and for $i\in[3q-4]$ we set

$\displaystyle a_{i}=\begin{cases}q^{2}-1-k(q+1)&\textrm{ if }i\in
Q_{1},k=(i-1)/3,\\\ 2q^{2}-2-k(q+1)&\textrm{ if }i\in Q_{2},k=(i-2)/3.\\\
2q^{2}-3-k(q+1)&\textrm{ if }i\in Q_{0},k=(i-3)/3,\\\ \end{cases}$

Observe that since $p\geq 2q+1$, the graph $G_{q,p}$ has at least $2q^{2}+q-2$
vertices, so the vertices $a_{i}$ are well-defined. Observe that for every
$i\in[3q-5]$, if $i=1\mod 3$ then $a_{i}<a_{i+1}$, and otherwise
$a_{i}>a_{i+1}$. In particular, if $i=2\mod 3$, then $a_{i+1}=a_{i}-1$.
Moreover, from the definition it follows that the sequence of the types of the
consecutive vertices of $P$ is

$(0,q-1,q-2,q-3,q-2,q-3,q-4,q-3,q-4,q-5,\ldots,2,1,0,1,0).$

Now to see that $P$ is an induced path, we show that for every
$i\in[3q-5]_{0}$ that is of type $s\in[q-1]_{0}$ the edge $a_{i}a_{i+1}$
exists and no edge of the form $a_{i}a_{j}$ for $j>i+1$ exists.

Case 1: $i=0$. Observe that $0a_{1}\in E(G_{q,p})$ since $(0,a_{1})$ is of
type $(0,q-1)$. On the other hand, for every $i\in\\{2,\ldots,3q-4\\}$ we have
$0a_{i}\notin E(G_{q,p})$, as $(0,a_{i})$ is not of type $(0,q-1)$.

Case 2: $i\in Q_{1}$. Observe that for every $j\in[3q-4]\setminus\\{i\\}$, if
$j\in Q_{0}\cup Q_{2}$ or $j\in Q_{1},j<i$, then $a_{i}<a_{j}$. Otherwise (if
$j\in Q_{1}$ and $j>i$), $a_{i}>a_{j}$. Thus, as $(a_{i},a_{i+1})$ is of type
$(s,s-1)$, the edge $a_{i}a_{i+1}$ belongs to $E(G_{q,p})$. On the other hand,
there is no $j>i+1$ such that (i) $a_{j}>a_{i}$ and $(a_{i},a_{j})$ is of type
$(s,s-1)$, or (ii) $a_{j}<a_{i}$ and $(a_{i},a_{j})$ is of type $(s,s+1)$,
thus $a_{i}a_{j}\notin E(G_{q,p})$ for any $j>i+1$.

Case 3: $i\in Q_{2}$. Observe that for every $j\in[3q-4]\setminus\\{i\\}$, if
$j\in Q_{1}$ or $j>i$, then $a_{i}>a_{j}$. Otherwise, $a_{i}>a_{j}$. As
$a_{i+1}=a_{i}-1$, the edge $a_{i}a_{i+1}$ belongs to $E(G_{q,p})$. On the
other hand, there is no $j>i+1$ such that (i) $a_{j}>a_{i}$ or (ii)
$a_{j}<a_{i}$ and $(a_{i},a_{j})$ is of type $(s,s+1)$. Thus $a_{i}a_{j}\notin
E(G_{q,p})$ for any $j>i+1$.

Case 3: $i\in Q_{0}$. Observe that for every $j\in[3q-4]\setminus\\{i\\}$, if
$j\in Q_{0}\cup Q_{2}$ and $j<i$, then $a_{i}<a_{j}$. Otherwise (if $j\in
Q_{1}$ or $j\in Q_{0}\cup Q_{2}$ and $j>i$), $a_{i}>a_{j}$. Thus, as
$(a_{i},a_{i+1})$ is of type $(s,s+1)$, the edge $a_{i}a_{i+1}$ belongs to
$E(G_{q,p})$. On the other hand, there is no $j>i+1$ such that (i)
$a_{j}>a_{i}$ or (ii) $a_{j}<a_{i}$ and $(a_{i},a_{j})$ is of type $(s,s+1)$.
Thus $a_{i}a_{j}\notin E(G_{q,p})$ for any $j>i+1$. ∎

## Acknowledgements

The authors are grateful to Rémi Di Guardia for fruitful and inspiring
discussions that led to this project. This project itself was initiated at
Dagstuhl Seminar 22481 “Vertex Partitioning in Graphs: From Structure to
Algorithms.” We are grateful to the organizers and other participants for a
productive atmosphere. Jorik Jooken is supported by an FWO grant with grant
number 1222524N. Jan Goedgebeur is supported by Internal Funds of KU Leuven
and an FWO grant with grant number G0AGX24N. Karolina Okrasa is supported by a
Polish National Science Centre grant no. 2021/41/N/ST6/01507.

## References

  * [1] Source code of algorithm Expand.  https://github.com/JorikJooken/ObstructionsForC5Coloring, 2024.
  * [2] S. Arnborg and A. Proskurowski.  Linear time algorithms for NP-hard problems restricted to partial $k$-trees.  Discret. Appl. Math., 23(1):11–24, 1989.
  * [3] F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, and M. Zhong.  Three-coloring and list three-coloring of graphs without induced paths on seven vertices.  Comb., 38(4):779–801, 2018.
  * [4] D. Bruce, C. T. Hoàng, and J. Sawada.  A certifying algorithm for 3-colorability of $P_{5}$-free graphs.  In Y. Dong, D. Du, and O. H. Ibarra, editors, Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, volume 5878 of Lecture Notes in Computer Science, pages 594–604. Springer, 2009.
  * [5] Q. Cai, J. Goedgebeur, and S. Huang.  Some results on $k$-critical $P_{5}$-free graphs.  Discret. Appl. Math., 334:91–100, 2023.
  * [6] M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong.  Obstructions for three-coloring graphs without induced paths on six vertices.  J. Comb. Theory, Ser. B, 140:45–83, 2020.
  * [7] M. Chudnovsky, S. Huang, P. Rzążewski, S. Spirkl, and M. Zhong.  Complexity of $C_{k}$-coloring in hereditary classes of graphs.  Inf. Comput., 292:105015, 2023.
  * [8] M. Chudnovsky, S. Huang, S. Spirkl, and M. Zhong.  List 3-Coloring graphs with no induced $P_{6}+rP_{3}$.  Algorithmica, 83(1):216–251, 2021.
  * [9] K. Coolsaet, S. D’hondt, and J. Goedgebeur.  House of Graphs 2.0: A database of interesting graphs and more.  Discret. Appl. Math., 325:97–107, 2023.
  * [10] M. Dębski, Z. Lonc, K. Okrasa, M. Piecyk, and P. Rzążewski.  Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws.  In S. W. Bae and H. Park, editors, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [11] T. Emden-Weinert, S. Hougardy, and B. Kreuter.  Uniquely colourable graphs and the hardness of colouring graphs of large girth.  Comb. Probab. Comput., 7(4):375–386, 1998.
  * [12] T. Feder and P. Hell.  Edge list homomorphisms.  Unpublished manuscript, available at http://theory.stanford.edu/~tomas/edgelist.ps.
  * [13] M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou.  The complexity of coloring circular arcs and chords.  SIAM J. Algebraic Discret. Methods, 1(2):216–227, 1980.
  * [14] J. Goedgebeur and O. Schaudt.  Exhaustive generation of $k$-critical $H$-free graphs.  J. Graph Theory, 87(2):188–207, 2018.
  * [15] M. Grötschel, L. Lovász, and A. Schrijver.  The ellipsoid method and its consequences in combinatorial optimization.  Comb., 1(2):169–197, 1981.
  * [16] M. Grötschel, L. Lovász, and A. Schrijver.  Corrigendum to our paper “The ellipsoid method and its consequences in combinatorial optimization”.  Comb., 4(4):291–295, 1984.
  * [17] P. Hell and J. Nešetřil.  On the complexity of $H$-coloring.  J. Comb. Theory, Ser. B, 48(1):92–110, 1990.
  * [18] P. Hell and J. Nešetřil.  The core of a graph.  Discret. Math., 109(1-3):117–126, 1992.
  * [19] 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(1):74–81, 2010.
  * [20] C. T. Hoàng, B. Moore, D. Recoskie, J. Sawada, and M. Vatshelle.  Constructions of $k$-critical $P_{5}$-free graphs.  Discret. Appl. Math., 182:91–98, 2015.
  * [21] I. Holyer.  The NP-completeness of edge-coloring.  SIAM J. Comput., 10:718–720, 1981.
  * [22] S. Huang.  Improved complexity results on $k$-coloring $P_{t}$-free graphs.  Eur. J. Comb., 51:336–346, 2016.
  * [23] M. Kamiński and A. Pstrucha.  Certifying coloring algorithms for graphs without long induced paths.  Discret. Appl. Math., 261:258–267, 2019.
  * [24] T. Klimošová, J. Malík, T. Masařík, J. Novotná, D. Paulusma, and V. Slívová.  Colouring $(P_{r}+P_{s})$-free graphs.  Algorithmica, 82(7):1833–1858, 2020.
  * [25] D. Leven and Z. Galil.  NP-completeness of finding the chromatic index of regular graphs.  J. Algorithms, 4(1):35–44, 1983.
  * [26] T. Łuczak and J. Nešetřil.  Note on projective graphs.  J. Graph Theory, 47(2):81–86, 2004.
  * [27] R. M. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer.  Certifying algorithms.  Comput. Sci. Rev., 5(2):119–161, 2011.
  * [28] B. D. McKay and A. Piperno.  Practical graph isomorphism, II.  J. Symb. Comput., 60:94–112, 2014.
  * [29] K. Okrasa and P. Rzążewski.  Complexity of the list homomorphism problem in hereditary graph classes.  In M. Bläser and B. Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 54:1–54:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [30] M. Pilipczuk, M. Pilipczuk, and P. Rzążewski.  Quasi-polynomial-time algorithm for Independent Set in $P_{t}$-free graphs via shrinking the space of induced paths.  In H. V. Le and V. King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 204–209. SIAM, 2021.
  * [31] S. Spirkl, M. Chudnovsky, and M. Zhong.  Four-coloring $P_{6}$-free graphs.  In T. M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1239–1256. SIAM, 2019.
  * [32] W. Xia, J. Jooken, J. Goedgebeur, and S. Huang.  Critical $(P_{5},\text{dart})$-free graphs.  In W. Wu and J. Guo, editors, Combinatorial Optimization and Applications - 17th International Conference, COCOA 2023, Hawaii, HI, USA, December 15-17, 2023, Proceedings, Part II, volume 14462 of Lecture Notes in Computer Science, pages 390–402. Springer, 2023.
  * [33] W. Xia, J. Jooken, J. Goedgebeur, and S. Huang.  Some results on critical $(P_{5},H)$-free graphs.  CoRR, abs/2403.05611, 2024.

## Appendix: Implementation and testing of Algorithm 1

##### Details related to the efficient implementation of Algorithm 1.

Some care is needed in order to make the implementation of Algorithm 1 run
fast in practice. For example, if it is necessary to verify whether or not a
graph simultaneously has properties A and B, it is not necessary to verify
property B if one already knows that property A does not hold. Moreover, the
time needed to verify one property can be drastically different from the time
needed to verify another one. For this reason, we experimentally determined
that it is beneficial to first test for $F$-freeness, then test for
$H$-colorability (if still necessary), and finally test for isomorphism (if
still necessary). This agrees with the experimental observations from [14] for
$k$-coloring. For isomorphism testing, we used the program nauty [28] for
computing the canonical form of a graph. This is stored in a balanced binary
search tree to allow efficient insertion and lookup.

Since the graphs that we deal with in this paper are all small, we represent
sets internally as bitvectors. This allows the hardware to efficiently support
standard operations such as the union or intersection of sets. For example,
when the algorithm adds a new vertex $x$ and edges between $x$ and previous
vertices in all possible ways, the algorithm keeps track of a set of edges
that would result in an induced $K_{3}$ after adding the edge. Bitvectors
allow the algorithm to efficiently iterate over only those edges that would
not result in an induced $K_{3}$ (note that, except for $K_{3}$, all minimal
obstructions to $C_{5}$-coloring are $K_{3}$-free). The source code of our
algorithm is made publicly available at [1].

##### Independent verifications and sanity checks.

Apart from Algorithm 1, we also implemented other algorithms to independently
verify some of our results and reproduce existing results from the literature.
All results are in agreement and this provides strong evidence for the
correctness of our implementation. More precisely, we adapted our algorithm to
find minimal obstructions to $H$-coloring which are $\\{F_{1},F_{2}\\}$-free
for several triples $(H,F_{1},F_{2})$ of graphs. Amongst others, this allowed
us to reproduce already known exhaustive lists of
$\\{P_{5},\text{dart}\\}$-free minimal obstructions to $k$-coloring (for
$k\in\\{4,5,6\\}$) [32], $\\{P_{5},\text{gem}\\}$-free minimal obstructions to
$k$-coloring (for $k\in\\{3,4\\}$) [5], $\\{P_{5},C_{5}\\}$-free minimal
obstructions to $4$-coloring [20] and $\\{P_{5},H\\}$-free minimal
obstructions to $4$-coloring for each
$H\in\\{K_{1,3}+P_{1},K_{1,4}+P_{1},\overline{K_{3}+2P_{1}}\\}$ [33]. In each
of these cases, our algorithm terminates. Apart from exhaustive generation, we
also used our algorithm to reproduce all $P_{6}$-free minimal obstructions to
$3$-coloring until order 13 [6] and all $\\{P_{7},C_{3}\\}$-free minimal
obstructions to $3$-coloring until order 16 [14]. We also adapted the
algorithm geng [28] to generate the same minimal obstructions for
$C_{5}$-coloring as our Algorithm 1. However, note that by only using geng,
one cannot conclude that there are no larger minimal obstructions than those
found by geng. This further motivates the need for a specialised algorithm
(cf. Algorithm 1).

We also implemented two independent algorithms for verifying whether a graph
$G$ can be $C_{5}$-colored. The first one is a simple recursive backtracking
algorithm that colors the vertices of $G$ one by one, but backtracks as soon
as no valid colors can be found for a given vertex. The second one formulates
the problem as an integer program and uses a mixed integer programming solver
to verify if there are any feasible solutions. A graph $G$ can be
$C_{5}$-colored if and only if the following constraints can be satisfied:

$\displaystyle\sum_{v\in V(C_{5})}x_{u,v}$ $\displaystyle=1$
$\displaystyle\forall u\in V(G)$ (1) $\displaystyle x_{u,v}$
$\displaystyle\leq\sum_{v^{\prime}\in N_{C_{5}}(v)}x_{u^{\prime},v^{\prime}}$
$\displaystyle\forall u\in V(G),u^{\prime}\in N_{G}(u)$ (2) $\displaystyle
x_{u,v}$ $\displaystyle\in\\{0,1\\}$ $\displaystyle\forall u\in V(G),v\in
V(H)$ (3)

Here, constraints (3) indicate the binary domains of the variables $x_{u,v}$;
such a variable will be equal to 1 if vertex $u\in V(G)$ is mapped to vertex
$v\in V(C_{5})$. Constraints (1) ensure that every vertex $u\in V(G)$ must be
mapped to precisely one vertex $v\in V(C_{5})$. Finally, constraints (2)
ensure that if a vertex $u\in V(G)$ is mapped to vertex $v\in V(C_{5})$, then
all neighbors $u^{\prime}\in V(G)$ must be mapped to neighbors $v^{\prime}$ of
$v$ in $C_{5}$.