Search

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,\cdots, 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., 20 pages, 6 figures. An extended abstract of this paper appeared in the proceedings of ISAAC 2018

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role from tree-width and path-width. As such, it is natural to examine if for every tree~$T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving: (1) for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; (2) for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width., Comment: 26 pages, 5 figures; accepted to SIAM Journal on Discrete Mathematics

We continue research into a well-studied family of problems that ask whether the vertices of a given 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 G. We consider the case where G is the class of k-degenerate graphs. This problem is known to be polynomial-time solvable if k = 0 (recognition of bipartite graphs), but 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 study the general k ≥ 1 case for n-vertex graphs of maximum degree k + 2 We show how to find A and B in O(n) time for k = 1, and in O(n 2 ) time for k ≥ 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, proved by Borodin, Kostochka and Toft [DM, 2000] and Matamala [JGT, 2007]. The results also enable us to solve an open problem of Feghali et al. [JGT, 2016]. For a given graph G and positive integer `, the vertex colouring reconfiguration graph of G has as its vertex set the set of `-colourings of G and contains an edge between each pair of colourings that differ on exactly on vertex. We complete the complexity classification of the problem of finding a path in the reconfiguration graph between two given `-colourings of a given graph of maximum degree k.

Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no subgraph isomorphic to $H_1$ or $H_2$. We continue a recent study into the clique-width of $(H_1,H_2)$-free graphs and present three new classes of $(H_1,H_2)$-free graphs of bounded clique-width and one of unbounded clique-width. The four new graph classes have in common that one of their two forbidden induced subgraphs is the diamond (the graph obtained from a clique on four vertices by deleting one edge). To prove boundedness of clique-width for the first three cases we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs. We extend our proof of unboundedness for the fourth case to show that Graph Isomorphism is Graph Isomorphism-complete on the same graph class. We also show the implications of our results for the computational complexity of the Colouring problem restricted to $(H_1,H_2)$-free graphs., Comment: 22 Pages, 2 figures, An extended abstract of this paper will appear in the proceedings of LATA 2015 (LNCS vol. 8977)

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$.

We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $H_1$ and $H_2$ for all but six pairs $(H_1,H_2)$. Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for $(H_1,H_2)$-free graphs to five., Comment: 28 pages, 4 figures

We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph H as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on H-free graphs for every graph H except when \(H=sP_1+P_4\) for some \(s\ge 1\). As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for \((sP_1+P_4)\)-free graphs for every \(s\ge 1\).

Daligault, Rao and Thomass\'e asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (JCTB 2017+) gave a negative answer to this question, but their counterexample is a class that can only be characterised by infinitely many forbidden induced subgraphs. This raises the issue of whether the question has a positive answer for finitely defined hereditary graph classes. Apart from two stubborn cases, this has been confirmed when at most two induced subgraphs $H_1,H_2$ are forbidden. We confirm it for one of the two stubborn cases, namely for the $(H_1,H_2)=(\mbox{triangle},P_2+P_4)$ case, by proving that the class of $(\mbox{triangle},P_2+P_4)$-free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of $3$-partite graphs. We also use this technique to prove that the class of $(\mbox{triangle},P_1+P_5)$-free graphs, which is known to have bounded clique-width, is well-quasi-ordered. Our results enable us to complete the classification of graphs $H$ for which the class of $(\mbox{triangle},H)$-free graphs is well-quasi-ordered., Comment: 32 pages, 4 figures. An extended abstract of this paper appeared in the proceedings of WG 2017

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., Comment: 39 pages, 7 figures

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 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(n4)-time solvable for graphs of maximum degree at most 6.

The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer $$k\ge 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\ge 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.

The Colouring problem asks whether the vertices of a graph can be coloured with at most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour. A graph is ( H 1 , H 2 ) -free if it has no induced subgraph isomorphic to H 1 or H 2 . A connected graph H 1 is almost classified if Colouring on ( H 1 , H 2 ) -free graphs is known to be polynomial-time solvable or NP -complete for all but finitely many connected graphs H 2 . We show that every connected graph H 1 apart from the claw K 1 , 3 and the 5-vertex path P 5 is almost classified. We also prove a number of new hardness results for Colouring on ( 2 P 2 , H ) -free graphs. This enables us to list all graphs H for which the complexity of Colouring is open on ( 2 P 2 , H ) -free graphs and all graphs H for which the complexity of Colouring is open on ( P 5 , H ) -free graphs. In fact we show that these two lists coincide. Moreover, we show that the complexities of Colouring for ( 2 P 2 , H ) -free graphs and for ( P 5 , H ) -free graphs are the same for all known cases.

A vertex or an edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of testing whether a graph has a critical vertex or a critical edge, respectively. We give a complete classification of the complexity of both problems for 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 one. Hence, we obtain the same classification for the problem of testing if a graph has an edge whose contraction reduces the chromatic number by one. As a consequence of our results, we are also able to complete the complexity classification of the more general vertex deletion and edge contraction blocker problems for H-free graphs when the graph parameter is the chromatic number.

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstadt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstadt, Le, and Mosca erroneously claimed that the gem and co-gem are the only two 1-vertex P4-extensions H for which the class of H-free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we find four new classes of H-free chordal graphs of bounded clique-width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H-free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of inline image-free graphs has bounded clique-width via a reduction to K4-free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique-width of H-free weakly chordal graphs.

graph is (H1;H2)-free for a pair of graphs H1;H2 if it contains no induced subgraph isomorphic to H1 or H2. In 2001, Kral’, Kratochvil, Tuza, and Woeginger initiated a study into the complexity of Colouring for (H1;H2)-free graphs. Since then, others have tried to complete their study, but many cases remain open. We focus on those (H1;H2)-free graphs where H2 is H1, the complement of H1. 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;H)-free graphs for all cases except when H = sP1 + P3 for s 3 or H = sP1 + P4 for s 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 (Pr; Pr)-free graphs.

Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class $${{\mathcal {H}}}$$ . There are both polynomial-time solvable and NP-complete results in this direction, depending on $${{\mathcal {H}}}$$ . We present a general framework for the problem if $$\mathcal{H}$$ is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where $${{\mathcal {H}}}$$ is the class of outerplanar graphs and $${{\mathcal {H}}}$$ is the class of graphs of pathwidth at most 2.

A graph H is a square root of a graph G, or equivalently, G is the square of H, 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. The problem of testing whether a graph admits a square root which belongs to some specified graph class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ is called the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ-Square Root problem. By showing boundedness of treewidth we prove that Square Root is polynomial-time solvable on some classes of graphs with small clique number and that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ-Square Root is polynomial-time solvable when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {H}$\end{document}ℋ is the class of cactuses.

We almost completely resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs \(H_1\) and \(H_2\). Schweitzer settled the complexity of this problem restricted to \((H_1,H_2)\)-free graphs for all but a finite number of pairs \((H_1,H_2)\), but without explicitly giving the number of open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. By combining known results with a number of new results, we reduce the number of open cases to seven. By exploiting the strong relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for \((H_1,H_2)\)-free graphs to five.

International audience; A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. 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 one. 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 one.

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and View the MathML source be the minimum size of an F-transversal of G that induces a connected graph. For a class of connected graphs G, we say that the price of connectivity of F-transversals is multiplicative if, for all G∈G, View the MathML source is bounded by a constant, and additive if View the MathML source is bounded by a constant. The price of connectivity is identical if tF(G) and View the MathML source are always equal and unbounded if View the MathML source cannot be bounded in terms of tF(G). We study classes of graphs characterized by one forbidden induced subgraph H and F-transversals where F contains an infinite number of cycles and, possibly, also one or more anticycles or short paths. We determine exactly those classes of connected H-free graphs where the price of connectivity of these F-transversals is unbounded, multiplicative, additive, or identical. In particular, our tetrachotomies extend known results for the case when F is the family of all cycles.

The Induced Disjoint Paths problem is to test whether an graph G on n vertices with k distinct pairs of vertices ( s i , t i ) contains paths P 1 , ź , P k such that P i connects s i and t i for i = 1 , ź , k , and P i and P j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1 ź i < j ź k . We present a linear-time algorithm that solves Induced Disjoint Paths and finds the corresponding paths (if they exist) on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs ( s i , t i ) are not necessarily distinct. In both cases, if a representation of the graph is given, then the algorithms run in O ( n + k ) time.

For a positive integer k, a k-coloring of a graph inline image is a mapping inline image such that inline image whenever inline image. The COLORING problem is to decide, for a given G and k, whether a k-coloring of G exists. If k is fixed (i.e., it is not part of the input), we have the decision problem k-COLORING instead. We survey known results on the computational complexity of COLORING and k-COLORING 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 coloring, or where lists of permissible colors are given for each vertex.

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.

A graph G contains a graph H as a pivot-minor if H can be obtained from G by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. However, so far, pivot-minors have only been studied from a structural perspective. We initiate a systematic study into their complexity aspects. We first prove that the Pivot-Minor problem, which asks if a given graph G contains a given graph H as a pivot-minor, is NP-complete. If H is not part of the input, we denote the problem by H-Pivot-Minor. We give a certifying polynomial-time algorithm for H -Pivot-Minor for every graph H with \(|V(H)|\le 4\) except when \(H \in \{K_4,C_3+ P_1,4P_1\}\), via a structural characterization of H-pivot-minor-free graphs in terms of a set \(\mathcal{F}_H\) of minimal forbidden induced subgraphs.

The complexity of {\sc Colouring} is fully understood for $H$-free graphs, but there are still major complexity gaps if two induced subgraphs $H_1$ and $H_2$ are forbidden. Let $H_1$ be the $s$-vertex cycle $C_s$ and $H_2$ be the $t$-vertex path $P_t$. We show that {\sc Colouring} is polynomial-time solvable for $s=4$ and $t\leq 6$, strengthening several known results. Our main approach is to initiate a study into the boundedness of the clique-width of atoms (graphs with no clique cutset) of a hereditary graph class. We first show that the classifications of boundedness of clique-width of $H$-free graphs and $H$-free atoms coincide. We then show that this is not the case if two graphs are forbidden: we prove that $(C_4,P_6)$-free atoms have clique-width at most~18. Our key proof ingredients are a divide-and-conquer approach for bounding the clique-width of a subclass of $C_4$-free graphs and the construction of a new bound on the clique-width for (general) graphs in terms of the clique-width of recursively defined subgraphs induced by homogeneous pairs and triples of sets. As a complementary result we prove that {\sc Colouring} is \NP-complete for $s=4$ and $t\geq 9$, which is the first hardness result on {\sc Colouring} for $(C_4,P_t)$-free graphs. Combining our new results with known results leads to an almost complete dichotomy for \cn restricted to $(C_s,P_t)$-free graphs., Comment: An extended abstract of this paper appeared in the proceedings of STACS 2018. http://drops.dagstuhl.de/opus/volltexte/2018/8492/pdf/LIPIcs-STACS-2018-35.pdf

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. On the other hand, the problem is known to be polynomial-time solvable for \(sP_2\)-free graphs for any integer \(s\ge 1\). We prove that it is also polynomial-time solvable for \((sP_1+P_5)\)-free graphs for every integer \(s\ge ~0\).

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.

A graph is H-free if it does not contain an induced subgraph isomorphic to H. For every integer k and every graph H, we determine the computational complexity of k- Edge Colouring for H-free graphs.

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ-coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper coloring by changing the color of one vertex. We show an analogue of Brooks' Theorem by proving that from any k-coloring, inline image, a Δ-coloring of G can be obtained by a sequence of inline image recolorings using only the original k colors unless – G is a complete graph or a cycle with an odd number of vertices, or – inline image, G is Δ-regular and, for each vertex v in G, no two neighbors of v are colored alike. We use this result to study the reconfiguration graph inline image of the k-colorings of G. The vertex set of inline image is the set of all possible k-colorings of G and two colorings are adjacent if they differ on exactly one vertex. We prove that for inline image, inline image consists of isolated vertices and at most one further component that has diameter inline image. This result enables us to complete both a structural and an algorithmic characterization for reconfigurations of colorings of graphs of bounded maximum degree.

Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (WG 2015) gave a negative answer to this question, but their counterexample is a class that can only be characterised by infinitely many forbidden induced subgraphs. This raises the issue of whether their question has a positive answer for finitely defined hereditary graph classes. Apart from two stubborn cases, this has been confirmed when at most two induced subgraphs H1,H2H1,H2 are forbidden. We confirm it for one of the two stubborn cases, namely for the case (H1,H2)=(triangle,P2+P4)(H1,H2)=(triangle,P2+P4) by proving that the class of (triangle,P2+P4)(triangle,P2+P4) -free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of 3-partite graphs. We also use this technique to completely determine which classes of (triangle,H)(triangle,H) -free graphs are well-quasi-ordered.

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.

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., Comment: 9 pages, 2 figures

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.

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.

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H-Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP-complete cases depending on the choice of H. Moreover, when G is AT-free, chordal or planar, we show that H-Minor Edit is polynomial-time solvable for all graphs H.

Let fvs$(G)$ and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph $G$, respectively. The price of connectivity for feedback vertex set (poc-fvs) for a class of graphs ${\cal G}$ is defined as the maximum ratio $\mbox{cfvs}(G)/\mbox{fvs}(G)$ over all connected graphs $G\in {\cal G}$. We study the poc-fvs for graph classes defined by a finite family ${\cal H}$ of forbidden induced subgraphs. We characterize exactly those finite families ${\cal H}$ for which the poc-fvs for ${\cal H}$-free graphs is upper bounded by a constant. Additionally, for the case where $|{\cal H}|=1$, we determine exactly those graphs $H$ for which there exists a constant $c_H$ such that $\mbox{cfvs}(G)\leq \mbox{fvs}(G) + c_H$ for every connected $H$-free graph $G$, as well as exactly those graphs $H$ for which we can take $c_H=0$.

Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these two settings: we give a sufficient condition on a graph class for the vertex deletion variant to be co-NP-hard even if d=k=1d=k=1 ; in addition we prove that the vertex deletion variant is co-NP-hard for triangle-free graphs even if d=k=1d=k=1 ; we prove that the edge contraction variant is NP-hard for bipartite graphs but linear-time solvable for trees. By combining our new results with known ones we are able to give full complexity classifications for both variants restricted to H-free graphs. D. Paulusma received support from EPSRC (EP/K025090/1).

The stable roommates problem with payments has as input a graph G=(V,E)G=(V,E) with an edge weighting w:E→R≥0w:E→R≥0 and the problem is to find a stable solution. A solution is a matching MM with a vector p∈R≥0V that satisfies pu+pv=w(uv)pu+pv=w(uv) for all uv∈Muv∈M and pu=0pu=0 for all uu unmatched in MM. A solution is stable if it prevents blocking pairs, i.e., pairs of adjacent vertices uu and vv with pu+pv

For an integer k>=1, a graph G is k-colorable if there exists a mapping c:V"G->{1,...,k} such that c(u) c(v) whenever u and v are two adjacent vertices. For a fixed integer k>=1, the k-Coloring problem is that of testing whether a given graph is k-colorable. The girth of a graph G is the length of a shortest cycle in G. For any fixed g>=4 we determine a lower bound @?(g), such that every graph with girth at least g and with no induced path on @?(g) vertices is 3-colorable. We also show that for all fixed integers k,@?>=1, thek-Coloring problem can be solved in polynomial time for graphs with no induced cycle on four vertices and no induced path on @? vertices. As a consequence, for all fixed integers k,@?>=1 and g>=5, the k-Coloring problem can be solved in polynomial time for graphs with girth at least g and with no induced path on @? vertices. This result is best possible, as we prove the existence of an integer @?^*, such that already 4-Coloring is NP-complete for graphs with girth 4 and with no induced path on @?^* vertices.

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k-Coloring problem requires in addition that every vertex u must receive a color from some given set L(u)⊆{1,?,k}. Let P n denote the path on n vertices, and G+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. For any two fixed integers k and r, we show that List k-Coloring can be solved in polynomial time for graphs with no induced rP 1+P 5, hereby extending the result of Hoang, Kaminski, Lozin, Sawada and Shu for graphs with no induced P 5. Our result is tight; we prove that for any graph H that is a supergraph of P 1+P 5 with at least 5 edges, already List 5-Coloring is NP-complete for graphs with no induced H.

We prove three complexity results on vertex coloring problems restricted to P"k-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to P"6-free graphs. Recent results of Hoang et al. imply that this problem is polynomially solvable on P"5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P"6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P"6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P"7-free graphs. This problem was known to be polynomially solvable for P"5-free graphs and NP-complete for P"8-free graphs, so there remains one open case.

A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K1,3,P1+P2,P1+P3,P4}{K1,3,P1+P2,P1+P3,P4}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k.

The k-Coloring problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed graph H on at most six vertices, it is known that 3-Coloring is polynomial-time solvable on H-free graphs whenever H is a linear forest, and NP-complete otherwise. By solving the missing case P"2+P"3, we prove the same result for 4-Coloring provided that H is a fixed graph on at most five vertices.

International audience; The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity was not known for planar graphs. We show that it is polynomial-time solvable on 3-connected planar graphs but NP-hard for 2-connected planar graphs. Our technique for the first result is based on a structural characterization of minimal disconnected cuts in 3-connected math formula-free-minor graphs and on solving a topological minor problem in the dual. In addition we show that the problem of finding a minimal connected cut of size at least 3 is NP-hard for 2-connected apex graphs. Finally, we relax the notion of minimality and prove that the problem of finding a so-called semi-minimal disconnected cut is still polynomial-time solvable on planar graphs.

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. By researching boundedness of the treewidth of a graph, we prove that Square Root is polynomial-time solvable on various graph classes of low clique number that are not minor-closed.

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are NP-complete for general graphs even if d is fixed, we restrict the input graph G to some special graph class. We continue a line of research that considers these problems for subclasses of perfect graphs, but our main results are full classifications, from a computational complexity point of view, for graph classes characterized by forbidding a single induced connected subgraph H.

Daligault, Rao and Thomasse conjectured that if a hereditary class of graphs is well-quasi-ordered by the induced subgraph relation then it has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this conjecture is not true for infinitely defined classes. For finitely defined classes the conjecture is still open. It 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. We reduce the number of open cases for well-quasi-orderability of such classes from 12 to 9. Our results agree with the conjecture and imply that there are only two remaining cases to verify for bigenic classes.

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 (Discrete Appl Math 231:95–112, 2017) and Hatanaka et al. (IEICE Trans Fundam Electron Commun Comput Sci 98(6):1168–1178, 2015). As a third example, we apply the method to the following well-studied 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.

The $$k$$k-colouring reconfiguration problem asks whether, for a given graph $$G$$G, two proper $$k$$k-colourings $$\alpha $$ź and $$\beta $$β of $$G$$G, and a positive integer $$\ell $$l, there exists a sequence of at most $$\ell +1$$l+1 proper $$k$$k-colourings of $$G$$G which starts with $$\alpha $$ź and ends with $$\beta $$β and where successive colourings in the sequence differ on exactly one vertex of $$G$$G. We give a complete picture of the parameterized complexity of the $$k$$k-colouring reconfiguration problem for each fixed $$k$$k when parameterized by $$\ell $$l. First we show that the $$k$$k-colouring reconfiguration problem is polynomial-time solvable for $$k=3$$k=3, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $$k \ge 4$$kź4, we show that the $$k$$k-colouring reconfiguration problem, when parameterized by $$\ell $$l, is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.

Let GG be a bipartite graph, and let HH be a bipartite graph with a fixed bipartition (BH,WH)(BH,WH). We consider three different, natural ways of forbidding HH as an induced subgraph in GG. First, GG is HH-free if it does not contain HH as an induced subgraph. Second, GG is strongly HH-free if no bipartition of GG contains an induced copy of HH in a way that respects the bipartition of HH. Third, GG is weakly HH-free if GG has at least one bipartition that does not contain an induced copy of HH in a way that respects the bipartition of HH. Lozin and Volz characterized all bipartite graphs HH for which the class of strongly HH-free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of HH-freeness.