
A colouring of a graph $G=(V,E)$ is a function $c: V\rightarrow\{1,2,\ldots
\}$ such that $c(u)\neq c(v)$ for every $uv\in E$. A $k$regular list
assignment of $G$ is a function $L$ with domain $V$ such that for every $u\in
V$, $L(u)$ is a subset of $\{1, 2, \dots\}$ of size $k$. A colouring $c$ of $G$
respects a $k$regular list assignment $L$ of $G$ if $c(u)\in L(u)$ for every
$u\in V$. A graph $G$ is $k$choosable if for every $k$regular list assignment
$L$ of $G$, there exists a colouring of $G$ that respects $L$. We may also ask
if for a given $k$regular list assignment $L$ of a given graph $G$, there
exists a colouring of $G$ that respects $L$. This yields the $k$Regular List
Colouring problem. For $k\in \{3,4\}$ we determine a family of classes ${\cal
G}$ of planar graphs, such that either $k$Regular List Colouring is
NPcomplete for instances $(G,L)$ with $G\in {\cal G}$, or every $G\in {\cal
G}$ is $k$choosable. By using known examples of non$3$choosable and
non$4$choosable graphs, this enables us to classify the complexity of
$k$Regular List Colouring restricted to planar graphs, planar bipartite
graphs, planar trianglefree graphs and to planar graphs with no $4$cycles and
no $5$cycles. We also classify the complexity of $k$Regular List Colouring
and a number of related colouring problems for graphs with bounded maximum
degree.

Deciding whether a given graph has a square root is a classical problem that
has been studied extensively both from graph theoretic and from algorithmic
perspectives. The problem is NPcomplete in general, and consequently
substantial effort has been dedicated to deciding whether a given graph has a
square root that belongs to a particular graph class. There are both
polynomialtime solvable and NPcomplete cases, depending on the graph class.
We contribute with new results in this direction. Given an arbitrary input
graph G, we give polynomialtime algorithms to decide whether G has an
outerplanar square root, and whether G has a square root that is of pathwidth
at most 2.

We introduce in a general setting a dynamic programming method for solving
reconfiguration problems. Our method is based on contracted solution graphs,
which are obtained from solution graphs by performing an appropriate series of
edge contractions that decrease the graph size without losing any critical
information needed to solve the reconfiguration problem under consideration.
Our general framework captures the approach behind known reconfiguration
results of Bonsma (2012) and Hatanaka, Ito and Zhou (2014). As a third example,
we apply the method to the following problem: given two $k$colorings $\alpha$
and $\beta$ of a graph $G$, can $\alpha$ be modified into $\beta$ by recoloring
one vertex of $G$ at a time, while maintaining a $k$coloring throughout? This
problem is known to be PSPACEhard even for bipartite planar graphs and $k=4$.
By applying our method in combination with a thorough exploitation of the graph
structure we obtain a polynomial time algorithm for $(k2)$connected chordal
graphs.

A simple game $(N,v)$ is given by a set $N$ of $n$ players and a partition of
$2^N$ into a set $\mathcal{L}$ of losing coalitions $L$ with value $v(L)=0$
that is closed under taking subsets and a set $\mathcal{W}$ of winning
coalitions $W$ with $v(W)=1$. Simple games with $\alpha= \min_{p\geq
0}\max_{W\in {\cal W},L\in {\cal L}} \frac{p(L)}{p(W)}<1$ are known as weighted
voting games. Freixas and Kurz (IJGT, 2014) conjectured that $\alpha\leq
\frac{1}{4}n$ for every simple game $(N,v)$. We confirm this conjecture for two
complementary cases, namely when all minimal winning coalitions have size $3$
and when no minimal winning coalition has size $3$. As a general bound we prove
that $\alpha\leq \frac{2}{7}n$ for every simple game $(N,v)$. For complete
simple games, Freixas and Kurz conjectured that $\alpha=O(\sqrt{n})$. We prove
this conjecture up to a $\ln n$ factor. We also prove that for graphic simple
games, that is, simple games in which every minimal winning coalition has size
2, computing $\alpha$ is \NPhard, but polynomialtime solvable if the
underlying graph is bipartite. Moreover, we show that for every graphic simple
game, deciding if $\alpha<a$ is polynomialtime solvable for every fixed $a>0$.

The kColouring problem is to decide if the vertices of a graph can be
coloured with at most k colours for a fixed integer k such that no two adjacent
vertices are coloured alike. If each vertex u must be assigned a colour from a
prescribed list L(u) \subseteq {1, ..., k}, then we obtain the List kColouring
problem. A graph G is Hfree if G does not contain H as an induced subgraph. We
continue an extensive study into the complexity of these two problems for
Hfree graphs. The graph (P_r+P_s) is the disjoint union of the rvertex path
P_r and the svertex path P_s. We prove that List 3Colouring is
polynomialtime solvable for (P_2+P_5)free graphs and for (P_3+P_4)free
graphs. Combining our results with known results yields complete complexity
classifications of 3Colouring and List 3Colouring on Hfree graphs for all
graphs H up to seven vertices. We also prove that 5Colouring is NPcomplete
for (P_3+P_5)free graphs.

A disconnected cut of a connected graph is a vertex cut that itself also
induces a disconnected subgraph. The decision problem whether a graph has a
disconnected cut is called Disconnected Cut. This problem is closely related to
several homomorphism and contraction problems, and fits in an extensive line of
research on vertex cuts with additional properties. It is known that
Disconnected Cut is NPhard on general graphs, while polynomialtime algorithms
are known for several graph classes. However, the complexity of the problem on
clawfree graphs remained an open question. Its connection to the complexity of
the problem to contract a clawfree graph to the 4vertex cycle $C_4$ led Ito
et al. (TCS 2011) to explicitly ask to resolve this open question.
We prove that Disconnected Cut is polynomialtime solvable on clawfree
graphs, answering the question of Ito et al. The centerpiece of our result is a
novel decomposition theorem for clawfree graphs of diameter 2, which we
believe is of independent interest and expands the research line initiated by
Chudnovsky and Seymour (JCTB 20072012) and Hermelin et al. (ICALP 2011). On
our way to exploit this decomposition theorem, we characterize how disconnected
cuts interact with certain cobipartite subgraphs, and prove two further novel
algorithmic results, namely Disconnected Cut is polynomialtime solvable on
circulararc graphs and line graphs.

The Connected Vertex Cover problem is to decide if a graph G has a vertex
cover of size at most $k$ that induces a connected subgraph of $G$. This is a
wellstudied problem, known to be NPcomplete for restricted graph classes,
and, in particular, for $H$free graphs if $H$ is not a linear forest (a graph
is $H$free if it does not contain $H$ as an induced subgraph). It is easy to
see that Connected Vertex Cover is polynomialtime solvable for $P_4$free
graphs. We continue the search for tractable graph classes: we prove that it is
also polynomialtime solvable for $(sP_1+P_5)$free graphs for every integer
$s\geq 0$.

The Surjective HColouring problem is to test if a given graph allows a
vertexsurjective homomorphism to a fixed graph H. The complexity of this
problem has been well studied for undirected (partially) reflexive graphs. We
introduce endotriviality, the property of a structure that all of its
endomorphisms that do not have range of size 1 are automorphisms, as a means to
obtain complexitytheoretic classifications of Surjective HColouring in the
case of reflexive digraphs.
Chen [2014] proved, in the setting of constraint satisfaction problems, that
Surjective HColouring is NPcomplete if H has the property that all of its
polymorphisms are essentially unary. We give the first concrete application of
his result by showing that every endotrivial reflexive digraph H has this
property. We then use the concept of endotriviality to prove, as our main
result, a dichotomy for Surjective HColouring when H is a reflexive
tournament: if H is transitive, then Surjective HColouring is in NL, otherwise
it is NPcomplete.
By combining this result with some known and new results we obtain a
complexity classification for Surjective HColouring when H is a partially
reflexive digraph of size at most 3.

We perform a systematic study in the computational complexity of the
connected variant of three related transversal problems: Vertex Cover, Feedback
Vertex Set, and Odd Cycle Transversal. Just like their original counterparts,
these variants are NPcomplete for general graphs. A graph $G$ is $H$free for
some graph $H$ if $G$ contains no induced subgraph isomorphic to $H$. It is
known that Connected Vertex Cover is NPcomplete even for $H$free graphs if
$H$ contains a claw or a cycle. We show that the two other connected variants
also remain NPcomplete if $H$ contains a cycle or claw. In the remaining case
$H$ is a linear forest. We show that Connected Vertex Cover, Connected Feedback
Vertex Set, and Connected Odd Cycle Transversal are polynomialtime solvable
for $sP_2$free graphs for every constant $s\geq 1$. For proving these results
we use known results on the price of connectivity for vertex cover, feedback
vertex set, and odd cycle transversal. This is the first application of the
price of connectivity that results in polynomialtime algorithms.

We continue research into a wellstudied family of problems that ask whether
the vertices of a graph can be partitioned into sets $A$ and~$B$, where $A$ is
an independent set and $B$ induces a graph from some specified graph class
${\cal G}$. We let ${\cal G}$ be the class of $k$degenerate graphs. This
problem is known to be polynomialtime solvable if $k=0$ (bipartite graphs) and
NPcomplete if $k=1$ (nearbipartite graphs) even for graphs of maximum degree
$4$. Yang and Yuan [DM, 2006] showed that the $k=1$ case is polynomialtime
solvable for graphs of maximum degree $3$. This also follows from a result of
Catlin and Lai [DM, 1995]. We consider graphs of maximum degree $k+2$ on $n$
vertices. We show how to find $A$ and $B$ in $O(n)$ time for $k=1$, and in
$O(n^2)$ time for $k\geq 2$. Together, these results provide an algorithmic
version of a result of Catlin [JCTB, 1979] and also provide an algorithmic
version of a generalization of Brook's Theorem, which was proven in a more
general way by Borodin, Kostochka and Toft [DM, 2000] and Matamala [JGT, 2007].
Moreover, the two results enable us to complete the complexity classification
of an open problem of Feghali et al. [JGT, 2016]: finding a path in the vertex
colouring reconfiguration graph between two given $\ell$colourings of a graph
of maximum degree $k$.

The NearBipartiteness problem is that of deciding whether or not the
vertices of a graph can be partitioned into sets $A$ and $B$, where $A$ is an
independent set and $B$ induces a forest. The set $A$ in such a partition is
said to be an independent feedback vertex set. Yang and Yuan proved that
NearBipartiteness is polynomialtime solvable for graphs of diameter 2 and
NPcomplete for graphs of diameter 4. We show that NearBipartiteness is
NPcomplete for graphs of diameter 3, resolving their open problem. We also
generalise their result for diameter 2 by proving that even the problem of
computing a minimum independent feedback vertex is polynomialtime solvable for
graphs of diameter 2.

The NPcomplete problem Feedback Vertex Set is that of deciding whether or
not it is possible, for a given integer $k\geq 0$, to delete at most $k$
vertices from a given graph so that what remains is a forest. The variant in
which the deleted vertices must form an independent set is called Independent
Feedback Vertex Set and is also NPcomplete. In fact, even deciding if an
independent feedback vertex set exists is NPcomplete and this problem is
closely related to the $3$Colouring problem, or equivalently, to the problem
of deciding whether or not a graph has an independent odd cycle transversal,
that is, an independent set of vertices whose deletion makes the graph
bipartite. We initiate a systematic study of the complexity of Independent
Feedback Vertex Set for $H$free graphs. We prove that it is NPcomplete if $H$
contains a claw or cycle. Tamura, Ito and Zhou proved that it is
polynomialtime solvable for $P_4$free graphs. We show that it remains
polynomialtime solvable for $P_5$free graphs. We prove analogous results for
the Independent Odd Cycle Transversal problem, which asks whether or not a
graph has an independent odd cycle transversal of size at most $k$ for a given
integer $k\geq 0$. Finally, in line with our underlying research aim, we
compare the complexity of Independent Feedback Vertex Set for $H$free graphs
with the complexity of $3$Colouring, Independent Odd Cycle Transversal and
other related problems.

A vertex or edge in a graph is critical if its deletion reduces the chromatic
number of the graph by 1. We consider the problems of deciding whether a graph
has a critical vertex or edge, respectively. We give a complexity dichotomy for
both problems restricted to $H$free graphs, that is, graphs with no induced
subgraph isomorphic to $H$. Moreover, we show that an edge is critical if and
only if its contraction reduces the chromatic number by 1. Hence, we also
obtain a complexity dichotomy for the problem of deciding if a graph has an
edge whose contraction reduces the chromatic number by 1.

We study the following problem: for given integers $d$, $k$ and graph $G$,
can we reduce some fixed graph parameter $\pi$ of $G$ by at least $d$ via at
most $k$ graph operations from some fixed set $S$? As parameters we take the
chromatic number $\chi$, clique number $\omega$ and independence number
$\alpha$, and as operations we choose the edge contraction ec and vertex
deletion vd. We determine the complexity of this problem for $S=\{\mbox{ec}\}$
and $S=\{\mbox{vd}\}$ and $\pi\in \{\chi,\omega,\alpha\}$ for a number of
subclasses of perfect graphs. We use these results to determine the complexity
of the problem for $S=\{\mbox{ec}\}$ and $S=\{\mbox{vd}\}$ and $\pi\in
\{\chi,\omega,\alpha\}$ restricted to $H$free graphs.

Testing if a given graph $G$ contains the $k$vertex path $P_k$ as a minor or
as an induced minor is trivial for every fixed integer $k\geq 1$. However, the
situation changes for the problem of checking if a graph can be modified into
$P_k$ by using only edge contractions. In this case the problem is known to be
NPcomplete even if $k=4$. This led to an intensive investigation for testing
contractibility on restricted graph classes. We focus on bipartite graphs.
Heggernes, van 't Hof, L\'{e}v\^{e}que and Paul proved that the problem stays
NPcomplete for bipartite graphs if $k=6$. We strengthen their result from
$k=6$ to $k=5$. We also show that the problem of contracting a bipartite graph
to the $6$vertex cycle $C_6$ is NPcomplete. The cyclicity of a graph is the
length of the longest cycle the graph can be contracted to. As a consequence of
our second result, determining the cyclicity of a bipartite graph is NPhard.

Cliquewidth is an important graph parameter due to its algorithmic and
structural properties. A graph class is hereditary if it can be characterized
by a (not necessarily finite) set ${\cal H}$ of forbidden induced subgraphs. We
initiate a systematic study into the boundedness of cliquewidth of hereditary
graph classes closed under complementation. First, we extend the known
classification for the ${\cal H}=1$ case by classifying the boundedness of
cliquewidth for every set ${\cal H}$ of selfcomplementary graphs. We then
completely settle the ${\cal H}=2$ case. In particular, we determine one new
class of $(H,\overline{H})$free graphs of bounded cliquewidth (as a side
effect, this leaves only six classes of $(H_1,H_2)$free graphs, for which it
is not known whether their cliquewidth is bounded). Once we have obtained the
classification of the ${\cal H}=2$ case, we research the effect of forbidding
selfcomplementary graphs on the boundedness of cliquewidth. Surprisingly, we
show that for a set ${\cal F}$ of selfcomplementary graphs on at least five
vertices, the classification of the boundedness of cliquewidth for
$(\{H,\overline{H}\}\cup {\cal F})$free graphs coincides with the one for the
${\cal H}=2$ case if and only if ${\cal F}$ does not include the bull (the
only nonempty selfcomplementary graphs on fewer than five vertices are $P_1$
and $P_4$, and $P_4$free graphs have cliquewidth at most $2$). Finally, we
discuss the consequences of our results for the Colouring problem.

A graph is $(H_1,H_2)$free for a pair of graphs $H_1,H_2$ if it contains no
induced subgraph isomorphic to $H_1$ or $H_2$. In 2001, Kr\'al',
Kratochv\'{\i}l, Tuza, and Woeginger initiated a study into the complexity of
Colouring for $(H_1,H_2)$free graphs. Since then, others have tried to
complete their study, but many cases remain open. We focus on those
$(H_1,H_2)$free graphs where $H_2$ is $\overline{H_1}$, the complement of
$H_1$. As these classes are closed under complementation, the computational
complexities of Colouring and Clique Cover coincide. By combining new and known
results, we are able to classify the complexity of Colouring and Clique Cover
for $(H,\overline{H})$free graphs for all cases except when $H=sP_1+ P_3$ for
$s\geq 3$ or $H=sP_1+P_4$ for $s\geq 2$. We also classify the complexity of
Colouring on graph classes characterized by forbidding a finite number of
selfcomplementary induced subgraphs, and we initiate a study of $k$Colouring
for $(P_r,\overline{P_r})$free graphs.

A homomorphism from a graph G to a graph H is a vertex mapping f from the
vertex set of G to the vertex set of H such that there is an edge between
vertices f(u) and f(v) of H whenever there is an edge between vertices u and v
of G. The HColouring problem is to decide whether or not a graph G allows a
homomorphism to a fixed graph H. We continue a study on a variant of this
problem, namely the Surjective HColouring problem, which imposes the
homomorphism to be vertexsurjective. We build upon previous results and show
that this problem is NPcomplete for every connected graph H that has exactly
two vertices with a selfloop as long as these two vertices are not adjacent.
As a result, we can classify the computational complexity of Surjective
HColouring for every graph H on at most four vertices.

Daligault, Rao and Thomass\'e asked whether a hereditary class of graphs
wellquasiordered by the induced subgraph relation has bounded cliquewidth.
Lozin, Razgon and Zamaraev recently showed that this is not true for classes
defined by infinitely many forbidden induced subgraphs. However, in the case of
finitely many forbidden induced subgraphs the question remains open and we
conjecture that in this case the answer is positive. The conjecture is known to
hold for classes of graphs defined by a single forbidden induced subgraph $H$,
as such graphs are wellquasiordered and are of bounded cliquewidth if and
only if $H$ is an induced subgraph of $P_4$. For bigenic classes of graphs,
i.e. ones defined by two forbidden induced subgraphs, there are several open
cases in both classifications. In the present paper we obtain a number of new
results on wellquasiorderability of bigenic classes, each of which supports
the conjecture.

The Colouring problem is that of deciding, given a graph $G$ and an integer
$k$, whether $G$ admits a (proper) $k$colouring. For all graphs $H$ up to five
vertices, we classify the computational complexity of Colouring for
$(\mbox{diamond},H)$free graphs. Our proof is based on combining known results
together with proving that the cliquewidth is bounded for $(\mbox{diamond},
P_1+2P_2)$free graphs. Our technique for handling this case is to reduce the
graph under consideration to a $k$partite graph that has a very specific
decomposition. As a byproduct of this general technique we are also able to
prove boundedness of cliquewidth for four other new classes of
$(H_1,H_2)$free graphs. As such, our work also continues a recent systematic
study into the (un)boundedness of cliquewidth of $(H_1,H_2)$free graphs, and
our five new classes of bounded cliquewidth reduce the number of open cases
from 13 to 8.

We generalize two wellknown gametheoretic models by introducing multiple
partners matching games, defined by a graph $G=(N,E)$, with an integer vertex
capacity function $b$ and an edge weighting $w$. The set $N$ consists of a
number of players that are to form a set $M\subseteq E$ of 2player coalitions
$ij$ with value $w(ij)$, such that each player $i$ is in at most $b(i)$
coalitions. A payoff vector is a mapping $p: N \times N \rightarrow {\mathbb
R}$ with $p(i,j)+p(j,i)=w(ij)$ if $ij\in M$ and $p(i,j)=p(j,i)=0$ if $ij\notin
M$. The pair $(M,p)$ is called a solution. A pair of players $i,j$ with $ij\in
E\setminus M$ blocks a solution $(M,p)$ if $i,j$ can form, possibly only after
withdrawing from one of their existing 2player coalitions, a new 2player
coalition in which they are mutually better off. A solution is stable if it has
no blocking pairs.
We give a polynomialtime algorithm that either finds that a given multiple
partners matching game has no stable solution, or obtains a stable solution for
it. We characterize the set of stable solutions of a multiple partners matching
game in two different ways and show how this leads to simple proofs for a
number of known results of Sotomayor (1992,1999,2007) for multiple partners
ssignment games and to generalizations of some of these results to multiple
partners matching games. We also perform a study on the core of the
corresponding cooperative game, where coalitions of any size may be formed. In
particular we show that the standard relation between the existence of a stable
solution and the nonemptiness of the core, which holds in the other models
with payments, is no longer valid for our (most general) model. We also prove
that the problem of deciding if an allocation belongs to the core jumps from
being polynomialtime solvable for $b\leq 2$ to NPcomplete for $b\equiv 3$.

A graph H is a square root of a graph G if G can be obtained from H by adding
an edge between any two vertices in H that are of distance 2. The Square Root
problem is that of deciding whether a given graph admits a square root. This
problem is only known to be NPcomplete for chordal graphs and polynomialtime
solvable for nontrivial minorclosed graph classes and a very limited number
of other graph classes. We prove that Square Root is O(n)time solvable for
graphs of maximum degree 5 and O(n^4)time solvable for graphs of maximum
degree at most 6.

A graph H is a square root of a graph G if G can be obtained from H by the
addition of edges between any two vertices in H that are of distance 2 from
each other. The Square Root problem is that of deciding whether a given graph
admits a square root. We consider this problem for planar graphs in the context
of the "distance from triviality" framework. For an integer k, a planar+kv
graph (or kapex graph) is a graph that can be made planar by the removal of at
most k vertices. We prove that a generalization of Square Root, in which some
edges are prescribed to be either in or out of any solution, has a kernel of
size O(k) for planar+kv graphs, when parameterized by k. Our result is based on
a new edge reduction rule which, as we shall also show, has a wider
applicability for the Square Root problem.

The SnakeintheBox problem is that of finding a longest induced path in an
$n$dimensional hypercube. We prove new lower bounds for the values $n\in
\{11,12,13\}$. The CoilintheBox problem is that of finding a longest induced
cycle in an $n$dimensional hypercube. We prove new lower bounds for the values
$n\in \{12,13\}$.

For a positive integer $k$, a $k$colouring of a graph $G=(V,E)$ is a mapping
$c: V\rightarrow\{1,2,...,k\}$ such that $c(u)\neq c(v)$ whenever $uv\in E$.
The Colouring problem is to decide, for a given $G$ and $k$, whether a
$k$colouring of $G$ exists. If $k$ is fixed (that is, it is not part of the
input), we have the decision problem $k$Colouring instead. We survey known
results on the computational complexity of Colouring and $k$Colouring for
graph classes that are characterized by one or two forbidden induced subgraphs.
We also consider a number of variants: for example, where the problem is to
extend a partial colouring, or where lists of permissible colours are given for
each vertex.