• Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs(1506.06564)

Feb. 7, 2019 math.CO, cs.DM, cs.DS, cs.CC
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 NP-complete 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 triangle-free 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.
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2(1703.05102)

Oct. 6, 2018 cs.DM, cs.DS
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 NP-complete 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 polynomial-time solvable and NP-complete cases, depending on the graph class. We contribute with new results in this direction. Given an arbitrary input graph G, we give polynomial-time algorithms to decide whether G has an outerplanar square root, and whether G has a square root that is of pathwidth at most 2.
• Using Contracted Solution Graphs for Solving Reconfiguration Problems(1509.06357)

July 11, 2018 cs.DS, cs.CC
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 PSPACE-hard 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 $(k-2)$-connected chordal graphs.
• Simple Games versus Weighted Voting Games(1805.02192)

May 6, 2018 cs.GT
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 \NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if $\alpha<a$ is polynomial-time solvable for every fixed $a>0$.
• Colouring (P_r+P_s)-Free Graphs(1804.11091)

April 30, 2018 cs.DS, cs.CC
The k-Colouring 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 k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph (P_r+P_s) is the disjoint union of the r-vertex path P_r and the s-vertex path P_s. We prove that List 3-Colouring is polynomial-time 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 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. We also prove that 5-Colouring is NP-complete for (P_3+P_5)-free graphs.
• Disconnected Cuts in Claw-free Graphs(1803.03663)

March 9, 2018 math.CO, cs.DM, cs.DS, cs.CC
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 NP-hard on general graphs, while polynomial-time algorithms are known for several graph classes. However, the complexity of the problem on claw-free graphs remained an open question. Its connection to the complexity of the problem to contract a claw-free graph to the 4-vertex cycle $C_4$ led Ito et al. (TCS 2011) to explicitly ask to resolve this open question. We prove that Disconnected Cut is polynomial-time solvable on claw-free graphs, answering the question of Ito et al. The centerpiece of our result is a novel decomposition theorem for claw-free graphs of diameter 2, which we believe is of independent interest and expands the research line initiated by Chudnovsky and Seymour (JCTB 2007-2012) 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 polynomial-time solvable on circular-arc graphs and line graphs.
• Connected Vertex Cover for $(sP_1+P_5)$-Free Graphs(1712.08362)

Feb. 28, 2018 math.CO, cs.DM, cs.DS, cs.CC
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 well-studied problem, known to be NP-complete 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 polynomial-time solvable for $P_4$-free graphs. We continue the search for tractable graph classes: we prove that it is also polynomial-time solvable for $(sP_1+P_5)$-free graphs for every integer $s\geq 0$.
• Surjective H-Colouring over Reflexive Digraphs(1709.09486)

Dec. 28, 2017 math.CO, cs.CC
The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, 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 complexity-theoretic classifications of Surjective H-Colouring in the case of reflexive digraphs. Chen  proved, in the setting of constraint satisfaction problems, that Surjective H-Colouring is NP-complete 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 endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for Surjective H-Colouring when H is a reflexive tournament: if H is transitive, then Surjective H-Colouring is in NL, otherwise it is NP-complete. By combining this result with some known and new results we obtain a complexity classification for Surjective H-Colouring when H is a partially reflexive digraph of size at most 3.
• Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity(1706.08050)

Sept. 21, 2017 math.CO, cs.DM, cs.DS, cs.CC
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 NP-complete 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 NP-complete even for $H$-free graphs if $H$ contains a claw or a cycle. We show that the two other connected variants also remain NP-complete 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 polynomial-time 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 polynomial-time algorithms.
• Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration(1707.09817)

July 31, 2017 math.CO, cs.DM, cs.DS
We continue research into a well-studied 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 polynomial-time solvable if $k=0$ (bipartite graphs) and NP-complete if $k=1$ (near-bipartite graphs) even for graphs of maximum degree $4$. Yang and Yuan [DM, 2006] showed that the $k=1$ case is polynomial-time 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$.
• Independent Feedback Vertex Sets for Graphs of Bounded Diameter(1707.09383)

July 28, 2017 math.CO, cs.DM, cs.DS
The Near-Bipartiteness 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 Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete 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 polynomial-time solvable for graphs of diameter 2.
• Independent Feedback Vertex Set for $P_5$-free Graphs(1707.09402)

July 28, 2017 math.CO, cs.DM, cs.DS
The NP-complete 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 NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete 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 NP-complete if $H$ contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for $P_4$-free graphs. We show that it remains polynomial-time 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.
• Critical Vertices and Edges in $H$-free Graphs(1706.09043)

June 27, 2017 math.CO, cs.DM, cs.CC
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.
• Contraction and Deletion Blockers for Perfect Graphs and $H$-free Graphs(1706.09052)

June 27, 2017 math.CO, cs.DM, cs.DS, cs.CC
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.
• Contracting Bipartite Graphs to Paths and Cycles(1706.03750)

June 12, 2017 math.CO, cs.DM, cs.CC
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 NP-complete 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 NP-complete 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 NP-complete. 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 NP-hard.
• Clique-Width for Graph Classes Closed under Complementation(1705.07681)

June 8, 2017 math.CO, cs.DM
Clique-width 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 clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the $|{\cal H}|=1$ case by classifying the boundedness of clique-width for every set ${\cal H}$ of self-complementary 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 clique-width (as a side effect, this leaves only six classes of $(H_1,H_2)$-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the $|{\cal H}|=2$ case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set ${\cal F}$ of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width 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 non-empty self-complementary graphs on fewer than five vertices are $P_1$ and $P_4$, and $P_4$-free graphs have clique-width at most $2$). Finally, we discuss the consequences of our results for the Colouring problem.
• Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide(1607.06757)

June 7, 2017 math.CO, cs.DM, cs.DS, cs.CC
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 self-complementary induced subgraphs, and we initiate a study of $k$-Colouring for $(P_r,\overline{P_r})$-free graphs.
• Surjective H-Colouring: New Hardness Results(1701.02188)

March 26, 2017 math.CO, cs.CC
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 H-Colouring 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 H-Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP-complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of Surjective H-Colouring for every graph H on at most four vertices.
• Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes(1611.03671)

Nov. 11, 2016 math.CO, cs.DM, cs.DS
Daligault, Rao and Thomass\'e asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. 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 well-quasi-ordered and are of bounded clique-width 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 well-quasi-orderability of bigenic classes, each of which supports the conjecture.
• Colouring Diamond-free Graphs(1512.07849)

Sept. 5, 2016 math.CO, cs.DM
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 clique-width 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 by-product of this general technique we are also able to prove boundedness of clique-width 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 clique-width of $(H_1,H_2)$-free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 13 to 8.
• The Stable Fixtures Problem with Payments(1508.06420)

Aug. 31, 2016 cs.GT, cs.DS, cs.CC
We generalize two well-known game-theoretic 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 2-player 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 2-player coalitions, a new 2-player coalition in which they are mutually better off. A solution is stable if it has no blocking pairs. We give a polynomial-time 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 non-emptiness 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 polynomial-time solvable for $b\leq 2$ to NP-complete for $b\equiv 3$.
• Squares of Low Maximum Degree(1608.06142)

Aug. 27, 2016 math.CO, cs.DM, cs.DS
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 NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed 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 Linear Kernel for Finding Square Roots of Almost Planar Graphs(1608.06136)

Aug. 22, 2016 cs.DM, cs.DS
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 k-apex 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.
• New Bounds for the Snake-in-the-Box Problem(1603.05119)

June 16, 2016 math.CO, cs.DM
The Snake-in-the-Box 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 Coil-in-the-Box 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\}$.
• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs(1407.1482)

Feb. 15, 2016 math.CO, cs.DM, cs.CC
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.