In the classic Maximum Weight Independent Set problem, we are given a graph G with a nonnegative weight function on its vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P 6 -free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P 5 -free graphs of Lokshtanov et al. [ 15 ] and the quasipolynomial-time algorithm on P 6 -free graphs of Lokshtanov et al. [ 14 ]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: For every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I .

Abstract The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $$H_1,H_2,\ldots $$ H 1 , H 2 , … ; the graphs in the class are called $$(H_1,H_2,\ldots )$$ ( H 1 , H 2 , … ) -free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For H-free graphs, the complexity is settled for any H on up to seven vertices. There are only two unsolved cases on eight vertices, namely $$2P_4$$ 2 P 4 and $$P_8$$ P 8 . For $$P_8$$ P 8 -free graphs, some partial results are known, but to the best of our knowledge, $$2P_4$$ 2 P 4 -free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on $$(2P_4,C_5)$$ ( 2 P 4 , C 5 ) -free graphs.

Abstract 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,\ldots ,k\},$$ L ( u ) ⊆ { 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$$ P r + P s is the disjoint union of the r-vertex path $$P_r$$ P r and the s-vertex path $$P_s.$$ P s . We prove that List 3-Colouring is polynomial-time solvable for $$(P_2+P_5)$$ ( P 2 + P 5 ) -free graphs and for $$(P_3+P_4)$$ ( 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.

In the classic Maximum Weight Independent Set problem we are given a graph G with a nonnegative weight function on vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P6-free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P5-free graphs of Lokshtanov et al. [11], and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [12]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: for every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I.

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.

We show that for every hereditary permutation property and every ∊0 > 0, there exists an integer M such that if a permutation π is ∊o-far from in the Kendall's tau distance, then a random subpermutation of π of order M has the property P with probability at most ∊0. This settles an open problem whether hereditary permutation properties are strongly testable, i.e., testable with respect to the Kendall's tau distance, which is considered to be the edit distance for permutations. Our method also yields a proof of a conjecture of Hoppen, Kohayakawa, Moreira and Sampaio on the relation of the rectangular distance and the Kendall's tau distance of a permutation from a hereditary property.

A graph $H$ is strongly immersed in $G$ if $G$ is obtained from $H$ by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of $H$ are mapped to distinct vertices of $G$ (branch vertices), and edges of $H$ are mapped to pairwise edge-disjoint paths in $G$, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We show that there exists a function $d\colon N\to N$ such that for all graphs $H$ and $G$, if $G$ contains a strong immersion of the star $K_{1,d(\Delta(H))|V(H)|}$ whose branch vertices are $\Delta(H)$-edge-connected to one another, then $H$ is strongly immersed in $G$. This has a number of structural consequences for graphs avoiding a strong immersion of $H$. In particular, a class $\mathcal{G}$ of simple 4-edge-connected graphs contains all graphs of maximum degree 4 as strong immersions if and only if $\mathcal{G}$ has either unbounded maximum degree or unbounded tree-width.