Combinatorial and Graph-Theoretical Problems and Augmenting Technique

Abstract

The notion of augmenting graphs generalizes Berge’s idea of augmenting chains, which was used by Edmonds in his celebrated so-called Blossom Algorithm for the maximum matching problem (Edmonds, Can J Math 17:449–467, 1965). This method then was developed for more general maximum independent set (MIS) problem, first for claw-free graphs (Minty, J Comb Theory Ser B 28(3):284–304, 1980; Sbihi, Discret Math 29(1):53–76, 1980). Then the method was used extensively for various special cases, for example, S _1,1,2 (or fork)-free graphs (Alekseev, Discret Anal Oper Res Ser 1:3–19, 1999), subclasses of P ₅ free graphs (Boliac and Lozin, Discret Appl Math 131(3):567–575, 2003; Gerber et al., Discret Appl Math 132(1–3):109–119, 2004; Mosca, Discret Appl Math 132(1–3):175–183, 2004; Lozin and Mosca, Inf Process Lett 109(6):319–324, 2009), P ₆-free graphs (Mosca, Discuss Math Graph Theory 32(3):387–401, 2012), S _1,2,l-free graphs (Hertz et al., Inf Process Lett 86(3):311–316, 2003; Hertz and Lozin, The maximum independent set problem and augmenting graphs. In: Graph theory and combinatorial optimization. Springer Science and Business Media, New York, pp. 69–99, 2005), S _1,2,5-free graphs (Lozin and Milanič, Discret Appl Math 156(13):2517–2529, 2008), and for S _1,1,3-free graphs (Dabrowski et al., Graphs Comb 32(4):1339–1352, 2016). In this paper, we will extend the method for some more general graph classes. Our objective is combining these approaches to apply this technique to develop polynomial time algorithms for the MIS problem in some special subclasses of S _2,2,5-free graphs, extending in this way different known results. Moreover, we also consider the augmenting technique for some other combinatorial graph-theoretical problems, for example maximum induced matching, maximum multi-partite induced subgraphs, maximum dissociative set, etc.

1 Introduction

Berge’s lemma [3] states that a matching M (a set of edges without common vertices) of a graph G is maximum (contains the largest number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with M. Edmonds [11] used this idea to develop Blossom Algorithm for this problem. This idea was used first for the Maximum Independent Set problem, i.e. the problem asks for a largest number of vertices set without edges among them, by Sbihi [33] and Minty [28]. Clearly, a matching in a graph G corresponds to an independent set in the line graph of G. Hence, we can use Edmonds’ algorithm to find Maximum Independent Set for line graphs. Sbihi and Minty extended this idea for a more general graph class, say claw-free graph, by showing that an independent set S of a graph G is maximum if and only if there is no augmenting path (a path that starts and ends on vertices not lies in the independent set and alternates between vertices in and not in the independent set) with S. This technique was extended for more general graph classes by using the augmenting graph concept as described as follows.

Definition 1 ([17])

Given a graph G and an independent set S, an induced bipartite subgraph H = (W, B, E) of G is called an augmenting graph for S if (i) W ⊆ S, B ⊆ V (G)∖S, (ii) N(B) ∩ (S∖W) = ∅, and (iii) |B| > |W|.

An augmenting graph H is called minimal if it does not contain any augmenting graph as a proper induced subgraph.

Theorem 1 ([17])

An independent set S in a graph G is maximum if and only if there is no augmenting graph for S.

This theorem suggests the following general approach to find a maximum independent set in a graph G. Begin with any independent set S (may be empty) in G and as long as S admits an augmenting graph H, exchange white and black vertices of H. Clearly, the problem of consecutively finding augmenting graphs and of applying these augmentations is generally NP-hard, as the MIS problem is NP-hard. Moreover, we can restrict ourselves in minimal augmenting graph only. Hence, for a polynomial time solution to some graph class, one has to solve the two following problems:

(P1) :

Find a complete list of (minimal) augmenting graphs.

(P2) :

Develop polynomial time algorithms for detecting (minimal) augmenting graphs.

So far, characterizations of (minimal) augmenting graphs mainly followed the two following directions. In the first approach, augmenting graphs in (S _1,2,k,banner)-free graphs are characterized based on the observation that a banner-free bipartite graph is either C ₄-free or complete. The most general result follows this direction described by Lozin and Milanič [23] for (S _1,2,5,banner)-free graphs.

In the second approach, augmenting graphs of subclasses of P ₅-free graphs are characterized based on the observation showed indepedently by many researchers (e.g., [29]) that every connected P ₅-free bipartite graph is a bipartite-chain graph, i.e. the vertices of each part can be ordered under inclusion of their neighborhood. Based on this property, polynomial solutions were obtained for some subclasses of P ₅-free graphs [4, 16, 25, 29, 30]. It is also worth to notice that the MIS problem is shown polynomially solvable in P ₅-free graphs [22].

In this paper, we try to combine the two above approaches to a subclass of (banner₂,domino)-free graphs (see Figure 1). In particular, we obtain the following theorem.

Fig. 1

S _i,j,k, domino, banner_k, and apple_l

Theorem 2

Given integers m, l, the MIS problem is polynomially solvable in (S _2,2,5 ,banner ₂ ,domino,M _m, K _m,m − e, $R^{1}_{l},R^{2}_{l},$ $R^{3}_{l}$ )-free graphs. (See Figure 4 .)

Obviously, banner and domino are two natural generalizations of P ₅ and banner (banner₁), $R^{1}_{l}$, $R^{2}_{l}$, $R^{3}_{l}$ are generalizations of S _1,2,5. Hence, our result is a generalization of some previous known results for (S _1,2,5, banner)-free graphs [23], (P ₅, K _3,3 − e)-free graphs [16, 25] for (P ₅, K _2,m − e)-free graphs, and some subclasses of S _1,2,2-free graphs [20].

The organization of the paper is as follows. Augmenting graphs for some subclasses of S _2,2,l-free graphs are characterized in Section 2, i.e. to solve Problem P1. Methods for finding such augmenting graphs are described in Section 3, i.e. to solve Problem V2. In Section 4, we summarize some results in using technique for other combinatorial and graph-theoretical problem. Section 5 is a discussion about the issue. Many of long proofs are put in the Appendix part.

Here, we want to collect most of the terminology and notations used in the paper. For those not given here, they will be defined when needed. For those not given, we refer the readers to [5]. Given a graph G = (V, E), for a vertex u, we denote by N(u) := {v ∈ V : uv ∈ E} the neighborhood of u in G. For a subset U ⊂ V (G), we denote by $N(U) := (\bigcup \limits _{u \in U} {N(u)}) \backslash U$ the neighborhood of U. If W, U are two vertex subsets of G, then N _U(W) := N(W) ∩ U. Also, N _U(v) := N(v) ∩ U for a vertex v. Given a graph G = (V, E) and a vertex subset U, we denote by G − U the graph obtained from G by deleting all vertices (together with adjacent edges) in U. For two vertices u, v ∈ V , we write u ∼ v if uv ∈ E. For a vertex u, we denote by d(u) := |N(u)|, the degree of u in G. We also denote by G[U] := G − (V (G)∖U), the subgraph of G induced by U.

2 Augmenting Graphs in Subclasses of (S _2,2,l,banner_l)-Free Graphs

Hertz and Lozin [17] obtained the following observation about minimal augmenting graphs.

Lemma 1 ([17])

If H = (B, W, E) is a minimal augmenting graph for an independent set S of a graph G, then

• 1. H is connected;

• 2. |W| = |B|− 1;

• 3. for every subset U ⊆ W, |U| < |N _B(U)|.

2.1 Redundant Sets and Reduction Sets

Let us report from Section 3 of [23] a general observation on the problem of finding augmenting graphs and let us slightly extend it according to the Remark of Section 3 of [23]. Given an augmenting graph class $\mathcal {A}$, a graph G, and an independent set S, let Problem Augmentation ($\mathcal {A}$) denote the problem of finding augmenting graphs if S admits an augmenting graph in $\mathcal {A}$. Lozin and Milanič [23] showed that in (S _1,2,5,banner)-free graphs, the problem can be reduced to finding augmenting graphs of the form tree¹,…,tree⁶ (see Figure 2) by using redundant set concept. We extend this concept as follows.

Fig. 2

Augmenting trees

Definition 2

In an augmenting graph H = (W, B, E), a vertex subset U is called redundant if

• 1. |U ∩ W| = |U ∩ B| and

• 2. for every vertex b ∈ B∖U, N _W∖U(U ∩ B) ⊆ N _W∖U(b).

Theorem 3

Let $\mathcal {A}_{1}$ and $\mathcal {A}_{2}$ be two classes of augmenting graphs. If there exists a constant k such that, for every augmenting graph $H = (W,B,E) \in \mathcal {A}_{2}$ , there exists a redundant subset U of size at most k such that $H - U \in \mathcal {A}_{1}$ , then Problem Augmentation( $\mathcal {A}_{2}$ ) is polynomially reducible to the problem Augmentation( $\mathcal {A}_{1}$ ).

Proof

Assume that Algorithm Augment ₁(G, S) outputs a subset V ′⊆ V (G) such that G[V ′] is augmenting for S whenever S admits an augmenting graph from $\mathcal {A}_{1}$ (and perhaps even if this is not the case). The procedure also returns ∅ if no augmenting graph is found.

Assume that S admits an augmenting graph $H = (B,W,E) \in \mathcal {A}_{2}$. Then by the theorem’s assumption, H contains a redundant set U of size at most k such that $H - U \in \mathcal {A}_{1}$. It is obvious that the graph H − U is augmenting for S∖U. Moreover, since U is redundant, G″ contains every vertex of H − U, i.e. Steps 1 and 2 have not removed any vertex of H − U. Therefore, Algorithm Augment ₁ must output a non-empty set T. Consequently, Algorithm Augment ₂ also outputs a non-empty set U ∪ T.

We show that G[U ∪ T] is augmenting for S. Indeed, by Step 1, G[U ∪ T] is a bipartite graph. Since T is augmenting for S∖U in G″, |T ∩ S∖U| < |T ∩ V (G″)|. Moreover, since |U ∩ S| = |U ∩ V (G)∖S|, |(T ∪ U) ∩ S| < |(T ∪ U) ∩ V (G)∖S|. By Step 2, N _S(U∖S) ⊆ T ∩ S, i.e. N _S((T ∪ U)∖S) ⊆ (T ∪ U) ∩ S. Hence, the graph G[U ∪ T] is augmenting for S, even if G[T] does not coincide with H − U. Therefore, whenever S admits an augmenting graph in $\mathcal {A}_{2}$, Algorithm Augment ₂ finds an augmenting graph.

To this end, the procedure inspects polynomially many subsets of vertices of the input graph, which results in polynomially many calls of Algorithm Augment ₁. The construction of the graph G″ also is performed in polynomial time. Hence, Problem Augmentation($\mathcal {A}_{2}$) is polynomially reducible to Problem Augmentation ($\mathcal {A}_{1}$).

Algorithm 1 Augment ₂(G, S) (Version 1)

Note that Problem Augmentation($\mathcal {A}_{1}$) becomes Problem (P2) when $\mathcal {A}_{1}$ is the class of all (possible) augmenting graphs.

Moreover, we can also extend the redundant set concept further as follows. If Algorithm Augment ₁ starts with some initialization process (see Algorithm 2), which computes some finite vertex set C such that N _S∖U(U∖S) ⊆ N _S(C∖S), then we can process this initialization procedure in Augment ₂ as in Version 2 and remove the condition that every neighbor in S∖U of black vertices in B∖U covers the neighbor of U in S∖U (see Algorithm 3). More precisely, we have the following definition.

Definition 3

Let $\mathcal {A}_{1}$ and $\mathcal {A}_{2}$ be the two augmenting graph classes. Given an integer k. Assume that there exists a polynomial time procedure finding an augmenting graph in $\mathcal {A}_{1}$ (or deciding such augmenting graph does not exist) and such a procedure has a form as in Algorithm 2, i.e. starts by generating some candidates and from each candidate C, builds up augmenting graphs (Generate ₁(C, G, S)). In an augmenting graph $H = (B,W,E) \in \mathcal {A}_{2}$, a vertex subset U is called a reduction set associated with some key set B ^∗⊆ B ∩ C if |U ∩ B| = |U ∩ W| and N _W∖U(U ∩ B) ⊆ N _W∖U((B ^∗∖U) ∩ B).

And by the above arguments, we have the following observation.

Theorem 4

Let $\mathcal {A}_{1}$ and $\mathcal {A}_{2}$ be the two augmenting graph classes. Then Problem Augmentation( $\mathcal {A}_{2}$ ) is polynomially reducible to Problem Augmentation( $\mathcal {A}_{1}$ ) if there are two integers k ₁, k ₂ such that for every augmenting graph $H = (B,W,E) \in \mathcal {A}_{2}$ , there is a reduction set U of size at most k ₁ associated with a key set B ^∗ of size at most k ₂ such that $H - U \in \mathcal {A}_{1}$.

Algorithm 2 Augment ₁(G, S)

Algorithm 3 Augment ₂(G, S) (Version 2)

2.2 Augmenting Graphs in Subclasses of S _2,k,l-Free Graphs

The following corollary is a consequence of Lemma 1 and was obtained in [23].

Corollary 1 ([23])

Let H = (B, W, E) be a minimal augmenting graph for an independent set S of a graph G. Then for every vertex b ∈ M, there exists a perfect matching between B∖{b} and W in H, i.e. a matching consists of every vertex of B∖{b} and W .

Remark 1

By the above corollary, from now on, given a minimal augmenting graph H = (B, W) and a black vertex b ∈ B, we denote by M such a perfect matching and for every vertex u of H different from b and by μ(u) the matched vertex of u in M. For a subset U ⊆ V (H), we also denote μ(U) := {μ(u) : u ∈ U}.

Corollary 2

Let H = (B, W) be a minimal augmenting graph. Then every white vertex of H is of degree at least two.

We say that G is an (k, m)-extended-chain if G is a tree and contains two vertices a, b such that there exists an induced path P ⊂ G connecting a, b, every vertex of G − P is of distance at most k − 1 from either a or b, and every vertex of G − P has no neighbor in P except possibly a or b and every vertex of G is of degree at most m − 1. The following observation is an extension of Theorem 8 of [17]. The result was announced in [21] without full proof.

Lemma 2 ([21])

For any three integers k, l, and m such that 4 ≤ 2k ≤ l and m ≥ 3, in (S _2,2k,l ,apple $^{l}_{4}$ , apple $^{l}_{6}$ ,…,apple $^{l}_{2k + 2}$ ,K _1,m )-free graphs, there are only finitely many minimal augmenting graphs different from augmenting (2k, m)-extended-chains and not of the form apple _2p . Moreover, if H is of the form augmenting (2k, m)-extended-chain, then every white vertex is of degree two.

Note that in an augmenting graph of the form apple_2p (or augmenting apple for short), the vertex of degree three is white. However, given an augmenting apple H = (B, W, E(H)), where b is the black vertex of degree one and w is the white vertex of degree three. Then U := {b, w} is a redundant set such that H − U is an augmenting chain, a special case of augmenting (k, m)-extended-chain.

2.3 Augmenting Graphs in Subclasses of S _2,2,5-Free Graphs

Now, we try to omit K _1,m from the list of forbidden induced subgraphs by considering (S _2,2,5,banner₂,domino)-free augmenting graphs. We extend the consideration of Section 4 in [23]

Lemma 3

Given a graph G and an (S _2,2,5 ,banner ₂ ,domino)-free minimal augmenting graph H = (B, W, E) for an independent set S, at least one of the following statements is true:

• 1. H belongs to some finite set of augmenting graphs;

• 2. H is an augmenting chain or an augmenting apple (see Figure 1);

• 3. H is an augmenting graph of the form tree ¹ , tree ² , …, tree ⁷ (see Figure 2) or can be reduced by a redundant set containing at most 32 vertices to an augmenting graph of the form tree ¹ , tree ² , …, tree ⁷ ;

• 4. there is a vertex b ∈ B such that b is adjacent to all vertices of W.

Such b of Case 4 is called the augmenting vertex of S, as in [29, 30]. We also call augmenting graphs of the form tree¹, tree², …, tree⁷ as augmenting trees. For Case 4 of Lemma 3, we show that under some restrictions, these augmenting graphs have structural properties similar to P ₅-free augmenting graphs, i.e. being a bipartite-chain by the following observation.

Lemma 4

Given a (domino,banner ₂ )-free graph G, an integer m ≥ 3, and an M _m -free (see Figure 3) minimal augmenting graph H = (B, W, E) for an independent set S such that there exists some black vertex b ∈ B adjacent to every white vertex of W, and |W|≥ 2m + 1, at least one of the following statements is true.

Fig. 3

M _m and Q _p

• 1. H is of the form tree ¹ or there exists a reduction set U of size at most 2m − 2 associated with a key set of size one such that H − U is of the form tree ¹.

• 2. H is a bipartite-chain or there exists a redundant set U of size at most 2m − 2 such that H − U is a bipartite-chain.

Proof

We refer to Lemma 10 for the procedure finding tree¹ and note that such a procedure starts by finding a candidate containing b, i.e. b is adjacent to every white vertex in the augmenting tree¹ and we have the key set B ^∗ := {b}.

Let B = {b, b ₁, …, b _q}, b be the vertex b in Corollary 1, p be the integer p in Lemma 8 such that N _W(b _i) ⊇ N _W(b _j) for every 1 ≤ i ≤ p, i < j ≤ q and |N _W(b _i)| = 1 for every i ≥ p + 1.

If p ≤ m − 1, then U = {b ₁, …, b _p, μ(b ₁), …, μ(b _p)} is a reduction set of size at most 2m − 2 associated with B ^∗ such that H − U is of the form tree¹.

If p ≥ q − m + 1, then U = {b _p+1, …, b _q, μ(b _p+1), …, μ(b _q)} is a redundant set of size at most 2m − 2 such that H − U is a bipartite-chain.

If m ≤ p ≤ q − m, then {b, b ₁, …, b _k−1, b _q−k+1, …, b _q, μ(b _q−k+1), …, μ(b _q)} induces an M _m, a contradiction.

The following observation is a generalization of Lemma 10 in [4] and Theorem 1 in [16] about augmenting graphs in (P ₅, K _2,m − e)-free graphs and (P ₅, K _3,3, − e)-free graphs, respectively.

Lemma 5

Given a graph G, an independent set S of G, an integer m, and a (K _m,m − e)-free minimal augmenting bipartite-chain H = (B, W, E), either

• 1. H has at most 2m − 2 white vertices; or

• 2. H is of the form K _l,l+1 or there is a redundant set of size at most 2m − 4 such that H − U is of the form K _l,l+1 , for some l.

Proof

Assume that |W| = p ≥ 2m − 1. Let W = {w ₁, w ₂, …, w _p} and B = {b ₁, b ₂, …, b _p, b _p+1}. Assume that N _W(b _i) ⊆ N _W(b _j) for i < j. Moreover, by Corollary 1, there exists a perfect matching between B∖{b _p+1} and W. Without loss of generality, assume that b _i ∼ w _i for 1 ≤ i ≤ p. Then we have |N _W(b _i)|≥ i for i = 1, 2, ….

Now, b _i ∼ w _j for every b _i ∈ B and w _j ∈ W such that p − m + 4 ≥ i ≥ m − 1 and p − m + 3 ≥ j ≥ i + 1, otherwise {b, b _p, …, b _p−m+3, b _i, w _j, w _m−1, …, w ₁} induces a K _m,m − e, a contradiction.

Hence, {b, b _p, …, b _m−1, w _p−m+1, …, w ₁} induces a K _{p−m+3,p−m+2} and U := {b _m−2, …, b ₁, w _p, …, w _p−m+2} is a redundant of size 2m − 4 such that H − U is a K _{p−m+3,p−m+2}.

Note that if an augmenting graph contains at most 2m − 2 white vertices, it contains at most 4m − 3 vertices.

3 Finding Augmenting Graphs

Now, we consider Problem (P2), i.e. the problem of finding augmenting graphs characterized in Section 2. Remind that we can enumerate all augmenting graphs of bounded size in polynomial time. Moreover, Hertz and Lozin [17] described a method of finding augmenting graphs of the form K _m,m+1 in banner₂-free graphs. Besides, it is obvious that augmenting apples can be reduced to augmenting chains by a redundant set of size two. Hence, we have to find augmenting extended-chains and augmenting trees.

3.1 Augmenting Extended-Chain and Augmenting Trees

The method for finding augmenting chains in (S _1,2,j,banner)-free graphs has been described by Hertz, Lozin, and Schindl [18]. We have extended this method and obtain the following result, which was published in [21] without proof.

Lemma 6 ([21])

Given integers l and m, where l is even, an (S _2,l,l ,banner _l , $R^{1}_{l}$ , $R^{2}_{l},R^{3}_{l},$ $R^{4}_{l},$ $R^{5}_{l}$ )-free graph G, and an independent set S in G, one can determine whether S admits an augmenting (l, m)-extended-chain in polynomial time (Figure 4).

Fig. 4

$R^{1}_{l}$,$R^{2}_{l},R^{3}_{l},R^{4}_{l}$, and $R^{5}_{l}$

By extending the techniques presented in [23] (finding augmenting trees of the form tree¹, …, tree⁶ in (S _1,2,5, banner)-free graphs), we obtain the following result.

Lemma 7

An augmenting graph of the form tree ¹ , tree ² , …, tree ⁷ can be found in (S _2,2,5 ,banner ₂ )-free graphs in polynomial time.

Together with the method of Lozin and Hertz [17] for finding augmenting graphs of the form K _p,p+1 in banner₂-free graphs, it leads us to the following result.

Corollary 3

Given an integer m, the MIS problem is polynomially solvable in (S _1,2,5 ,banner ₂ ,domino,M _m, K _m,m − e)-free graphs.

Theorem 42 (as well as Corollary 3) is a generalization of the results of Lozin and Milanič for (S _1,2,5, banner)-free graphs [23], of Lozin and Mosca for (P ₅, K _3,3 − e)-free graphs [25], of Gerber et al. [16] for (P ₅, K _2,m − e)-free graphs, and some subclasses of S _1,2,2-free graphs [20]. Note that we used redundant set and reduction set to reduce “near” augmenting complete bipartite graphs to augmenting complete bipartite graphs. This technique is a generalization of method for augmenting $K^{+}_{m,m}$’s in [25].

3.2 The Maximum Independent Set Problem in Further Subclasses of S _2,2,5-Free Graphs

So far, for (S _2,2,5,banner₂,domino,$R^{1}_{l},R^{2}_{l},R^{3}_{l},M_{m}$)-free graphs, we can find every (minimal) augmenting graph in polynomial time except for augmenting bipartite-chains. Mosca in [29] and then in [30] (see also [14, 16]) developed augmenting vertex technique for this issue, which we describe next.

Let S be an independent set of a graph G = (V, E) and v ∈ V ∖S. We denote as in [29], H(v, S) := {w ∈ V ∖(S ∪{v}∪ N(v)) : N _S(w) ⊂ N _S(v)}. Given a graph G = (V, E), an independent set S, and a vertex v ∈ V ∖S, Mosca [29] defined that v is augmenting for S (and that S admits an augmenting vertex), if G[H(v, S)] contains an independent set S _v such that |S _v|≥|N _S(v)|. This implies that H′ := (S _v ∪{v}, N _S(v), E(H′)) is an augmenting graph. Then by Theorem 1 and Lemma 3, we restrict ourselves in the following problem.

Here we use some notations in [30]. Let K be a graph, we denote as K ^(h) the graph obtained from K by adding h + 1 new vertices v, s ₁, …, s _h such that {s ₁, s ₂, …, s _h} induce an independent set, s _i’s dominate K, while v is adjacent only to s _i’s.

By considering the problem of finding augmenting bipartite chains, we obtain the following result as an extension of a similar result in [30] for P ₅-free graphs.

Theorem 5

Given three integers h, l, m and a graph K, if the MIS problem in the (S _2,2,5 ,banner ₂ ,domino, $M_{m},R^{1}_{l},R^{2}_{l},R^{3}_{l},K$ )-free graph class is polynomially solvable, then so it is in the (S _2,2,5 , banner ₂ ,domino, $M_{m},R^{1}_{l},R^{2}_{l},R^{3}_{l},K^{(h)}$ )-free graph class.

Corollary 4

Given two integers h, m and a graph K, if the MIS problem is polynomially solvable in (S _1,2,5 ,banner ₂ ,domino,M _m, K)-free graph class, then so it is the (S _1,2,5 ,banner ₂ ,domino,M _m ,K ^(h) )-free graph class.

Especially, Theorem 5 leads to some interesting polynomially solvable graph classes of the MIS problem. Remind that the MIS problem was proved to be polynomially solvable in P ₅-free graphs [22], (P ₂ + claw)-free graphs [24], 2P ₃-free graphs [26], and pK ₂-free graphs [1], we have the following consequence.

Corollary 5

Given four integers h, l, m, p, the MIS problem is polynomially solvable in the following graph classes (see Figure 5):

Fig. 5

Special graphs in Corollary 5

• 1. (S _2,2,5 ,banner ₂ ,domino, $M_{m},R^{1}_{l},R^{2}_{l},R^{3}_{l},P_{5}^{(h)}$ )-free graphs,

• 2. (S _2,2,5 ,banner ₂ ,domino, $M_{m},R^{1}_{l},R^{2}_{l},R^{3}_{l},(P_{2} + \mathit{\mbox{claw}})^{(2)}$ )-free graphs,

• 3. (S _2,2,5 ,banner ₂ ,domino, $M_{m},R^{1}_{l},R^{2}_{l},R^{3}_{l},(2P_{3})^{(2)}$ )-free graphs, and

• 4. (S _2,2,5 ,banner ₂ ,domino, $M_{m},R^{1}_{l},R^{2}_{l},R^{3}_{l},(pK_{2})^{(h)}$ ).

Let tree_r be the graph of the form tree¹ with parameter r (Figure 2). Let G = (V, E) be a graph, U be a subset of V  and u be a vertex of G outside U. We say that u distinguishes U if u has both a neighbor and a non-neighbor in U. A subset U ⊆ V (G) is called a module in G if it is indistinguishable for any vertex outside U. A module U is trivial if U is a single vertex or V  itself, otherwise it is non-trivial. A graph whose each module is trivial is called prime . It has been shown (for example in [27]) that if the problem is polynomially solvable for every prime graph of a graph class $\mathcal {X}$, then it is also polynomial solvable in $\mathcal {X}$. Using the modular decomposition technique described in [6] for P ₅-free graphs we can extend Case 4., the case h = 2 of the above corollary, as follows.

Corollary 6

Given four integers l, m, p, and r, the MIS problem is polynomially solvable in (S _2,2,5 ,banner ₂ ,domino,M _m , tree _r , $R^{1}_{l},R^{2}_{l},R^{3}_{l},Q_{p}$ )-free graph class (see Figure 3).

Proof

We show that a prime (Q _p,tree_r)-free graph is ((2p + r − 2)K ₂)⁽²⁾-free. Indeed, let G be a prime (Q _p,tree_r)-free graph, and suppose that G contains an induced subgraph Q′ isomorphic to ((2p + r − 2)K ₂)⁽²⁾.

Let T ⊆ V (G) be the subset of vertices of G adjacent to every vertex of the (2p + r − 2)K ₂ of Q′. Since T contains at least two non-adjacent vertices, $\bar {G}[T]$, the complement subgraph of G induced by T, contains a non-trivial component C. Since G is prime, C is not a module. Hence, there exists a vertex v ∈ V (G)∖C distinguishing C, i.e. v ∼ c ₁ and $v \nsim c_{2}$ for some vertices c ₁, c ₂ in C. Moreover, since $\bar {G}[C]$ is connected, we can substitute c ₁, c ₂ by two vertices of the path connecting them and can assume that $c_{1} \nsim c_{2}$ in G.

If v is adjacent to every vertex of the (2p + r − 2)K ₂ of Q′, then v ∈ T and since $v \nsim c_{2}$, v ∈ C, a contradiction. Hence, there exists a vertex c′ of the (2p + r − 2)K ₂ of Q′ such that $c' \nsim v$.

Since G is tree_r-free, v distinguishes at most r − 1 edges of the (2p + r − 2)K ₂ of Q′. Then we have the two following cases.

Case 1 v is adjacent to both end-vertices of at least p edges of the (2p + r − 2)K ₂ of Q′. Then {v, c′, c ₂} together with these p edges induce a Q _p, a contradiction.

Case 2 v is non-adjacent to both end-vertices of at least p edges of the (2p + r − 2)K ₂ of Q′. Then {v, c ₁, c ₂} together with these p edges induce a Q _p, a contradiction (Figure 6).

Fig. 6

Q _p

4 Augmenting Graphs in Other Problems

In [19], we have extended the augmenting graph approach for a more more general combinatorial and graph-theoretical problem, say Maximum Π-set Problem. Given a graph G, the problem asks for a maximum vertex subset such that the induced subgraph satisfies some give properties Π. Here are some examples for the property Π and related problems.

• Maximum k -Independent Set. [13] Π: Every vertex is of degree at most k − 1. Note that the Maximum Independent Set is the case k = 1.

• Maximum k -Path Free Set. Π: The graph contains no path (not necessarily induced) of k vertices (k ≥ 2), also called k-path free. This problem is a dual version of the Minimum Vertex k-Path Cover problem [7].

• Maximum Forest. Π: The graph contains no cycle. This problem is a dual version of the Minimum Feedback Vertex Cover problem [12].

• Maximum Induced Bipartite Subgraph. Π: The graph contains no cycle of odd length.

• Maximum k -Acyclic Set. Π: The graph contains no cycle of length at most k.

• Maximum k -Chordal Set. Π: The graph contains no cycle of length larger than k.

• Maximum k -Cycle Free Set. Π: The graph contains no cycle of length k (k ≥ 3), also called k-cycle free. This problem is a dual version of the Minimum Vertex k-Cycle Cover problem.

• Maximum Induced Matching. [8] Π: Every vertex is of degree one.

• Maximum k -Regular Induced Subgraph. [9] Π: Every vertex is of degree k.

• Maximum k -Regular Induced Bipartite Subgraph. [9] Π: The graph is bipartite and every vertex is of degree k.

• Maximum Induced k -Cliques. Π: Every connected component is a k-clique. This problem is a generalization of Maximum Induced Matching problem (k = 2).

We have considered two special cases of the problem. First, the property Π is hereditary (i.e., if a graph G satisfies Π, then every induced subgraph of G satisfies Π) and additive (i.e., a graph G satisfies Π if and only if every connected component of G satisfies Π). Second, Π is of the form $\mathcal {F}$-induced subgraph, i.e. every connected component of G belongs to some graph set $\mathcal {F}$. In both cases, we have defined the augmenting graphs and the key theorem, says the Π-set is maximum if and only if there exists no augmenting graph. We also have considered a simple case, says the (S _1,2,l,banner_l,K _1,m)-free minimal augmenting graph either belongs to a finite set or is augmenting extended-chain. By showing that we can find augmenting extended-chain in polynomial time for the above problem, we obtained polynomial algorithms for these non-trivial problems in (S _1,2,l,banner_l,K _1,m)-free graphs.

5 Conclusion

In this paper, we have combined the methods applied for P ₅-free graphs and (S _1,2,5,banner)-free graphs to generalize some known results. By extending the method of Lozin and Milanič [23] for (S _1,2,5,banner)-free graphs, we show that the problem can be restricted to finding augmenting chains and augmenting bipartite-chains in (S _2,2,5,banner₂,domino, M _m)-free graphs by using concepts of redundant sets (in the extended senses). It leads us to some generalizations of results about (P ₅, K _2,m − e)-free graphs [4], (P ₅, K _3,3 − e)-free graphs [16], and augmenting vertex in P ₅-free graphs [14, 16, 29, 30]. It also leads to some interesting results in (S _2,2,5,banner₂,domino,M _m)-free graphs, e.g. Corollaries 5 and 6.

Note that S _1,1,2 (fork) and S _0,1,3 (P ₅) are the largest single known forbidden subgraphs, for which the MIS problem is polynomially solvable. For S _i,j,k such that i + j + k ≥ 5, even for subclasses, to the best of our knowledge, there are still not many known results except in some subclasses of P ₆-free graphs, graphs of bounded maximum degree, planar graphs, (S _1,2,5,banner)-free graphs [23], (S _1,1,3, K _p,p)-free graphs [10], and (S _1,2,l,banner_l,K _1,m)-free graphs [19]. Combining different techniques is a potential approach helping us extend these results to tackling the general question about complexity of the MIS problem in S _i,j,k-free graphs.

Besides, by applying a technique, which has been used for P ₅-free graphs, for a larger graph class, e.g. S _2,2,5-free graphs, we believe that it is possible to apply other techniques, which were used in P ₅-free graphs, in S _2,2,l-free graphs.

The augmenting graph technique is also very potential in many other non-trivial combinatorial and graph-theoretical problems.

Appendices

Appendix 1: Proof of Lemma 2

Proof

(of Lemma 2) Let H = (B, W, E) be a minimal augmenting graph. If Δ(H) = 2, then H is a cycle or a chain. Since H is bipartite and |B| = |W| + 1, H cannot be a cycle. Now, assume that H is not a chain. We show that either (i) there exists some vertex a such that there is no vertex of distance 2k + l + 1 from a or (ii) H is an augmenting extended-chain or augmenting apple. Note that, every vertex of H is of degree at most m − 1, otherwise an induced K _1,m appears, a contradiction. Since H is connected, if we have (i), then

$$\displaystyle \begin{aligned}|V(H)| \leq \sum_{i=0}^{2k + l + 1}(m - 1)^{i} = \frac{1 - (m - 1)^{2k + l + 2}}{2 - m},\end{aligned}$$

i.e., H belongs to some finite set of augmenting graphs.

If a white vertex w ∈ W has two black neighbor b ₁, b ₂ of degree one, then {b ₁, a, b ₂} is an augmenting P ₃, a contradiction. Hence, we have the following observation.

Claim 1

Every white vertex of H has at most one black neighbor of degree one. In particular, if a white vertex w is of degree at least four, then there are at least three neighbors of w of degree two.

Claim 2

Either H contains a vertex, say a, of degree at least three and a has at least three neighbors of degree at least two or H is an augmenting apple.

Proof

Since H is neither a chain or a cycle, there exists at least one vertex of degree at least three.

By Corollary 2, every white vertex of H is of degree at least two, i.e. every white neighbor of a black vertex has another black neighbor. Hence, if H contains a black vertex of degree three, then this vertex is a desired vertex a.

Hence, we assume that (1) every black vertex of H is of degree at most two. If there exist two black vertices of degree one, then by (1), the path connecting these two black vertices is an augmenting chain, a contradiction. Hence, we assume that (2) there exists at most one black vertex of degree one.

By Claim 1, there exists no white vertex of degree four or we have a desired vertex a. Moreover, if there exist two white vertices of degree three, then either one of them has three neighbors of degree two, i.e. we have a desired vertex a, or we have two black vertex of degree one.

Now, if every white vertex of H is of degree two except one of degree three whose one black neighbor is of degree one, then H is an augmenting apple.

Let a be a vertex in the conclusion of the above claim. Denote by V _i the subset of vertices of H of distance i from a. Let a _p be the vertex of maximum distance from a and assume that p ≥ 2k + l + 1. Let P := (a ₀, a ₁, …, a _p), where a _i ∈ V _i, be a shortest path connecting a = a ₀ and a _p. Let V ₁ = {a ₁, b _1,1, b _1,2, …}, and b _i+1,j be a vertex of $N_{V_{i + 1}}(b_{i,j})$, if such one exists. By the assumption about a, b _2,1, and b _2,2 exist (note that they may coincide).

We show that $a_{i} \nsim b_{i + 1,1}$ and $a_{i + 1} \nsim b_{i,1}$ for i = 1, 2, …, 2k by induction. Note that it also implies that b _i,j ≠ a _i for every i, j.

If a ₂ ∼ b _1,1, then {b _1,1, a, a ₁, a ₂, a ₃, …, a _l+2} induces a banner_l, a contradiction.

If a ₁ ∼ b _2,1, then either {b _2,1, b _1,1, a, a ₁, a ₂, …, a _l+1} or {b _2,1, a ₁, a ₂, a ₃, a ₄, …, a _l+3} induces a banner_l depending on a ₃ ∼ b _2,1 or not, a contradiction.

Now, by induction hypothesis, consider 2 ≤ i ≤ k. If a _i ∼ b _i+1,1, then either {b _i+1,1, a _i, a _i+1, a _i+2, a _i+3, …, a _i+l+2} induces a banner_l or {b _i+1,1, b _i,1, …, b _1,1, a, a ₁, …, a _i, a _i+1, …, a _i+l} induces an apple$^{l}_{2i + 2}$ depending on a _i+2 ∼ b _i+1 or not, a contradiction. If a _i+1 ∼ b _i,1 for 2 ≤ i ≤ k, then {b _i,1, b _i−1,1, …, b _1,1, a, a ₁, a ₂, …, a _i+1, a _i+2, …, a _i+l+1} induces an apple$^{l}_{2i + 2}$, a contradiction.

Again, by induction hypothesis, consider k + 1 ≤ i ≤ 2k. If a _i ∼ b _i+1,1, then either {b _i+1,1, a _i, a _i+1, a _i+2, a _i+3, …, a _i+l+2} induces a banner_l or {a _i−1, a _i−2, …, a ₁, a, b _1,1, b _2,1, …, b _i+1,1, a _i, a _i+1, a _i+2, …, a _i+l} induces an S _2,2k,l depending on a _i+1 ∼ b _i,1 or not, a contradiction. If a _i+1 ∼ b _i,1, then {a _i, a _i−1, a _i−2, …, a ₁, a, b _1,1, b _2,1, …, b _i,1, a _i+1, a _i+2, …, a _i+l+1} induces an S _2,2k,l, a contradiction.

Hence, a _i has only one neighbor, say a _i+1, in V _i+1 and only one neighbor, say a _i−1, for i = 1, 2, …, 2k.

If b _i,1 ∼ b _i+1,2 for some 1 ≤ i ≤ 2k − 1 (if such two vertices exist), then {b _1,1, …, b _i,1, b _i+1,2, b _i,2, …, b _1,2, a, a ₁, …, a _l} induces an apple$^{l}_{2i + 2}$, a contradiction. Hence, b _i,j (if such vertex exists) has at most one neighbor in V _i+1 for 1 ≤ i ≤ 2k − 1. It also implies that b _i,j ≠ b _i,k for every 1 ≤ i ≤ 2k and j ≠ k if such vertices exist.

If V _2k contains at least two vertices, say a _2k and, without loss of generality, b _2k,1, then {b _2,2, b _1,2, a, b _1,1, b _2,1, …, b _2k,1, a ₁, a ₂, …, a _l} induces an S _2,2k,l, a contradiction.

To summarize, V _2k = {a _2k}, every vertex of V _i has only one neighbor in V _i−1, for every 1 ≤ i ≤ p.

Let T be the connected component of H − a ₁ containing a. Then T is a tree by the above arguments. We show that a is black. Indeed, for contradiction, suppose that a is white. Let a ₁ be the black vertex b of Corollary 1. Then there is a perfect matching between B ∩ T and W ∩ T. Let b be a leaf of T. Then by Corollary 2, b is black and hence μ(b) be the (only) white neighbor of b. It also implies that μ(b) has only one neighbor being a leaf. Indeed, if μ(b) has another black neighbor being a leaf b′, then there exists no μ(b′), a contradiction. Then by induction on T, a has only one black neighbor in T, a contradiction to a is of degree at least three. Hence, we have the following claim.

Claim 3

If a is a vertex of the conclusion of Claim 2, then a is black. Moreover, there exists a neighbor w of a such that the connected component of H − w containing a is a tree T, every vertex of T is of distance at most 2k − 2 to a, and every white vertex of T is of degree two.

Let a be the black vertex b of Corollary 1. Then there is a perfect matching between B ∩ T∖{a} and W ∩ T, i.e. |B ∩ T| = |W ∩ T| + 1. Claims 1 and 3 lead to the following observation.

Claim 4

Every white vertex w of H is either of degree two or three. Moreover, in the latter case, exactly one black neighbor of w is of degree one.

Let j be the largest number such that |V _j|≥ 2. Then 2 ≤ j ≤ 2k − 2. Moreover, j is even, since every leaf of T is black.

Note that every black vertex a _q such that 2k − j < q < p − 2k is of degree two, otherwise a _q becomes a vertex of the conclusion of Claim 2 and there exist at least two vertices of degree 2k from a _q, a contradiction to Claim 3.

Let T ₁ and T ₂ be the two connected component of H − a _2k−j+1 − a _p−2k−1 containing a _2k−j and a _p−2k, respectively. Then by Claim 3, T ₁ and T ₂ are trees such that the most distance between a vertex of T ₁ (respectively, T ₂) to a _2k−j (respectively, a _p−2k) is 2k − 2. Moreover |W ∩ (T ₁ + T ₂)| + 2 = |B ∩ (T ₁ + T ₂)|.

Now, every white vertex a _q, where 2k − j < q < p − 2k, is of degree two or three, and in the later case a black neighbor of a _q different from a _q−1 and a _q+1 is of degree one. Hence, every such white vertex is of degree two, otherwise we have a contradiction to |W| + 1 = |B|.

Thus, H is an augmenting (2k − 1, m)-extended-chain.

Appendix 2: Proof of Lemma 3

We go through the Proof by first obtaining some results related to the cases when the considered augmenting graph contains a K _1,m as an induced subgraph.

Lemma 8

Let G = (X, Y, E) be a bipartite graph such that there exists a vertex x ∈ X and N _Y(x) = Y . Assume that |X| = m + 1. Then at least one of the following statements is true.

• 1. H ₂ contains a banner ₂ or a domino.

• 2. We can linearly order X = (x, x ₁, x ₂, …, x _m) so that there exists a natural p, with 0 ≤ p ≤ m, such that (i) N _Y(x ₁) ⊇… ⊇ N _Y(x _p) and |N _Y(x _i)| = 1 for every i ≥ p + 1. Moreover, if p ≥ m − 1, then G is a bipartite-chain.

Proof

First, assume that Case 1 does not happen. We linearly order X by the construction method.

Assume that we already have chosen x ₁, …, x _p. Let U = X∖{x, x ₁, …, x _p}. Let x _p+1 ∈ U be a vertex such that |N _Y(x _p+1)| is largest among vertices in U. Suppose that |N _Y(x _p+1)|≥ 2 and there exists a vertex x _i ∈ U∖{x _p+1} such that x _i ∼ y _i and $x_{p + 1} \nsim y_{i}$ for some y _i ∈ Y . By the choice of x _p+1, $x_{i} \nsim y_{j}$ for some y _j ∈ N _Y(x _p+1). Then {x, y _k, y _i, y _j, x _p+1, x _j} induces a domino or a banner₂ for some y _k ∈ N _Y(x _p+1)∖{y _j} depending on x _i ∼ y _k or not and x is a vertex of degree three in both cases, a contradiction.

If p ≥ m − 1, then N _Y(x) ⊇ N _Y(x _i) ⊇ N _Y(x _j) for every 1 ≤ i < j ≤ m. We show that for y _i, y _j ∈ Y , either N _X(y _i) ⊆ N _X(y _j) or N _X(y _j) ⊆ N _X(y _i). Indeed, suppose that y _i ∼ x _i and y _j ∼ x _j for some x _i ∈ X∖N(y _j) and x _j ∈ X∖N(y _i). Then N _Y(x _i)⊈N _Y(x _j) and N _Y(x _j)⊈N _Y(x _i), a contradiction.

Lemma 9

If an (S _2,2,5 ,banner ₂ ,domino)-free minimal augmenting graph H contains no black vertex of degree more than k (k ≥ 2), then the degree of each white vertex is at most k ² + k + 2.

Proof

Suppose that H contains a white vertex w of degree more than k ² + k + 2. Denote by V _j the set of vertices of H at distance j from w. Hence, |V ₁|≥ k ² + k + 3.

Claim 5

|V ₂|≥ k ² + k + 1, V ₂ contains at least k ² + 1 vertices having only one neighbor in V ₁, i.e. having a neighbor in V ₃, and |V ₃|≥ k + 1.

Proof

Suppose that V ₃ = ∅. Then by Lemma 1, |V ₂| = |V ₁|− 2 ≥ k ² + k + 1. Let p be the p in 2. of Lemma 8. Note that p ≤ k, otherwise there exists a black vertex in V ₁ having at least k neighbors in H, a contradiction. Hence, by Lemma 8, there exists a white vertex in V ₂ having only one neighbor in V ₁, i.e. only one black neighbor. This contradiction (with Corollary 2) implies that V ₃ ≠ ∅.

Then |V ₂|≥ k ² + k + 1, otherwise H[{b}∪ V ₁ ∪ V ₂] is an augmenting graph, a contradiction. Again, by Lemma 8 and condition that there is no black vertex of degree larger than k, V ₂ contains at least k ² + 1 vertices having only one neighbor in V ₁, i.e. having a neighbor in V ₃ by Corollary 2. Since every black vertices of V ₃ has at most k neighbors in V ₂, |V ₃|≥ k + 1. □

Claim 6

V ₄ = ∅, i.e. |V ₃| + |V ₁| = |V ₂| + 2.

Proof

Suppose that V ₄ contains a (white) vertex x and let y be its neighbor in V ₃. Assume that y ∼ w ₁ ∈ V ₂ and w ₁ ∼ b ₁ ∈ V ₁.

If w ₁ ∼ b ₂ for some b ₂ ∈ V ₁∖{b ₁}, then {b ₁, w, b ₂, w ₁, y, x} induces a banner₂, a contradiction. Hence, $N_{V_{1}}(w_{1}) = \{b_{1}\}$.

By Corollary 2, x has at least one more black neighbor, named z (z ∈ V ₃ or z ∈ V ₅). Now, let b ₁ be the b in Corollary 1. We have |μ(V ₁∖{b ₁, μ(w)})|≥ k ² + k + 1. Since d(y), d(z) ≤ k, V ₁ contains at least two vertices, named b ₂, b ₃ whose the neighbors, say w ₂ = μ(b ₂), w ₃ = μ(b ₃) ∈ V ₂, respectively, adjacent to neither y nor z.

If w ₂ ∼ b ₁, then {w, w ₁, w ₂, b ₁, b ₂, y} induces a domino or a banner₂, depending on y ∼ w ₂ or not, a contradiction. If w ₂ ∼ b ₄ for some b ₄ ∈ V ₁∖{b ₁, b ₂}, then {b ₂, w ₂, b ₄, w, b ₁, w ₁} induces a banner₂, a contradiction. Hence, w ₁, w ₂, and w ₃, each has only one neighbor in V ₁. Moreover, $z \nsim w_{1}$, otherwise, {y, x, z, w ₁, b ₁, w} induces a banner₂, a contradiction. Now, {w ₃, b ₃, w, w ₂, b ₂, b ₁, w ₁, y, z, x} induces an S _2,2,5, a contradiction. Therefore, V ₄ is empty and |V ₃| + |V ₁| = |V ₂| + 2 by Lemma 1. □

Let b ∈ V ₃ be the vertex b in Corollary 1. Since μ(w) has at most k − 1 neighbors in μ(V ₃∖{b}), there exists a vertex d ₁ ∈ V ₃ such that $\mu (d_{1}) \nsim \mu (w)$.

Claim 7

μ(d ₁) has a neighbor a ₁ in V ₁ such that μ(a ₁) has no neighbor in V ₁ other than a ₁.

Proof

Let a ₁ be a neighbor of μ(d ₁) in V ₁, i.e. μ(a ₁) ≠ w. If μ(a ₁) has no neighbor in V ₁ other than a ₁, then we have the statement of the claim. Now, let a ₂ be a neighbor of μ(a ₁) in V ₁. Then μ(d ₁) ∼ a ₂, otherwise {w, a ₂, μ(a ₁), a ₁, μ(d ₁), d ₁} induces a domino or a banner₂ depending on d ₁ ∼ μ(a ₁) or not, a contradiction. It implies that μ(a ₂) ≠ w. We continue considering μ(a ₂). Since V ₁ is finite, this process must stop, i.e. we have the claim. □

Note that $d_{1} \nsim \mu (a_{1})$, otherwise {μ(a ₁), d ₁, μ(d ₁), a ₁, w, μ(w)} induces a domino or a banner₂ depending on μ(w) ∼ μ(a ₁) or not, a contradiction. Since μ(a ₁) has no neighbor in V ₁ other than a ₁, by Corollary 2, μ(a ₁) has a neighbor d ₂ ∈ V ₃.

Since $|N_{V_{2}}(\{d_{1},d_{2}\})| \leq 2k$, there is a vertex a ∈ V ₁∖{μ(w)} such that μ(a) is not adjacent to d ₁, d ₂. Then $\mu (a) \nsim a_{1}$, otherwise {w, a, μ(a), a ₁, μ(a ₁), d ₂} induces a banner₂, a contradiction. If μ(a) ∼ a ₂ for some a ₂ ∈ V ₁, then {a, μ(a), a ₂, w, a ₁, μ(a ₁)} induces a banner₂, a contradiction. Hence, μ(a) has only one neighbor in V ₁ and has a neighbor, named d ₃ ∈ V ₃, by Corollary 2.

Then $\mu (d_{1}) \nsim a$, otherwise {w, a ₁, a, μ(d ₁), d ₃, μ(a)} induces a domino or a banner₂ depending on d ₃ ∼ μ(d ₁) or not, a contradiction. Moreover $\mu (d_{3}) \nsim a$, otherwise {w, a ₁, a, μ(a), d ₃, μ(d ₃)} induces a domino or a banner₂ depending on a ₁ ∼ μ(d ₃) or not, a contradiction.

We show that $d_{1} \nsim \mu (d_{3})$. Indeed, if d ₁ ∼ μ(d ₃), then $\mu (d_{1}) \nsim d_{3}$, otherwise {μ(d ₃), d ₁, μ(d ₁), d ₃, μ(a), a} induces a banner₂, a contradiction. If μ(d ₁) ∼ a ₂ for some a ₂ ∈ V ₁∖{a ₁}, then {w, a ₁, μ(d ₁), a ₂, d ₁, μ(d ₃)} induces a domino or a banner₂ depending μ(d ₃) ∼ a ₂ or not, a contradiction. If μ(d ₃) has two neighbors a ₂, a ₃ ∈ V ₁∖{a ₁}, then {a ₂, w, a ₃, μ(d ₃), d ₁, μ(d ₁)} induces a banner₂, a contradiction. Hence, μ(d ₁) has only one neighbor in V ₁ and μ(d ₃) has at most one neighbor in V ₁ different from a ₁. Thus, because $|N_{V_{2}}(d_{1},d_{2})| \leq 2k$, there exist two vertices b ₁, b ₂ ∈ V ₁∖{μ(w)} such that μ(b ₁), μ(b ₂) each has only one neighbor in V ₁ and is not adjacent to d ₁, d ₃. Now, {μ(b ₁), b ₁, w, b ₂, μ(b ₂), a ₁, μ(d ₁), d ₁, μ(d ₃), d ₃} induces an S _2,2,5, a contradiction.

Similarly, d ₃ is not adjacent to μ(d ₁), μ(a ₁), and $\mu (d_{3}) \nsim d_{2}$. Moreover $\mu (d_{1}) \nsim d_{2}$, otherwise {w ₁, d ₂, μ(d ₁), a ₁, w, μ(w)} induces a banner₂, a contradiction. Similarly, $\mu (a_{1}) \nsim d_{1}$.

Now, {d ₂, μ(a ₁), a ₁, μ(d ₁), d ₁, w, a, μ(a), d ₃, μ(d ₃)} induces an S _2,2,5, a contradiction. □

Proof (of Lemma 3)

We proof by contradiction. Let b ∈ B such that |N _W(b)| is largest. If every black vertex is of degree one, then H is an augmenting P ₃. If N _W(b) = W, then we have 4. By Lemma 9, if every black vertex of H is of degree bounded by a given number k, then every white vertex of H is of degree bounded by k ² + k + 2, i.e. H is K _1,m-free for m = k ² + k + 3. In this case, by Lemma 2, we have 1. or 2.

Now, we assume that 10 ≤|N _W(b)|≤|W|− 1. Let b be the vertex b of Corollary 1. Let A = N(b) = {w ₁, w ₂, …, w _k} (k ≥ 10), C = W∖A, i.e. C ≠ ∅. Let b _i = μ(w _i). Let C ₁ denote the set of vertices in C having at least one neighbor in μ(A) and C ₀ = C∖C ₁. By the connectivity of H, one can choose μ(A) in order that C ₁ ≠ ∅. We have the following observations.

Claim 8

H[A ∪ μ(A)] is an induced sub-matching of M.

Proof

We show that $b_{i} \nsim w_{j}$ for every pair i, j such that i ≠ j, 1 ≤ i, j ≤ k. Let z ∈ C ₁ and without loss of generality, assume that z ∼ b ₁ ∈ μ(A).

By the choice of b, b ₁ is not adjacent to all w _i’s, without loss of generality, assume that $b_{1} \nsim w_{2}$.

Now, $b_{2} \nsim w_{1}$, otherwise {b, b ₁, b ₂, w ₁, w ₂, z} induces a domino or a banner₂ depending on b ₂ ∼ z or not, a contradiction.

Moreover, $b_{2} \nsim w_{i}$ for every i > 2, otherwise {b, b ₁, b ₂, w ₁, w ₂, w _i} induces a domino or a banner₂ depending on b ₁ ∼ w _i or not, a contradiction.

Now, $b_{1} \nsim w_{i}$, for every i > 2, otherwise {w ₁, b ₁, w _i, b, w ₂, b ₂} induces a banner₂, a contradiction.

Hence, $b_{i} \nsim w_{1}$ for i > 2, otherwise {b, w _i, b _i, w ₁, b ₁, z} induces a domino or a banner₂, depending on z ∼ b _i or not, a contradiction.

Thus, $b_{i} \nsim w_{2}$ for i > 2, otherwise {w ₂, b _i, w _i, b, w ₁, b ₁} induces a banner₂, a contradiction.

Moreover $b_{i} \nsim w_{j}$, for any j ≠ i and i, j > 2, otherwise {w _j, b _i, w _i, b, w ₁, b ₁} induces a banner₂, a contradiction.

Claim 9

There exists no vertex pair z ₁, z ₂ ∈ C ₁ sharing two neighbors in μ(A).

Proof

Suppose that there exists a vertex pair z ₁, z ₂ ∈ C ₁ sharing two neighbors in μ(A), without loss of generality, assume that they are b ₁, b ₂. Then {z ₁, b ₂, z ₂, b ₁, w ₁, b} induces a banner₂, a contradiction. □

Claim 10

Given z ∈ C ₁, z ∼ b _j for some b _j ∈ μ(A), a black neighbor c of z different from b _j, a black neighbor μ(t) of z for some t ∈ C, and another white neighbor y ∈ C of μ(t) different from z, the following statements are true:

• 1. $c \nsim w_{j}$;

• 2. $y \nsim b_{j}$ and $\mu (y) \nsim z$; and

• 3. if μ(t) ∼ w _i for some i ≠ j, then y, z are not adjacent to b _i and $\mu (y) \nsim w_{i}$;

• 4. in particular, μ(y) and μ(t) cannot share a same neighbor in A.

Proof

Suppose that c ∼ w _j. Then c ∼ w _i for every i ≠ j, otherwise {b _j, z, c, w _j, b, w _i} induces a banner₂, a contradiction. But now, we have a contradiction to the choice of b.

Now, $y \nsim b_{j}$, otherwise {z, μ(t), y, b _j, w _j, b} induces a banner₂, a contradiction. Moreover, $\mu (y) \nsim z$, otherwise {w _j, b _j, z, μ(t), y, μ(y)} induces a domino or a banner₂ depending on μ(y) ∼ w _j or not, a contradiction.

Assume that μ(t) ∼ w _i for some i ≠ j. Then $z \nsim b_{i}$, otherwise {μ(t), w _i, b _i, z, b _j, w _j} induces a banner₂, a contradiction. Hence, $y \nsim b_{i}$, otherwise {b _i, y, μ(t), w _i, b, w _j} induces a banner₂, a contradiction. Now, $\mu (y) \nsim w_{i}$, otherwise {w _i, μ(y), y, μ(t), z, b _j} induces a banner₂, a contradiction. □

Claim 11

Every black vertex different from b has at most one neighbor in A.

Proof

Clearly, every black vertex of μ(A) has only one neighbor in A by Claim 8. Now, suppose that there exists some black vertex y ∈ B∖({b}∪ μ(A)) having two neighbors, without loss of generality, assume that they are w ₁, w ₂ ∈ A. Then y is adjacent to every vertex w _i ∈ A∖{w ₁, w ₂}, otherwise {w ₁, y, w ₂, b, w _i, b _i} induces a banner₂, contradiction. Now, y is adjacent to every vertex of A and μ(y), a contradiction to the choice of b. □

Claim 12

There exists no vertex b _j ∈ μ(A) having two neighbors z ₁, z ₂ ∈ C ₁ sharing another black neighbor, named c ≠ b _j.

Proof

Indeed, otherwise, by Claim 10, $c \nsim w_{j}$, then {z ₁, c, z ₂, b _j, w _j, b} induces a banner₂, a contradiction. □

Claim 13

Given a vertex b _j ∈ μ(A), let C(b _j) be the set of vertices of C ₁ adjacent to b _j. Then H[C(b _j) ∪ μ(C(b _j))] is an induced sub-matching of M.

Proof

For contradiction, without loss of generality, suppose that z ₁, z ₂ ∈ C are two neighbors of b _j and z ₁ ∼ μ(z ₂). By Claim 10, $\mu (z_{2}) \nsim w_{j}$. Hence, {z ₁, μ(z ₂), z ₂, b _j, w _j, b} induces a banner₂, a contradiction. □

Claim 14

If H contains a vertex y ∈ C ₁ adjacent to at least k − 3 vertices of μ(A), then either H is of the form tree⁵ or tree⁶ or H contains a redundant set U of size at most 32, such that H − U is of the form either tree¹, tree⁴, tree⁵, or tree⁶.

Proof

Let D ₁ be the subset of vertices of C ₁ sharing some neighbor in μ(A) with y, A ₁ be the vertex subset of A such that μ(A ₁) = N _μ(A)(y), A ₂ = A∖A ₁, E ₁ be the vertices subset of C ₁ adjacent to some vertex in μ(A ₂). Without loss of generality, assume that w ₁, w ₂, …, w _k−3 ∈ A ₁. We have the following observations.

• (1) y has no neighbor in μ(D ₁) and μ(y) has no neighbor in A ₁ ∪ D ₁. Indeed, by Claim 10, μ(y) has no neighbor in A ₁. If for some z ∈ D ₁, without loss of generality, assume that z ∼ b ₁, y ∼ μ(z), then $y \nsim b_{1}$, by Claim 10, a contradiction. Moreover, since $\mu (y) \nsim w_{1}$, $\mu (y) \nsim z$, otherwise {z, μ(y), y, b ₁, w ₁, b} induces a banner₂, a contradiction.

• (2) By Claim 9, every vertex of D ₁ has exactly one neighbor in μ(A ₁). In particular, every vertex of C ₁∖{y} has at most four neighbors in μ(A). Moreover, there exists only one vertex y ∈ C ₁ adjacent to at least k − 3 vertices in μ(A).

• (3) Any two vertices of D ₁ have different neighbors in μ(A ₁). Indeed, without loss of generality, suppose that z ₁, z ₂ ∈ D ₁ both are adjacent to b ₁. By Claim 11, and since |A ₁| = k − 3 ≥ 7, there exist w _i, w _j ∈ A ₁ different from w ₁ and not adjacent to μ(z ₁), μ(z ₂). By (2) and Claim 13, {μ(z ₁), z ₁, b ₁, z ₂, μ(z ₂), y, b _i, w _i, b, w _j} induces an S _2,2,5, a contradiction.

• (4) Similar to Claim 13, let C(y) be the subset of vertices of C ₀ adjacent to μ(y). Then H[C(y) ∪ μ(C(y))] is an induced sub-matching of M.

• (5) Similarly to (3) (using (4)), there is at most one vertex of C ₀ adjacent to μ(y).

• (6) H[(C ₁∖{y}) ∪ μ(C ₁∖{y})] is an induced sub-matching of M. Indeed, suppose that for a couple of vertices z ₁, z ₂ ∈ C ₁∖{y}, z ₁ ∼ μ(z ₂). Without loss of generality, assume that z ₁, z ₂ are adjacent to $b_{i_{1}}, b_{i_{2}} \in \mu (A)$, respectively. Then by Claim 10, $\mu (z_{2}) \nsim w_{i_{2}}$. Hence, $z_{1} \nsim b_{i_{2}}$, otherwise $\{z_{2},\mu (z_{2}),z_{1},b_{i_{2}},w_{i_{2}},b\}$ induces a banner₂, a contradiction. By (2) and Claim 11, there exists a pair of vertices b _i, b _j ∈ μ(A) not adjacent to z ₁, z ₂ such that w _i and w _j are not adjacent to μ(z ₁), μ(z ₂). Now, $\{b_{i},w_{i},b,w_{j},b_{j},w_{i_{2}},b_{i_{2}},z_{2},\mu (z_{2}),z_{1}\}$ induces an S _2,2,5, a contradiction.

• (7) There exists no vertex t ∈ C∖{y} having a neighbor in μ(C ₁∖{y, μ(t)}). Indeed, if t ∈ C is adjacent to μ(z) for some z ∈ C ₁∖{y, t}, then for the vertex b _j adjacent to z, $t \nsim b_{j}$ by Claim 10. By (2) and Claim 13, there exists a pair of vertices w _i, w _l non-adjacent to μ(z) such that b _i, b _l non-adjacent z, t. Now, {b _i, w _i, b, w _l, b _l, w _j, b _j, z, μ(z), t} induces an S _2,2,5, a contradiction.

• (8) Similarly, there exists no vertex t ∈ C ₁∖{y} having a neighbor in μ(C∖{y, μ(t)}).

• (9) If C ₀ = {z}, then z ∼ μ(y). If |C ₀|≥ 2, then there exists a vertex x ∈ C ₀ such that x ∼ μ(z). For every such vertex x, the following statements are true: y ∼ μ(x), $\mu (x) \nsim z$, and $\mu (x) \nsim w_{i}$ for w _i ∈ A ₁. Moreover, if |C ₀|≥ 2, then A ₂ = ∅, i.e. y is adjacent to every vertex of μ(A).

  Indeed, if C ₀ ≠ ∅, then by (7) and the minimality of H, there exists a vertex z ∈ C ₀ such that z ∼ μ(y), otherwise |C ₀| = |N _H(C ₀)|(= |μ(C ₀)|), a contradiction. Moreover, no other vertex of C ₀ is adjacent to μ(y) by (5). Hence, if |C ₀|≥ 2, then, again by (7) and the minimality of H, there exists a vertex x ∈ C ₀ such that x ∼ μ(z).

  Let x ∈ C ₀ such that x ∼ μ(z). Since $\mu (z) \nsim y$ by Claim 10, $x \nsim \mu (y)$, otherwise {z, μ(z), x, μ(y), y, b ₁} induces a banner₂, a contradiction. Thus, $\mu (x) \nsim z$, otherwise {y, μ(y), z, μ(z), x, μ(x)} induces a domino or a banner₂, depending on μ(x) ∼ y or not, a contradiction. Now, if $y \nsim \mu (x)$, then by Claim 11, there exists a pair of vertices b _i, b _j ∈ μ(A ₁) such that w _i and w _j are not adjacent to μ(x), μ(z) and {w _i, b _i, y, b _j, w _j, μ(y), z, μ(z), x, μ(x)} induces an S _2,2,5, a contradiction. Then $\mu (x) \nsim w_{i}$ for any w _i ∈ A ₁, otherwise {y, b _i, w _i, μ(x), x, μ(t)} induces a banner₂, a contradiction.

  Assume that |C ₀|≥ 2, we show that A ₂ = ∅. Indeed, without loss of generality, assume that $y \nsim b_{k}$. Let x ∈ C ₀ be a vertex such that x ∼ μ(z). Then μ(y) or μ(z) is not adjacent to w _k, otherwise since $z \nsim w_{k}$ by Claim 10, {z, μ(z), w _k, μ(y), y, b ₁} induces a banner₂, a contradiction. Similarly, μ(x) or μ(z) is not adjacent to w _k. Now, $\mu (y) \nsim w_{k}$, otherwise since there exists a pair of vertices w _i, w _j ∈ A ₁ not adjacent to μ(y), μ(z) by Claim 11, {b _i, w _i, b, w _j, b _j, w _k, μ(y), z, μ(z), x} induces an S _2,2,5, a contradiction. By similar reasons, $\mu (x) \nsim w_{k}$. Now, by Claim 11, there exists a vertex w _i ∈ A ₁ not adjacent to μ(x) and {z, μ(y), y, μ(x), x, b _i, w _i, b, w _k, b _k} induces an S _2,2,5, a contradiction.

• (10) If |D ₁|≥ 2, then no vertex of μ(D ₁) has a neighbor in A. Indeed, by (3), without loss of generality, let z ₁, z ₂ ∈ D ₁ be adjacent to b ₁, b ₂, respectively. To the contrary, suppose that μ(z ₁) has a neighbor w _i ∈ A. By Claim 10, w _i ≠ w ₁. If w _i = w ₂, then by (1), (6), and Claims 10, 11, {z ₂, b ₂, w ₂, b, w _j, μ(z ₁), z ₁, b ₁, y, μ(y)} induces an S _2,2,5 for some vertex w _j ≠ w ₁, w ₂ such that $w_{j} \nsim \mu (z_{1})$, a contradiction. If w _i ≠ w ₁, w ₂, then by (1) and (6), {w ₂, b, w _i, μ(z ₂), z ₂, μ(z ₁), z ₁, b ₁, y, μ(y)} induces an S _2,2,5 in the case that μ(z ₂) ∼ w _i, or {μ(z ₂), z ₂, b ₂, y, μ(y), w ₂, b, w _i, μ(z ₁), z ₁} induces an S _2,2,5 in the case that $\mu (z_{2}) \nsim w_{i}$, a contradiction.

• (11) If there exist two vertices z ₁, z ₂ ∈ C ₁ sharing a neighbor in μ(A ₂), then either H is of the form tree⁵ or there is a redundant set U containing at most four vertices such that H − U is of the form tree² or tree⁵.

First, since A ₂ ≠ ∅, |C ₀|≤ 1 by (9). Without loss of generality, assume that z ₁, z ₂ share a neighbor b _k ∈ μ(A ₂).

If z ₂ has another neighbor, say b _l ∈ μ(A), then since by (2), there exists a pair of vertices b _i, b _j ∈ μ(A ₁) not adjacent to z ₁, z ₂, one has that {b _i, w _i, b, w _j, b _j, w _l, b _l, z ₂, b _k, z ₁} induces an S _2,2,5, a contradiction. Thus, b _k is the only one neighbor in μ(A) for any vertex z ∈ C ₁ adjacent to b _k.

Note that, for any such z, $\mu (z) \nsim w_{k}$ by Claim 10. Moreover, $\mu (z) \nsim w_{j} \in A$ for w _j ≠ w _k, otherwise {b _i, w _i, b, b _l, w _l, w _j, μ(z), z, b _k, z′} induces an S _2,2,5 for z′ be another neighbor of b _k in C ₁ different from z; by Claim 11 and (2), b _i, b _l not adjacent to z, z′; and w _i, w _l not adjacent to μ(z), a contradiction.

Now, y is adjacent to at least one vertex among μ(z ₁), μ(z ₂), otherwise by (6), {μ(z ₁), z ₁, b _k, z ₂, μ(z ₂), w _k, b, w ₁, b ₁, y} induces an S _2,2,5, a contradiction. Without loss of generality, assume that y ∼ μ(z ₁). Then y ∼ μ(z ₂), otherwise by (6), {w ₁, b ₁, y, b ₂, w ₂, μ(z ₁), z ₁, b _k, z ₂, μ(z ₂)} induces an S _2,2,5, a contradiction. Hence, y is adjacent to every vertex z ∈ C ₁ adjacent to b _k.

That also implies that y has no other non-neighbor than b _k in μ(A). Indeed, without loss of generality, suppose that $y \nsim b_{k - 1}$. Then {z ₁, μ(z ₁), y, μ(z ₂), z ₂, b ₁, w ₁, b, w _k−1, b _k−1} induces an S _2,2,5, a contradiction.

Moreover, $\mu (y) \nsim z$ for every vertex z ∈ C ₁ adjacent to b _k, otherwise {μ(y), z, μ(z), y, b ₁, w ₁} induces a banner₂, a contradiction.

Besides, D ₁ = ∅. Indeed, without loss of generality, suppose that there exists some vertex t ∈ D ₁ such that t ∼ b ₁. Then $t \nsim b_{k}$, otherwise an S _2,2,5 arises. Moreover, $t \nsim \mu (z)$ for any z ∈ C ₁ adjacent to b _k, otherwise {t, μ(z), y, b ₁, w ₁, b} induces a banner₂, a contradiction. Now, by (6), {μ(z ₁), z ₁, b _k, z ₂, μ(z ₂), w _k, b, w ₁, b ₁, t} induces an S _2,2,5, a contradiction.

We consider the two following cases.

Case 1. C ₀ = ∅. Then

$$\displaystyle \begin{aligned}U := \{y,\mu(y)\}\end{aligned}$$

is a redundant set of size two such that H − U is of the form tree² in the case that $\mu (y) \nsim w_{k}$, or H is of the form tree⁵ in the case that μ(y) ∼ w _k.

Case 2. C ₀ = {x} and x ∼ μ(y) by (9). Then $\mu (x) \nsim w_{k}$, otherwise {x, μ(x), w _k, μ(y), y, b ₁} induces a banner₂ or {w ₁, b ₁, y, b ₂, w ₂, μ(y), x, μ(x), w _k, b _k} induces an S _2,2,5 depending on μ(y) ∼ w _k or not, a contradiction. Thus, $\mu (x) \nsim z$ for any z ∈ C ₁ adjacent to b _k, otherwise, by Claim 11, there exists a pair of vertices w _i, w _j ≠ w _k not adjacent to μ(x) and hence, {b _i, w _i, b, w _j, b _j, w _k, b _k, z, μ(x), x} induces an S _2,2,5, a contradiction. Moreover, $\mu (x) \nsim w_{i}$ for any w _i ∈ A ₁, otherwise {z ₁, μ(z ₁), y, μ(z ₂), z ₂, μ(y), x, μ(x), w _i, b} induces an S _2,2,5, a contradiction. Now,

$$\displaystyle \begin{aligned}U := \{y,\mu(y),x,\mu(x)\}\end{aligned}$$

is a redundant set of size at most four such that H − U is of the form tree², in the case that $\mu (y) \nsim w_{k}$, or

$$\displaystyle \begin{aligned}U := \{x,\mu(x)\}\end{aligned}$$

is a redundant set of size at most two such that H − U is of the form tree⁵, in the case that μ(y) ∼ w _k.

From now on, we assume the following statement.

• (11’) Two different vertices in C ₁∖{y} share no common neighbor in μ(A). This also implies that |E ₁|≤ 3.

• (12) If D ₁ = ∅, then there exists a redundant set U of size at most 24 such that H − U is of the form tree¹. Indeed, if in addition, C ₀ = ∅, then by Claim 11,

  $$\displaystyle \begin{aligned}U := \{y,\mu(y)\} \cup A_{2} \cup \mu(A_{2}) \cup E_{1} \cup \mu(E_{1}) \cup N_{A}(\mu(E_{1})) \cup \mu(N_{A}(\mu(E_{1})))\end{aligned}$$

  is a redundant set of size at most 20 such that H − U is of the form tree¹. Now, we consider the two following cases.

Case 1. C ₀ = {z}. Then by (9) and Claim 11,

$$\displaystyle \begin{aligned} \begin{array}{rcl} U &\displaystyle := &\displaystyle \{y,\mu(y),z,\mu(z)\} \cup A_{2} \cup \mu(A_{2}) \cup E_{1} \cup \mu(E_{1}) \cup \\ &\displaystyle &\displaystyle \cup N_{A}(\mu(E_{1}) \cup \{\mu(z)\}) \cup \mu(N_{A}(\mu(E_{1}) \cup \{\mu(z)\})) \end{array} \end{aligned} $$

is a redundant set of size at most 24 such that H − U is of the form tree¹.

Case 2. |C ₀|≥ 2. Then y is adjacent to every vertex of μ(A) by (2). Let z be the (only) vertex of C ₀ adjacent to μ(y). Denote by $C^{\prime }_{0}$ the set of vertices of C ₀∖{z} adjacent to μ(z) and let $C^{\prime \prime }_{0} := C_{0} \backslash (C^{\prime }_{0} \cup \{z\})$. Then $C^{\prime }_{0} \neq \emptyset$, otherwise |C ₀∖{z}| = |N _H(C ₀∖{z})|, a contradiction to the minimality of H. Moreover, for every $x \in C^{\prime }_{0}$, μ(x) ∼ y, μ(x) is not adjacent to any vertex of A ₁, and $x \nsim \mu (y)$ by (9).

2.1. $C^{\prime \prime }_{0} = \emptyset$. Then H is of the form tree⁵ or tree⁶ depending on μ(z) has a neighbor in A or not.

2.2. $C^{\prime \prime }_{0} \neq \emptyset$. Then it must contain a vertex t ∼ μ(x) for some $x \in C^{\prime }_{0}$, otherwise $|N(C^{\prime \prime }_{0})| = |C^{\prime \prime }_{0}|$, a contradiction to the minimality of H. Now, $\mu (t) \nsim x$, otherwise {z, μ(z), x, μ(x), t, μ(t)} induces a domino or a banner₂ depending on μ(t) ∼ z or not, a contradiction. Thus, $\mu (t) \nsim y$, otherwise {y, μ(t), t, μ(x), x, μ(z)} induces a banner₂, a contradiction. Now, by Claim 11, there exists a pair of vertices w _i, w _j is not adjacent to μ(x), μ(t), μ(z) and hence, {μ(t), t, μ(x), x, μ(z), y, b _i, w _i, b, w _j} induces an S _2,2,5, a contradiction.

From now on, we assume the following statement.

• (12’) D ₁ ≠ ∅.

• (13) If |C ₀|≥ 2, then H contains a redundant set U of size at two such that H − U is of the form tree⁵.

By (9), y is adjacent to every vertex of μ(A). Let z be the (only) vertex of C ₀ adjacent to μ(y) and x ∈ C ₀ be adjacent to μ(z). Also by (9), for every such vertex x, μ(x) ∼ y, $\mu (x) \nsim z$. Moreover, by Claim 10, z has no neighbor in μ(A).

Since D ₁ ≠ ∅, without loss of generality, assume that there exists a vertex z ₁ ∈ D ₁ adjacent to b ₁. Now, μ(z) ∼ w ₁, otherwise {μ(z ₁), z ₁, b ₁, w ₁, b, y, μ(y), z, μ(z), x} induces an S _2,2,5, a contradiction. Moreover, by (3) and Claim 11, D ₁ = {z ₁}. We consider the two following cases.

Case 1. z has a neighbor μ(t) ∈ μ(C ₀) for some t ∈ C ₀ different from z. Then by (7), (8), and Claim 10, μ(t) ∼ w ₁, otherwise {μ(z ₁), z ₁, b ₁, w ₁, b, y, μ(y), z, μ(t), t} induces an S _2,2,5, a contradiction. But now, {μ(z), w ₁, μ(t), z, μ(y), y} induces a banner₂, a contradiction.

Case 2. z has no neighbor in μ(C ₀) other than μ(z). Let x be a vertex in C ₀ adjacent to μ(z) and $C^{\prime }_{0}$ be the set of vertices of C ₀ different from z and not adjacent to μ(z). If $C^{\prime }_{0} \neq \emptyset$, then by (7) and (8), there exists a vertex $t \in C^{\prime }_{0}$ adjacent to μ(x), otherwise $|C^{\prime }_{0}| = |N_{H}(C^{\prime }_{0})|$, a contradiction to the minimality of H. Now, $t \nsim \mu (z)$, otherwise {μ(y), z, μ(z), x, μ(x), t} induces a domino or a banner₂ depending on t ∼ μ(y) or not, a contradiction. Now, by Claim 11, there exists a pair of vertices w _i, w _j different from w ₁ not adjacent to μ(x) and hence, {b _i, w _i, b, w _j, b _j, w ₁, μ(z), x, μ(x), t} induces an S _2,2,5, a contradiction.

From above considerations, every vertex x ∈ C ₀ different from z is adjacent to μ(z) and μ(x) is adjacent to y. Now,

$$\displaystyle \begin{aligned}U := \{z_{1},\mu(z_{1})\}\end{aligned}$$

is a redundant set of size two, such that H − U is of the form tree⁵.

From now on, we assume the following statement.

• (13’) |C ₀|≤ 1.

• (14) If |D ₁|≥ 2, then by (10) and (13’),

  $$\displaystyle \begin{aligned} \begin{array}{rcl} U &\displaystyle := &\displaystyle \{y,\mu(y)\} \cup C_{0} \cup \mu(C_{0}) \cup E_{1} \cup \mu(E_{1}) \cup \\ &\displaystyle &\displaystyle \cup N_{A}(\mu(E_{1}) \cup \mu(C_{0})) \cup \mu(N_{A}(\mu(E_{1}) \cup \mu(C_{0}))) \cup \\ &\displaystyle &\displaystyle \cup N_{D_{1}}(\mu(N_{A}(\mu(E_{1}) \cup \mu(C_{0})))) \cup \\ &\displaystyle &\displaystyle \cup \mu(N_{D_{1}}(\mu(N_{A}(\mu(E_{1}) \cup \mu(C_{0}))))) \end{array} \end{aligned} $$

  is a redundant set of size at most 26 such that H − U is of the form tree⁴.

• (15) If |D ₁| = 1, then

  $$\displaystyle \begin{aligned} \begin{array}{rcl} U &\displaystyle := &\displaystyle \{y,\mu(y)\} \cup C_{0} \cup \mu(C_{0}) \cup D_{1} \cup \mu(D_{1}) \cup E_{1} \cup \mu(E_{1}) \cup \\ &\displaystyle &\displaystyle \cup N_{A}(\mu(D_{1}) \cup \mu(E_{1}) \cup \mu(C_{0})) \cup \mu(N_{A}(\mu(D_{1}) \cup \mu(E_{1}) \cup \mu(C_{0}))) \cup \\ &\displaystyle &\displaystyle \cup N_{D_{1}}(\mu(N_{A}(\mu(D_{1}) \cup \mu(E_{1}) \cup \mu(C_{0})))) \\ &\displaystyle &\displaystyle \cup \mu(N_{D_{1}}(\mu(N_{A}(\mu(D_{1}) \cup \mu(E_{1}) \cup \mu(C_{0}))))) \end{array} \end{aligned} $$

  is a redundant set of size at most 32 such that H − U is of the form tree¹.

All the above observations ((1)–(15)) finish the proof of the claim. □

From now on, assume that every vertex of C ₁ has at least four non-neighbors in μ(A).

Claim 15

C ₀ = ∅, i.e. C = C ₁.

Proof

Suppose that C ₀ ≠ ∅. Then there exists some vertex z ∈ C ₁, without loss of generality, assume that z ∼ b ₁, and y ∈ C ₀ such that y ∼ μ(z), otherwise |C ₀| = |N _H(C ₀)|, a contradiction to the minimality of H. Thus, {b _i, w _i, b, w _j, b _j, w ₁, b ₁, z, μ(z), y} induces an S _2,2,5, for b _i, b _j not adjacent to z and w _i, w _j not adjacent to μ(z), a contradiction. □

Claim 16

If |C|≤ 4, then H contains a redundant set U of size at most 16 such that H − U is of the form tree¹.

Proof

Assume that |C|≤ 4, i.e. |μ(C)|≤ 4. Note that every (black) vertex of μ(C) has at most one neighbor in A by Claim 11, i.e. |N _A(μ(C))|≤ 4. Then

$$\displaystyle \begin{aligned}U := C \cup \mu(C) \cup N_{A}(\mu(C)) \cup \mu(N_{A}(\mu(C)))\end{aligned}$$

is a redundant set of size at most 16 such that H − U is of the form tree¹. □

Claim 17

Assume that |C|≥ 5. Then the following statements are true.

Case 1. If there exist vertices z ₁, z ₂ ∈ C sharing some neighbor in μ(A), then H is of the form tree².

Case 2. If for any two vertices y, z ∈ C, y, z share no neighbor in μ(A), then H is of the form tree³ or tree⁷ or H contains a redundant set U of size at most six such that H − U is of the form tree³.

Proof

We consider the two above cases.

Case 1. Without loss of generality, assume that z ₁, z ₂ ∈ C share a neighbor b ₁ ∈ μ(A). Let us consider the following occurrences which are exhaustive by symmetry.

1.1. z ₂ has another neighbor, say b ₂ ∈ μ(A). Note that then $b_{2} \nsim b_{1}$ since otherwise a banner₂ arises. Assume that there exist two vertices, without loss of generality, assume that they are b ₃, b ₄, not adjacent to z ₁, z ₂. Then {b ₃, w ₃, b, b ₄, w ₄, w ₂, b ₂, z ₂, b ₁, z ₁} induces an S _2,2,5, a contradiction. Hence, |N _μ(A)({z ₁, z ₂})|≥ k − 1. Since both z ₁ and z ₂ have at most k − 4 neighbors in μ(A), each of them has at least four neighbors in μ(A).

Let z ₃ ∈ C be adjacent to some vertex b _i ∈ N _μ(A)({z ₁, z ₂}). Then z ₃ has at least four neighbors in μ(A). Hence, z ₃ shares two neighbors in μ(A) with z ₁ or z ₂, a contradiction to Claim 9. So, there exists no other vertex in C (than z ₁, z ₂) having a neighbor in N _μ(A)({z ₁, z ₂}). Together with |C|≥ 5, this implies that |N _μ(A)({z ₁, z ₂})|≤ k − 1, i.e. |N _μ(A)({z ₁, z ₂})| = k − 1.

Without loss of generality, assume that z ₁, z ₂ are not adjacent to b _k. Since |C|≥ 5, there exist z ₃, z ₄ ∈ C such that z ₃, z ₄ are adjacent to b _k. Moreover, z ₃, z ₄ have no other neighbor in μ(A). By Claim 11, there exists a vertex b _i such that b _i ∼ z ₁ and w _i is not adjacent to μ(z ₃), μ(z ₄). Hence, by Claim 13, {μ(z ₃), z ₃, b _k, z ₄, μ(z ₄), w _k, b, b _i, w _i, z ₁} induces an S _2,2,5, a contradiction.

1.2. Every vertex of C adjacent to b ₁ has only one neighbor (b ₁) in μ(A). Note that, for every such vertex z, $\mu (z) \nsim w_{1}$ by Claim 10. Moreover, $\mu (z) \nsim w_{i} \in A$ for w _i ≠ w ₁, otherwise since by Claim 11, there exists a pair of vertices w _j, w _l ≠ w ₁ and non-adjacent to μ(z) and one has that {b _j, w _j, b, w _l, b _l, w _i, μ(z), z, b ₁, z′} induces an S _2,2,5 for z′ be another neighbor of b ₁ in C different from z, a contradiction.

Now, let C ₁₁ be the set of vertices of C ₁ adjacent to b ₁ and C ₁₂ := C ₁∖C ₁₁. If C ₁₂ = ∅, then H is of the form tree². Then assume that C ₁₂ ≠ ∅ and let y ∈ C ₁₂ and, without loss of generality, assume that y ∼ b ₂ ∈ μ(A). If y is not adjacent to two vertices, say μ(z ₁), μ(z ₂) ∈ μ(C ₁₁), then {μ(z ₁), z ₁, b ₁, z ₂, μ(z ₂), w ₁, b, w ₂, b ₂, y} induces an S _2,2,5, a contradiction.

If y is adjacent to two vertices μ(z ₁), μ(z ₂) ∈ μ(C ₁₁), then y is adjacent to every vertex b _i ∈ μ(A) different from b ₁, otherwise {z ₁, μ(z ₁), y, μ(z ₂), z ₂, b ₂, w ₂, b, w _i, b _i} induces an S _2,2,5, a contradiction.

Now, y has at least k − 1 neighbors in μ(A), a contradiction. Hence, C ₁₁ = {z ₁, z ₂} and every vertex y ∈ C ₁₂ is adjacent to exactly one vertex of μ(C ₁₁).

If μ(z ₁) is adjacent to two vertices y ₁, y ₂ ∈ C ₁₂, then {y ₁, μ(z ₁), y ₂, b _i, w _i, b} induces a banner₂ in the case that y ₁, y ₂ share the same neighbor b _i ∈ μ(A) by Claim 10 or $\{b_{i_{1}},y_{1},\mu (z_{1}),y_{2},b_{i_{2}},z_{1},b_{1},w_{1},b,w_{i}\}$ induces an S _2,2,5 for $b_{i_{1}},b_{i_{2}}$ be (different) neighbors of y ₁, y ₂ in μ(A), respectively, and w _i ∈ A different from $w_{1},w_{i_{1}},w_{i_{2}}$, a contradiction. Hence, each μ(z ₁), μ(z ₂) has at most one neighbor in C ₁₂. It implies that |C ₁₂|≤ 2 and thus, |C|≤ 4, a contradiction.

Case 2. If for every vertex μ(z) ∈ μ(C ₁), z is the only neighbor of μ(z), then H is of the form tree³.

Then assume that there is a vertex μ(z) ∈ μ(C ₁) such that z is not the only neighbor of μ(z). First we show that for every pair z ₁, z ₂ ∈ C, $\mu (z_{1}) \nsim z_{2}$. Indeed, for contradiction, suppose that μ(z ₁) ∼ z ₂. Without loss of generality, assume that z ₁, z ₂ are adjacent to b ₁, b ₂, respectively. Then $\mu (z_{2}) \nsim z_{1}$, otherwise by Claim 10, {μ(z ₂), z ₁, μ(z ₁), z ₂, b ₂, w ₂} induces a banner₂, a contradiction.

Moreover, N _μ(A)({z ₁, z ₂}) ≥ k − 2, otherwise by Claim 11, there exists a pair of vertices w _i, w _j not adjacent to μ(z) such that b _i, b _j not adjacent to z ₁, z ₂, and hence, {b _i, w _i, b, w _j, b _j, w ₂, b ₂, z ₂, μ(z ₁), z ₁} induces an S _2,2,5, a contradiction.

Hence, the non-neighbors of z ₁, z ₂ in μ(A) have at most two neighbors in C, i.e. |C|≤ 4, a contradiction.

Then there exists some vertex z ∈ C, such that μ(z) is adjacent to some vertex of A. Without loss of generality, assume that z ∼ b ₁ and μ(z) ∼ w ₂. Then $b_{2} \nsim z$, by Claim 10. We consider the two following subcases.

2.1. b ₂ ∼ y for some y ∈ C. Then for every x ∈ C∖{y, z}, μ(x) ∼ w ₂, otherwise {z, μ(z), w ₂, b ₂, y, b, w _i, b _i, x, μ(x)} induces an S _2,2,5 for b _i ∼ x, a contradiction. By Claim 11, that also implies that μ(y) is not adjacent to any vertex w _i ∈ A such that b _i ∼ x for some x ∈ C ₁ different from y, otherwise |C| = 2 < 5, a contradiction. Now,

$$\displaystyle \begin{aligned}U := \{w_{2},b_{2},y,\mu(y)\} \cup N_{A}(\mu(y)) \cup \mu(N_{A}(\mu(y)))\end{aligned}$$

is a redundant set containing at most six vertices such that H − U is of the form tree³.

2.2. N _C(b ₂) = ∅. Assume that there exists some vertex y ∈ C, without loss of generality, assume that y ∼ b ₃ and μ(y) ∼ w ₂. Then for every x ∈ C different from y, z, μ(x) ∼ w ₂, otherwise {z, μ(z), w ₂, μ(y), y, b, w _i, b _i, x, μ(x)} induces an S _2,2,5 for b _i ∼ x, a contradiction. Now,

$$\displaystyle \begin{aligned}U := \{w_{2},b_{2}\}\end{aligned}$$

is a redundant set of size two such that H − U is of the form tree³.

Now, if there exists no vertex pair y, z ∈ C, such that μ(y), μ(z) share the same neighbor in A, then H is of the form tree⁷. □

All above claims finish the proof.

Appendix 3: Proof of Lemma 6

Proof (of Lemma 6)

To simplify the proof, we start with a pre-processing consisting in detecting augmenting (l, m)-extended-chains whose path-part is of length at most 2l since such an augmenting (l, m)-extended-chain contains at most $\frac {1 - (m-1)^{l}}{2 - m} + 2l + 1$ vertices and can be enumerated in polynomial time.

In order to determine whether S admits an augmenting (l, m)-extended-chain whose path-part is of length at least 2l + 2, we first find a candidate, i.e. a pair (L, R), where L and R are disjoint trees consisting induced paths x ₀, x ₁, …, x _l and x _2p−l, x _2p−l+1, …, x _2p, respectively (p ≥ l + 1) and every vertex outside that path of L (R, respectively) is of distance at most l − 1 from x ₀ (x _2p, respectively) and not adjacent to any vertices among {x ₁, x ₂, …, x _l, x _2p−l, x _2p−l+1, …, x _2p}. If such a candidate does not exist, then there is no augmenting (l, m)-extended-chain whose path-part is of length at least 2l + 2 for S. Moreover, since such candidates contain only finite vertices, we can enumerate them in polynomial time.

Our purpose is to find an alternating chain connecting x _l and x _2p−l. Evidently, if there are no such chains, then there is no augmenting (l, m)-extended-chain whose path-part is of length at least 2l + 2 for S containing L and R.

Having found a candidate (L, R), we have the following observations about vertices of G in the sense that the vertices not satisfying these assumptions can be simply removed from the graph, since they cannot occur in any valid alternating chain connecting x _l and x _2p−l. Let P := (x ₀, x ₁, …, x _2p) be the path part of a desired (l, m)-extended-chain.

Claim 18

• 1. Each white vertex has at least two black neighbors.

• 2. Each black vertex lying outside L and R has exactly two white neighbors.

• 3. No black vertex outside L and R has a neighbor in L or R.

• 4. No white vertex outside L and R has a neighbor in L or R, except such a neighbor is x _l or x _2p−l.

  Moreover, no white vertex outside P has a neighbor in P.

Proof

1. and 2. are obvious since a vertex not satisfying these conditions cannot occur in any augmenting extended-chain containing L and R as sub-extended-chains.

Note that x _l and x _2p−l are black vertices. Hence, if a black vertex outside L and R has a neighbor in L or R, then clearly such a vertex cannot belong to the desired augmenting chain, similar for a white vertex outside L and R.

If a white vertex outside P has a neighbor in P, then clearly such a neighbor is black and hence it has at least three white neighbors, a contradiction.

From the conditions of the above claim, we have the following observation.

Claim 19

If S admits an augmenting (l, m)-extended-chain containing L and R, then no vertex of P∖(L ∪ R) is the center of an induced claw.

Proof

By contradiction, suppose that G contains a claw G[C], where C = {a, b, c, d}, whose center a (i.e., the vertex of degree three) is a vertex x _j on P. Without loss of generality, we choose a claw such that |{b, c, d}∖P| is minimal and, among such claws, choose a claw such that j is minimum. Note that, since there exists at least one vertex of {b, c, d} lying outside P, together with 3. of Claim 18, l + 1 ≤ j ≤ 2p − l − 1. Moreover, since every black vertex of P has all its white neighbors lying in P, every vertex of C∖P is black.

We shall use the following convention: for a black vertex v outside P, if only one of the two white neighbors of v is defined explicitly, then the other is denoted as $\bar {v}$. Also, for a vertex v of C not belonging to P such that N(v) ∩ P ≠ ∅, we denote by r(v) the largest index in {j, j + 1, …, 2p − l − 1} and by s(v) the smallest index in {l + 1, l + 2, …, j} such that v is adjacent to x _r(v), x _s(v).

We now analyze three cases: exactly one (C1), two (C2), or three (C3) vertex/vertices of {b, c, d} do(es)n’t belong to P.

Case (C1). Without loss of generality, assume that b = x _j−1 and c = x _j+1. Then we have the following observations.

• (1) d is not adjacent to x _j−2, x _j+2. Indeed, if d ∼ x _j−2 (similar for the case d ∼ x _j+2), then {x _j−2, x _j−1, x _j, d, x _r(d), x _r(d)+1, …, x _r(d)+l−1} induces a banner_l in the case r(d) ≥ j + 2 or {d, x _j−2, x _j−1, x _j, x _j+1, …, x _j+l} induces a banner_l in the case r(d) = j, a contradiction.

• (2) r(d) = j or s(d) = j. Indeed, by (1), suppose that r(d) ≥ j + 3 and s(d) ≤ j − 3. Then {x _j−1, x _j, d, x _s(d), x _s(d)−1, …, x _s(d)−l+1, x _r(d), x _r(d)+1, …, x _r(d)+l−1} induces an S _2,l,l, a contradiction.

• (3) s(d) ≥ j − 3 and r(d) ≤ j + 3. Indeed, suppose that s(d) ≤ j − 4 (similar for the case r(d) ≥ j + 4). Then by (2), {x _j−2, x _j−1, x _j, x _s(d), x _s(d)−1, …, x _s(d)−l+1, x _j+1, x _j+2, …, x _j+l−1} induces an S _2,l,l, a contradiction.

• (4) r(d) = s(d) = j. Indeed, by (2) and (3), suppose that r(d) = j + 3 and s(d) = j (similar for the case s(d) = j − 3 and r(d) = j). Among {x _j, x _j+3}, there exists at most one white vertex. Hence, $\{x_{j + 2},x_{j + 1},\bar {d},d,x_{j+3},x_{j + 4},x_{j + 5},\ldots ,x_{j + l + 3},x_{j},$ x _j−1, …, x _j−l} induces an $R^{1}_{l}$, a contradiction.

Now, since r(d) = s(d) = j, $\{\bar {d},d,x_{j},x_{j {-} 1},x_{j {-} 2},\ldots ,x_{j {-} l},x_{j {+} 1},x_{j {+} 2},\ldots ,$ x _j+l} induces an S _2,l,l, a contradiction.

Case (C2). Without loss of generality, assume that b = x _j−1 and c and d are outside P. Then we have the following observations.

• (1) x _j+1 is adjacent both to c and d to avoid (C1).

• (2) Also to avoid (C1), c is adjacent to x _s(c)+1, x _r(c)−1, similarly for d.

• (3) It cannot happen that s(c) = s(d) ≤ j − 2 or r(c) = r(d) ≥ j + 2. Indeed, say if s(c) = s(d) ≤ j − 2, then {c, x _j+1, d, x _s(c), x _s(c)−1, …, x _s(c)−l} induces a banner_l, a contradiction.

• (4) Similarly, if s(c) = s(d) = j, then there exists no common neighbor x _i of c and d for i ≥ j + 2 and if r(c) = r(d) = j + 1, then there exists no common neighbor x _i of c and d for i ≤ j − 2. And in both cases, c and d have no common neighbor outside P.

• (5) c and d are not adjacent to x _j−2. Indeed, suppose that c ∼ x _j−2 (similar for the case d ∼ x _j−2). Then r(c) = j + 1 (similarly, r(d) = j + 1), otherwise {x _j, x _j−1, x _j−2, c, x _r(c), x _r(c)+1, …, x _r(c)+l−1} induces a banner_l, a contradiction, and s(c) = j − 3, otherwise {x _j, x _j−1, x _j−2, c, x _s(c), x _s(c)−1, …, x _s(c)−l+1} induces a banner_l, a contradiction. Moreover, d is neither adjacent to x _j−2 nor x _j−3 also by (4). Hence, s(d) = j, otherwise {x _j−1, x _j−2, c, x _j, d, x _s(d), x _s(d)−1, …, x _s(d)−l+1} induces a banner_l, a contradiction. Now, among {x _j, x _j+1}, there exists exactly one white vertex. Moreover, $c \nsim \bar {d}$ by (4). Now, $\{d,\bar {d},x_{j + 1},c,x_{j - 3},$ x _j−4, …, x _j−l−2, x _j+2, x _j+3, …, x _j+l+1}, induces an S _2,l,l, a contradiction.

• (6) By (2) and (5), if s(c) ≤ j − 3, then s(c) ≤ j − 4.

• (7) s(c) = j or r(c) = j + 1. Similarly, s(d) = j or r(d) = j + 1. Indeed, by (5) and (6), if s(c) ≤ j − 4 and r(c) ≥ j + 2, then {x _j−1, x _j, c, x _s(c), x _s(c)−1, …, x _s(c)−l+1, x _r(c), x _r(c)+1, …, x _r(c)+l−1} induces an S _2,l,l, a contradiction.

• (8) s(c) = j or r(d) = j + 1 (similarly, s(d) = j or r(c) = j + 1). Indeed, by (5) and (6), without loss of generality, suppose that s(c) ≤ j − 4 and r(d) ≥ j + 2. Then by (7), r(c) = j + 1 and s(d) = j. Hence, {x _j−2, x _j−1, x _j, c, x _s(c), x _s(c)−1, …, x _s(c)−l+2, d, x _r(d), x _r(d)+1, …, x _r(d)+l−2} induces an S _2,l,l, a contradiction.

• (9) s(c) = j or s(d) = j. Indeed, by (5) and (6), without loss of generality, suppose that s(c), s(d) ≤ j − 4. Then r(c) = r(d) = j + 1, by (7). Now, by (3), without loss of generality, assume that s(c) < s(d). Then by (4), {x _s(d)+1, d, x _j+1, c, x _s(c), x _s(c)−1, …, x _s(c)−l+2, x _j+2, x _j+3, …, x _j+l+1} induces an S _2,l,l, a contradiction.

• (10) r(c) = j + 1 or r(d) = j + 1. Indeed, if r(c), r(d) ≥ j + 2, then by (7), s(c) = s(d) = j. Without loss of generality, by (2) and (4), assume that r(c) > r(d) + 1. Then {x _r(d), d, x _j, c, x _r(c), x _r(c)+1, …, x _r(c)+l−2, x _j−1, x _j−2, …, x _j−l} induces an S _2,l,l, a contradiction.

• (11) s(c) = s(d) = j. Indeed, by (5) and (6), suppose that s(c) ≤ j − 4 (similar for the case that s(d) ≤ j − 4). Then by (9), (8), and (7), s(d) = j, r(d) = r(c) = j + 1. Note that, among {x _j, x _j+1, x _s(c), x _s(c)+1}, neighbors of c, there exist exactly two white vertices and hence, $c \nsim \bar {d}$. Now, $\{\bar {d},d,x_{j+1},c,x_{s(c)},x_{s(c) - 1},\ldots ,x_{s(c) - l + 2},$ x _j+2, x _j+3, …, x _j+l+1} induces an S _2,l,l, a contradiction.

• (12) r(c) = r(d) = j + 1. Indeed, by (10), suppose that r(c) = j + 1 and r(d) ≥ j + 2. Among x _j, x _j+1, there exists only one white vertex and $d \nsim \bar {c}$ by (4). Then $\{\bar {c},c,x_{j},x_{j - 1},x_{j - 2},\ldots ,x_{j - l},d,x_{r(d)},x_{r(d) + 1},\ldots ,x_{r(d) + l - 2}\}$ induces an S _2,l,l, a contradiction.

Now, $\{\bar {c},c,x_{j},d,\bar {d},x_{j - 1},x_{j - 2},\ldots ,x_{j - l},x_{j + 1},x_{j + 2},\ldots ,x_{j + l + 1}\}$ induces an $R^{2}_{l}$, a contradiction.

Case (C3). We have the following observations.

• (1) First, note that, r(b), r(c), and r(d) (and similarly, s(b), s(c), and s(c)) are three mutually different integers. Otherwise, suppose that r(b) = r(c). Then we have the claw {x _r(c), x _r(c)+1, b, c}, i.e. (C2).

• (2) To avoid (C1), if b ∼ x _i for some i, then b is adjacent to at least one vertex among x _i−1, x _i+1. It implies b is adjacent to x _s(b)+1, x _r(b)−1. Similarly for c and d.

• (3) Moreover, by the minimality of j and to avoid (C2), we know that x _j−1 has exactly two neighbors in {b, c, d}, say b and c. To avoid (C1) and (C2), we conclude that x _j+1 is adjacent to d and has at least one neighbor in {b, c}, say c. Moreover, $b \nsim x_{j + 1}$. Indeed, if b ∼ x _j+1, then r(b), r(c), r(d) ≤ j + 2, otherwise {x _j−1, b, x _j+1, c, x _r(c), x _r(c)+1, …, x _r(c)+l−1} or {x _j−1, c, x _j+1, b, x _r(b), x _r(b)+1, …, x _r(b)+l−1} or {b, x _j−1, c, x _j+1, d, x _r(d), x _r(d)+1, …, x _r(d)+l−2} induces a banner_l depending on which is the largest index among r(b), r(c), r(d), a contradiction. But now, j + 1 ≤ r(c), r(b), r(d) ≤ j + 2, a contradiction with the mutual difference of r(b), r(c), and r(d).

• (4) It also implies that at least one of s(b), s(c) is less than j − 1 and at least one of r(d), r(c) is greater than j + 1.

• (5) $b \nsim x_{j + 1}$, together with b ∼ x _r(b)−1, it implies that if r(b) ≥ j + 2, then r(b) ≥ j + 3. Similarly, if s(d) ≤ j − 2, then s(d) ≤ j − 3.

• (6) In a pair of consecutive vertices of P, there is a black vertex and a white vertex. Hence, b, c, d are not adjacent to three pairs of consecutive vertices of P, otherwise we have a black vertex with three white neighbors, a contradiction. Together with c is adjacent to x _s(c)+1 and x _r(c)−1, it leads to either r(c) ≤ j + 2 or s(c) ≥ j − 2. Moreover, if c is adjacent to x _j−2, x _j+2, then s(c) = j − 2 and r(c) = j + 2. Similarly, we have the following observations: r(b) = j or s(b) ≥ j − 2, s(d) = j or r(d) ≤ j + 2.

• (7) c and b cannot share a neighbor x _i for some i ≤ j − 2, otherwise {x _i, c, x _j, b, x _r(b), …, x _r(b)+l−1}, {b, x _i, c, x _j, d, x _r(d), …, x _r(d)+l−2}, or {x _i, b, x _j, c, x _r(c), …, x _r(c)+l−1} induces a banner_l depending on which is the largest index among r(b), r(c), r(d) (note that at least one of these integers is bigger than j + 1 and they are mutually different by (1)), a contradiction. Moreover, b and c cannot share a neighbor x _i for some i ≥ j + 2, otherwise {x _j, c, x _i, b, x _s(b), x _s(b)−1, …, x _s(b)−l+1} or {x _j, b, x _i, c, x _s(c), …, x _s(c)−l+1} induces a banner_l depending on which one is larger among s(b) and s(c). Similarly, c and b cannot share a white neighbor outside P. By similar arguments, these properties are also true for the two pairs c, d and b, d.

• (8) s(c) ≥ j − 2, similarly, r(c) ≤ j + 2. Moreover, if s(c) = j − 2, then r(c) = j + 1. Similarly, if r(c) = j + 2, then s(c) = j − 1. Indeed, suppose that s(c) ≤ j − 4. Then c ∼ x _j−2, otherwise {x _j−1, x _j−2, x _j−3, c, x _r(c), x _r(c)+1, …, x _r(c)+l−1} induces a banner_l or {x _j−2, x _j−1, c, x _s(c), x _s(c)−1, …, x _s(c)−l+1, x _r(c), x _r(c)+1, x _r(c)+l−1} induces an S _2,l,l depending on c ∼ x _j−3 or not. But now, c is adjacent to {x _s(c), x _s(c)+1, x _j+1, x _j, x _j−1, x _j−2}, a contradiction to (6). Now, if s(c) = j − 3, then c ∼ x _j−2 by (2) and r(c) = j + 1 by (6). Hence, {c, x _j−l−3, …, x _j−4, x _j−3, …, x _j+1, x _j+2, …, x _j+l+1} induces an $R^{3}_{l}$, a contradiction. Moreover, if s(c) = j − 2 and r(c) = j + 2, then {c, x _j−l−2, …, x _j−3, x _j−2, …, x _j+1, x _j+2, …, x _j+l+2} induces an $R^{3}_{l}$, a contradiction.

• (9) r(b) = j or s(b) = j − 1, similarly, r(d) = j + 1 or s(d) = j. Indeed, if r(b) ≥ j + 3 and s(b) ≤ j − 2, then {x _j, x _j+1, x _j+2, b, x _s(b), x _s(b)−1, …, x _s(b)−l+1} induces a banner_l or {x _j+1, x _j, b, x _s(b), x _s(b)−1, …, x _s(b)−l+1, x _r(b), x _r(b)+1, …, x _r(b)+l−1} induces an S _2,l,l depending on b ∼ x _j+2 or not, a contradiction.

• (10) s(b) ≥ j − 3, similarly, r(d) ≥ j + 3. Indeed, suppose that s(b) ≤ j − 4. Then r(b) = j, by (9). Now b is not adjacent to x _j−2 and x _j−3 at the same time, otherwise either {b, x _j−l−4, …, x _j−5, x _j−4, …, x _j, x _j+1, …, x _j+l} induces an $R^{3}_{l}$ or b is adjacent to three pairs of consecutive vertices of P, a contradiction to (6). Hence, $b \nsim x_{j - 2}$, otherwise {x _j−3, x _j−2, b, x _s(b), x _s(b)−1, …, x _s(b)−l+1, x _j, x _j+1, …, x _j+l−1} induces an S _2,l,l, a contradiction. Suppose that b ∼ x _j−3. Then c ∼ x _j−2, otherwise {b, x _j−3, x _j−2, x _j−1, c, x _r(c), x _r(c)+1, …, x _r(c)+l−2} induces a banner_l, a contradiction. Now, r(c) = j + 1 by (8), r(d) ≥ j + 2 by (1), and s(d) = j by (9). Hence, $\{x_{j - 2},c,x_{j},b,x_{s(b),x_{s(b) - 1}},\ldots ,x_{s(b) - l + 2},d,$ x _r(d), x _r(d)+1, …, x _r(d)+l−2} induces an S _2,l,l, a contradiction. Thus, $b \nsim x_{j - 3}$. Now, {x _j−3, x _j−2, x _j−1, b, x _s(b), …, x _s(b)−l+2, c, x _r(c), …, x _r(c)+l−2} induces an S _2,l,l, a contradiction.

• (11) r(b) = j, similarly, s(d) = j. Indeed, suppose that r(b) ≥ j + 3. Then by (9), s(b) = j − 1. Moreover, s(c) = j − 2, r(c) = j + 1, r(d) ≥ j + 2, and s(d) = j by (1), (8), and (9). Now, {x _r(b)−1, b, x _j, c, x _j−2, x _j−3, …, x _j−l, d, x _r(d), x _r(d)+1, …, x _r(d)+l−2} or {x _r(d), d, x _j, c, x _j−2, x _j−3, …, x _j−l, b, x _r(b), x _r(b)+1, …, x _r(b)+l−2} induces an S _2,l,l depending on r(d) > r(b) or r(b) > r(d) (note that by (2) and (7), if r(b) > r(d), then r(b) > r(d) + 1).

• (12) s(c) = j − 1, similarly, r(c) = j + 1. Indeed, suppose that s(c) = j − 2. Then r(c) = j + 1 by (8), s(b) = j − 1 by (1), (2), and (7) and r(d) ≥ j + 2 by (1). Among x _j and x _j−1, there exists only one white vertex. Consider the other white neighbor of b, say $\bar {b}$. Then $\{\bar {b},b,x_{j},c,x_{j - 2},x_{j - 3},\ldots ,x_{j - l},d,x_{r(d)},x_{r(d) + 1},\ldots ,x_{r(d) + l - 2}\}$ induces an S _2,l,l, a contradiction.

• (13) x _j is black, otherwise $\{\bar {c},c,x_{j},b,x_{s(b)},\ldots ,x_{s(b) - l + 2},d,x_{r(d)},\ldots ,x_{r(d) + l - 2}\}$ induces an S _2,l,l, a contradiction. Now, by the symmetry, we have three remaining cases, which are considered follows.

Case 3.1. b is adjacent to x _j−2 and x _j−3, d is adjacent to x _j+2 and x _j+3. Then {x _j, x _j−l−2, …, x _j−3, b, x _j−1, c, x _j+1, d, x _j+3, …, x _j+l+2} induces an $R^{3}_{l}$, a contradiction.

Case 3.2. s(b) = j − 2 and r(d) = j + 2. Then $\{x_{j},x_{j - l - 1},\ldots ,x_{j - 2},\bar {b},b,x_{j - 1},c,$ $x_{j + 1},d,\bar {d},$ x _j+2, …, x _j+l+1} induces an $R^{4}_{l}$, a contradiction.

Case 3.3. s(b) = j − 2 and d is adjacent to x _j+2 and x _j+3. Then {x _j, x _j−l−1, …, $x_{j - 2},\bar {b},b,$ x _j−1, c, x _j+1, d, x _j+2, x _j+3, …, x _j+l+1} induces an $R^{5}_{l}$, a contradiction.

Our purpose here is to detect an augmenting extended-chain whose path-part is of length at least 2l + 2. We first find candidates (L, R) as described above. Note that such candidates can be enumerated in polynomial time. Then perform Steps (a) through (d) for each such pair:

• (a) remove all black vertices that have a neighbor in L or in R,

• (b) remove the vertices of L and R except for x _l and x _2p−l, and

• (c) remove all the vertices that are the center of a claw in the remaining graph,

• (d) then in the resulting claw-free graph, determine whether there exists an alternating chain between x _l and x _2p−l by the method described in [28, 33].

For each candidate, Steps (a) through (d) can be implemented in time O(n ⁴). Hence, we have the conclusion of the lemma.

Appendix 4: Proof of Lemma 7

The proof is consisted of the six following observations.

Lemma 10

If G contains no augmenting P ₃ , then an augmenting tree ¹ (if any) can be found in time O(n ¹⁷).

Proof

Refer to Figure 2, tree¹ with parameter r. If r = 1, then tree¹ is a P ₃. Assume that G contains an augmenting graph tree¹, for some r ≥ 2. Therefore, G contains an induced P ₅ = (b ₁, a ₁, x, a ₂, b ₂), where b ₁, b ₂ ∈ B ¹ and b ₁, b ₂ are non-adjacent to any vertex of W{a ₁, x, a ₂}. If G contains no such an initial structure, then it contains no augmenting tree¹. If such a structure exists, then we proceed as follows.

Let us denote $A = \{a \in W(x) \backslash \{a_{1},a_{2}\} : a \nsim b_{1},b_{2}\}$ and for a ∈ A, let K(a) denote the set of black neighbors of a in B ₁ not adjacent to any vertex of {x, a ₁, a ₂, b ₁, b ₂}. Notice that a desired augmenting tree exists only if K(a) ≠ ∅ for every a ∈ A. Finally, let $V' = \bigcup \limits _{a \in A}K(a)$. Since K(a) ⊆ B ¹ for every a ∈ A, K(a) ∩ K(a′) = ∅ for every pair of distinct vertices a, a′∈ A.

Consider any vertex a ∈ A, we show that K(a) induces a clique for every a ∈ A. Indeed, suppose that K(a) contains two non-adjacent vertices b ₁, b ₂. Then {b ₁, a, b ₂} induces an augmenting P ₃, a contradiction. It follows that a desired augmenting tree¹ exists if and only if α(G[V ′]) = |A|.

We show that G[V ′] must be P ₅-free. Indeed, consider an induced P ₄ = (p ₁, p ₂, p ₃, p ₄) in G[V ′] and let a ∈ A be such that p ₁ ∈ K(a). Then none of the vertices p ₃, p ₄ is adjacent to a because K(a) is a clique. Thus, p ₂ ∈ K(a), otherwise {b ₁, a ₁, x, a ₂, b ₂, a, p ₁, p ₂, p ₃, p ₄} induces an S _2,2,5, a contradiction. Hence, if G[V ′] induces a P ₄ = (p ₁, p ₂, p ₃, p ₄), then p ₁ and p ₂ have a common white neighbor, while p ₂ and p ₃ have no common white neighbor, a contradiction to when consider an induced P ₄ = (p ₂, p ₃, p ₄, p ₅) in the P ₅ = (p ₁, p ₂, p ₃, p ₄, p ₅).

Since the P ₅-free graph class is MIS-solvable in time O(n ¹²) [22], one can find a simple augmenting tree containing the P ₅ (b ₁, w ₁, b, w ₂, b ₂) in O(n ¹²). With an exhaustive search, all candidate P ₅ of augmenting trees can be found in time O(n ⁵). For such candidates P ₅’s, V ′ can be built in O(n ³). Hence, we have the conclusion of the lemma.

Lemma 11

If G contains neither augmenting P ₃ nor P ₇ , then an augmenting tree ² (if any) can be found in time O(n ¹⁴).

Proof

Refer to Figure 2, tree² with parameter r and s. We may restrict ourselves to finding a tree² with r, s ≥ 2, since any tree² with, say r = 1, either equals to P ₇ or contains a redundant subset U of size two such that tree² − U is of the form tree¹.

As a candidate, consider the subgraph of tree² (see Figure 2) induced by {a ₁, a ₂, b ₁, b ₂, c ₁, c ₂, d ₁, d ₂, x, y, z} such that b ₁, b ₂, d ₁, d ₂ ∈ B ¹ and x, z share no common white neighbor other than y.

Let us denote A = (W(x) ∪ W(z))∖{a ₁, a ₂, c ₁, c ₂, y}. For a ∈ A, let K(a) denote the set of black neighbors of a in B ¹ not adjacent to any vertex of {x, b ₁, b ₂, d ₁, d ₂}. Note that, by the assumption, every vertex of A is either adjacent to x or y. Notice that a desired augmenting tree exists only if K(a) ≠ ∅ for every a ∈ A.

We show that K(a) induces a clique. Indeed, suppose that K(a) contains two non-adjacent vertices b ₁, b ₂. Then {b ₁, a, b ₂} induces an augmenting P ₃, a contradiction.

Since for every a ∈ A, K(a) ∈ B ¹, K(a) ∩ K(a′) = ∅ for every pair of distinct vertices a, a′∈ A.

Finally, let $V' = \bigcup \limits _{a \in A}K(a)$. It follows that a desired augmenting tree² exists if and only if α(G[V ′]) = |A|.

We now show that G[V ′] is P ₃-free. Suppose, to the contrary, that (p ₁, p ₂, p ₃) is an induced P ₃ in G[V ′]. Let a ∈ A such that p ₁ ∈ K(a). Since K(a) is a clique, p ₃ is not adjacent to a. Assume that p ₃ ∼ a′. Then since p ₂ ∈ B ¹, p ₂ is not adjacent to at least one vertex among a, a′. Without loss of generality, assume that $p_{2} \nsim a$, and a is adjacent to x, but not to z. Then {d ₂, c ₂, z, c ₁, d ₁, y, x, a, p ₁, p ₂} induces an S _2,2,5, a contradiction.

Hence, G[V ′] is a disjoint union of cliques, i.e. a maximum independent set in G[V ′] can be found in linear time. All candidates of the form tree² whose r = s = 2 can be found by an exhaustive search in time O(n ¹¹). For such candidates P ₅’s, V ′ can be built in O(n ³). Hence, we have the conclusion of the lemma.

Lemma 12

If G contains neither augmenting P ₃ nor P ₅ , then an augmenting tree ³ or an augmenting tree ⁴ (if any) can be found in time O(n ³¹).

Proof

First, note that tree⁴ is a special case of tree³. We refer to Figure 2, tree³ for indices. Moreover, we may restrict ourselves to finding a tree³ with s ≥ 3, since any tree³ with, say, s ≤ 2 is either of the form tree¹ or contains a redundant subset U of size four such that tree³ − U is of the form tree¹.

As a candidate, consider the subgraph of tree³ (see Figure 2) induced by $\{d_{1},c_{1},b^{1}_{1},$ $a^{1}_{1},x,a^{2}_{1},b^{2}_{1},c_{2},d_{2},a^{3}_{1},b^{3}_{1},c_{3},d_{3}\}$ such that $b^{1}_{1},b^{2}_{1},b^{3}_{1} \in B^{2}$, d ₁, d ₂, d ₃ ∈ B ¹. Let us denote $A = W(x) \backslash \{a^{1}_{1},a^{2}_{1},a^{3}_{1}\}$. For a ∈ A, let K(a) denote the set of black neighbors b of a in B ¹ ∪ B ² and not adjacent to any vertex of $\{x,b^{1}_{1},b^{2}_{1},b^{3}_{1},d_{1},d_{2},d_{3}\}$ such that if b ∈ B ², then G contains a pair of adjacent vertices c _b and d _b such that c _b∉W(x), W(b) = {a, c _b}, d _b ∈ B ¹, and d _b is not adjacent to any vertex of $\{x,b^{1}_{1},b^{2}_{1},b^{3}_{1},d_{1},d_{2},d_{3},b\}$ (note that d _b may coincide with d ₁, d ₂, or d ₃). Let $V' = \bigcup \limits _{a \in A}K(a)$. And again, by the existence of a desired augmenting tree³, K(a) is not empty for all a ∈ A. Note that by the assumption, K(a) ∩ K(a′) = ∅ for every pair of distinct vertices a, a′∈ A.

Consider any vertex a ∈ A, we show that K(a) induces a clique. Indeed, suppose that K(a) contains two non-adjacent vertices b, b′. By the symmetry, we consider the three following cases.

Case 1. b, b′∈ B ¹. Then {b, a, b′} induces an augmenting P ₃, a contradiction.

Case 2. b′∈ B ¹ and b ∈ B ². Then {b′, a, b, c _b, d _b} induces an augmenting P ₅, a contradiction.

Case 3. b, b′∈ B ². Then $c_{b} \neq c_{b'}$, otherwise $\{b,c_{b},b',a,x,a^{1}_{1}\}$ induces a banner₂, a contradiction. Now, $\{c_{b'},b',a,b,c_{b},x,a^{i}_{1},b^{i}_{1},c_{i},d_{i}\}$ induces an S _2,2,5, for c _i is among c ₁, c ₂, c ₃ different from $c_{b},c_{b'}$, a contradiction.

It follows that a desired augmenting tree³ exists if and only if α(G[V ′]) = |A|.

Given a, a′∈ A and b ∈ K(a) ∩ B ², b′∈ K(a′) such that $b \nsim b'$ and if b′∈ B ², assume that $d_{b} \neq d_{b'}$, we show that $b' \nsim d_{b}$. Indeed, suppose that b′∼ d _b. Then $b' \nsim c_{b}$, otherwise $c_{b'} = c_{b}$, and hence, $d_{b'} = d_{b}$, a contradiction. Thus, $\{b^{1}_{1},a^{1}_{1},x,a^{2}_{1},b^{2}_{1},a',b',d_{b},c_{b},b\}$ induces an S _2,2,5, a contradiction. Now, if b′∈ B ², then $d_{b} \nsim d_{b'}$, otherwise $\{b^{1}_{1},a^{1}_{1},x,a^{2}_{1},b^{2}_{1},a',b',c_{b'},d_{b'},d_{b}\}$ induces an S _2,2,5, a contradiction.

Hence, for every pair of non-adjacent vertices b, b′ such that b ∈ K(a) ∩ B ², b′∈ K(a′) for two distinct vertices a, a′∈ A, {b, b′, d(b)} is independent. Moreover, if b′∈ B ², then $\{b,b',d_{b},d_{b'}\}$ is independent.

Now, assume that B′ is a maximum independent set of G[V ′]. Let C′ := {c _b : b ∈ B′∩ B ²}, D′ := {d _b : b ∈ B′∩ B ²}. Then by above arguments, B′∪ D′ is independent. And in the case that |B′| = |A|, H := G[A ∪ B′∪ C′∪ D′] is an augmenting graph of the form tree³ of G.

As in Lemma 10, we show that G[V ′] is P ₅ free. Indeed, consider an induced P ₄ = (p ₁, p ₂, p ₃, p ₄) in G[V ′] and let a ∈ A such that p ₁ ∈ K(a). Then none of the vertices p ₃, p ₄ is adjacent to a because K(a) is a clique. But now, p ₂ ∈ K(a), otherwise $\{b^{1}_{1},a^{1}_{1},x,a^{2}_{1},b^{2}_{1},a,p_{1},p_{2},p_{3},p_{4}\}$ induces an S _2,2,5, a contradiction. Hence, if G[V ′] induces a P ₄ = (p ₁, p ₂, p ₃, p ₄), then p ₁ and p ₂ have a common white neighbor, while p ₂ and p ₃ have no common white neighbor, a contradiction to when consider an induced P ₄ = (p ₂, p ₃, p ₄, p ₅) in the P ₅ = (p ₁, p ₂, p ₃, p ₄, p ₅).

All candidates can be found by an exhaustive search in time O(n ¹⁹). For such candidates, V ′ can be built in O(n ³). Again, by the solution for the MIS problem in P ₅-free graphs [22], we have the conclusion of the lemma.

Lemma 13

An augmenting tree ⁵ (if any) can be found in time O(n ¹⁴).

Proof

Refer to Figure 2, tree⁵ with parameter r and s. We may restrict ourselves to finding a tree⁵ with r, s ≥ 1 and r ≥ 2, since a tree⁵ with, say, r = 0 contains a redundant set U of size four such that tree⁵ − U is of the form tree¹, and a tree⁵ with r = s = 1 can be found in time O(n ⁹).

As a candidate, consider the subgraph of tree⁵ (see Figure 2) induced by {a ₁, a ₂, b ₁, b ₂, c ₁, d ₁, u, v, x, y, z} such that b ₁, b ₂, v, d ₁ ∈ B ² and x, y share no common white neighbor other than u. Let us denote A _x = W(x)∖{a ₁, a ₂, u} and A _y = W(y)∖{c ₁, u} and for a ∈ A := A _x ∪ A _y, let K(a) denote the set of common black neighbors of a and z in B ² not adjacent to any vertex of {x, y, b ₁, b ₂, v, d ₁}.

Note that by the assumption, every vertex of A is either adjacent to x or y. Since K(a) ⊆ B ² for every a ∈ A, K(a) ∩ K(a′) = ∅, for every pair of distinct vertices a, a′∈ A.

Consider a pair of distinct vertices b, b′∈ K(a) for some a ∈ A. If $b \nsim b'$, then {b, a, b′, z, v, u} induces a banner₂, a contradiction. Hence, K(a) is a clique for all a ∈ A.

Now, let $V'(x) := \bigcup \limits _{a \in A_{x}}(K(a))$, $V'(y) := \bigcup \limits _{a \in A_{y}}(K(a))$, and $V' := V'(x) \cup V^{\prime }_{y}$. Note that, V ′(x) ∩ V ′(y) = ∅ by the definition. Then a desired augmenting tree⁵ exists if and only if K(a) ≠ ∅ for every a ∈ A and α(G[V ′]) = |A|.

As in Lemma 11, we show that G[V ′] is P ₃-free. Suppose, to the contrary, that (p ₁, p ₂, p ₃) is an induced P ₃ in G[V ′]. Let a ∈ A such that p ₁ ∈ K(a). Since K(a) is a clique, p ₃ is not adjacent to a. Assume that p ₃ ∼ a′. Since p ₂ ∈ B ², p ₂ is not adjacent to at least one vertex among a, a′. Without loss of generality, assume that $p_{2} \nsim a$ and a is adjacent to y, but not to x. Then {b ₂, a ₂, x, b ₁, a ₁, u, y, a, p ₁, p ₂} induces an S _2,2,5, a contradiction. Hence, a maximum independent set can be found in G[V ′] in linear time.

All candidates can be found by an exhaustive search in time O(n ¹¹). For such candidates, V ′ can be build in O(n ³). Hence, we have the conclusion of the lemma.

Lemma 14

An augmenting tree ⁶ (if any) can be found in time O(n ²⁷).

Proof

Refer to Figure 2, tree⁶ with parameter r and s. We may restrict ourselves to finding a tree⁶ with r, s ≥ 2, since a tree⁶ with, say, r = 1, contains a redundant set U of size four such that tree⁶ − U is of the form tree¹.

As a candidate, consider the subgraph of tree⁶ (see Figure 2) induced by {a ₁, a ₂, b ₁, b ₂, c ₁, c ₂, d ₁, d ₂, x, y, z} such that b ₁, b ₂, c ₁, c ₂ ∈ B ² and x, z share no common white neighbor.

Let us denote A _x = W(x)∖{a ₁, a ₂} and A _z = W(z)∖{d ₁, d ₂}. For a ∈ A := A _x ∪ A _z, let K(a) denote the set of common black neighbors of a and y in B ² and not adjacent to any vertex of {x, b ₁, b ₂, c ₁, c ₂, z}. Note that A _x ∩ A _z = ∅ by the assumption. Since for every a ∈ A, K(a) ⊆ B ², K(a) ∩ K(a′) = ∅ for every pair of distinct vertices a, a′∈ A.

Consider a pair of distinct vertices b, b′∈ K(a) for some a ∈ A. If $b \nsim b'$, then {b, a, b′, y, c ₁, d ₁} induces a banner₂ in the case that a ∈ A _x (similar for the case a ∈ A _z), a contradiction. Hence, K(a) is a clique for all a ∈ A.

Now, let $V'(x) := \bigcup \limits _{a \in A_{x}}(K(a))$, $V'(z) := \bigcup \limits _{a \in A_{z}}(K(a))$, and $V' := V'(x) \cup V^{\prime }_{z}$. Note that, V ′(x) ∩ V ′(z) = ∅. Then a desired augmenting tree⁶ exists if and only if K(a) ≠ ∅ for every a ∈ A and α(G[V ′]) = |A|.

As in Lemma 10, we show that $G[V^{\prime }_{x}]$ and $G[V^{\prime }_{z}]$ are P ₅-free. Indeed, consider an induced P ₄ = (p ₁, p ₂, p ₃, p ₄) in $G[V^{\prime }_{x}]$ or $G[V^{\prime }_{z}]$, let a ∈ A be such that p ₁ ∈ K(a). Then none of the vertices p ₃, p ₄ is adjacent to a because K(a) is a clique. But now, p ₂ ∈ K(a), otherwise {b ₁, a ₁, x, a ₂, b ₂, a, p ₁, p ₂, p ₃, p ₄} or {c ₁, d ₁, z, d ₂, c ₂, a, p ₁, p ₂, p ₃, p ₄} induces an S _2,2,5 depending on a ∈ A _x or a ∈ A _z, a contradiction. Hence, if $G[V^{\prime }_{x}]$ or $G[V^{\prime }_{z}]$ induces a P ₄ = (p ₁, p ₂, p ₃, p ₄), then p ₁ and p ₂ have a common white neighbor, while p ₂ and p ₃ have no common white neighbor, a contradiction to when consider an induced P ₄ = (p ₂, p ₃, p ₄, p ₅) in the P ₅ = (p ₁, p ₂, p ₃, p ₄, p ₅).

Moreover, assume that there exists a pair of vertices b, b′ such that b ∈ K(a), b′∈ K(a′) for some a ∈ A(x), a′∈ A _z, and b ∼ b′. Then {b ₁, a ₁, x, a ₂, b ₂, a, b, b′, a′, z} induces an S _2,2,5, a contradiction. Hence, there is no edge connecting a vertex in $G[V^{\prime }_{x}]$ and a vertex in $G[V^{\prime }_{z}]$. So, G[V ′] is P ₅-free.

Note that all candidates can be found by an exhaustive search in time O(n ¹⁵). For such candidates, V ′ can be build in O(n ³). Hence, by the result of Lokshtanov et al. [22] we have the conclusion of the lemma.

Lemma 15

If G contains no augmenting P ₃ , nor P ₅ , nor P ₇ , then an augmenting tree ⁷ (if any) can be found in time O(n ¹⁹).

Proof

Refer to Figure 2 for indices. We may restrict ourselves to finding a tree⁷ with s ≥ 3, since a tree⁷ with s ≤ 2 is of the form tree³ or contains a redundant set U of size at most eight such that tree⁷ − U is of the form tree³.

As a candidate, consider the subgraph of tree⁷ (see Figure 2) induced by $\{x,a^{1}_{1},b^{1}_{1},$ $c_{1},d_{1},e_{1},f_{1},a^{2}_{1},b^{2}_{1},c_{2},d_{2},e_{2},f_{2},a^{3}_{1},b^{3}_{1},c_{3},d_{3},e_{3},f_{3}\}$ such that $b^{1}_{1},d_{1} \in B^{2}$ and f ₁ ∈ B ¹. Let us denote $A = W(x) \backslash \{a^{1}_{1},a^{2}_{1},a^{3}_{1},e_{1},e_{2},e_{3}\}$. For a ∈ A, let K(a) denote the set of black neighbors b of a in B ¹ ∪ B ² not adjacent to any vertex of $\{x,b^{1}_{1},d_{1},e_{1},f_{1},b^{2}_{1},d_{2},e_{2},f_{2},b^{3}_{1},$ d ₃, e ₃, f ₃} and such that if b ∈ B ², then G contains either

• two vertices c _b, d _b such that c _b∉W(x), W(b) = {a, c _b}, d _b ∈ B ¹, and d _b is not adjacent to any vertex of $\{x,b^{1}_{1},b^{2}_{1},b^{3}_{1},d_{1},d_{2},d_{3},f_{1},f_{2},f_{3},b\}$ or

• an induced alternating (black white vertices) P ₄ (c _b, d _b, e _b, f _b) such that $e_{b} \in W(x) \backslash \{a^{1}_{1},c_{1},a^{2}_{1},c_{2},a^{3}_{1},c_{3}\}$, c _b∉W(x), W(b) = {a, c _b}, W(d _b) = {c _b, e _b}, W(f _b) = {e _b}, and d _b, f _b are not adjacent to any vertex of $\{x,b^{1}_{1},b^{2}_{1},b^{3}_{1},d_{1},d_{2},$ d ₃, f ₁, f ₂, f ₃, b}.

Let $V' = \bigcup \limits _{a \in A}K(a)$.

By the existence of a desired augmenting tree⁷, K(a) is not empty for all a ∈ A. Note that, by assumption, K(a) ∩ K(a′) = ∅ for every pair of distinct vertices a, a′∈ A.

Given a vertex b ∈ K(a) ∩ B ² for some a ∈ A, we show that d _b∉K(e _b). Indeed, suppose that d _b∉K(e _b). Since d _b ∈ B ², $c_{b} = c_{d_{b}}$, $d_{d_{b}} = b$, and $e_{d_{b}} = a$. Hence, there exists some vertex b′∈ B ¹, such that $f_{d_{b}} = b'$, i.e. b′∼ a and b′ is not adjacent to b, d _b. Hence, $b' \nsim f_{b}$, otherwise $\{c_{b},b,a,b',f_{b},x,a^{i}_{1},b^{i}_{1},c_{i},d_{i}\}$ induces an S _2,2,5, for c _i is a vertex among c ₁, c ₂, c ₃ different from c _b, a contradiction. Now, {b′, a, b, c _b, d _b, e _b, f _b} induces an augmenting P ₇, a contradiction.

Suppose that there exist two vertices b, b′ such that b ∈ K(a) ∩ B ² and b′∈ K(a′) ∩ B ² for two distinct vertices a, a′∈ A and $d_{b},d_{b'}$ are different and adjacent to some vertex $a'' \in W(x) \backslash \{a,a',a^{1}_{1},a^{2}_{1},a^{3}_{1}\}$ different from a, a′. Then $\{c_{b},d_{b},a'',d_{b'},c_{b'},x,a^{i}_{1},b^{i}_{1},c_{i},d_{i}\}$ induces an S _2,2,5 where c _i is a vertex among c ₁, c ₂, c ₃ different from $c_{b},c_{b'}$, a contradiction. Hence, for every pair of vertices b, b′ such that b ∈ K(a) ∩ B ², b′∈ K(a′) ∩ B ² for two distinct vertices a, a′∈ A, $e_{b} \neq e_{b'}$.

Consider any vertex a ∈ A, we show that K(a) induces a clique. Indeed, suppose that K(a) contains two non-adjacent vertices b, b′. By the symmetry, we consider the three following cases.

Case 1. b, b′∈ B ¹. Then {b, a, b′} induces an augmenting P ₃, a contradiction.

Case 2. b′∈ B ¹ and b ∈ B ². We have the three following subcases.

2.1. d _b ∈ B ¹. Then {b′, a, b, c _b, d _b} induces an augmenting P ₅, a contradiction.

2.2. d _b ∈ B ² and $b' \nsim f_{b}$. Then {b′, a, b, c _b, d _b, e _b, f _b} induces an augmenting P ₇, a contradiction.

2.3. d _b ∈ B ² and b′∼ f _b. Then $\{f_{b},b',a,b,c_{b},x,a^{i}_{1},b^{i}_{1},c_{i},d_{i}\}$ induces an S _2,2,5, for c _i is a vertex among c ₁, c ₂, c ₃ different from c _b, a contradiction.

Case 3. b, b′∈ B ². Then $c_{b} \neq c_{b'}$, otherwise $\{b,c_{b},b',a,x,a^{1}_{1}\}$ induces a banner₂, a contradiction. Now, $\{c_{b'},b',a,b,c_{b},x,a^{i}_{1},b^{i}_{1},c_{i},d_{i}\}$ induces an S _2,2,5, for c _i is a vertex among c ₁, c ₂, c ₃ different from $c_{b},c_{b'}$, a contradiction.

It follows that a desired augmenting tree⁷ exists if and only if α(G[V ′]) = |A|.

Given a, a′∈ A, b ∈ K(a) ∩ B ², and b′∈ K(a′) such that $b \nsim b'$, if b′∼ d _b, then $b' \nsim c_{b}$, otherwise $c_{b'} = c_{b}$ and then $d_{b'} = d_{b}$, a contradiction. Then $\{b^{1}_{1},a^{1}_{1},x,a^{2}_{1},b^{2}_{1},a',b',d_{b},c_{b},$ b} induces an S _2,2,5, a contradiction. Now, if b′∈ B ², then $d_{b} \nsim d_{b'}$, otherwise $\{b^{i}_{1},a^{i}_{1},x,a^{j}_{1},$ $b^{j}_{1},a',b',c_{b'},d_{b'},d_{b}\}$ induces an S _2,2,5, for i, j ∈{1, 2, 3} such that c _b is different from c _i, c _j, a contradiction. Note that for every b ∈ K(a) ∩ B ² for some a ∈ A, f _b ∈ K(e _b). Hence, for every pair of non-adjacent vertices b, b′ such that b ∈ K(a) ∩ B ², b′∈ K(a′) for two distinc vertices a, a′∈ A, {b, b′, d _b, f _b} is independent. Moreover, if b′∈ B ², then $\{b,b',d_{b},d_{b'},f_{b},f_{b'}\}$ is independent.

Now, assume that B′ is a maximum independent set of G[V ′]. Let C′ := {c _b : b ∈ B′∩ B ²}, D′ := {d _b : b ∈ B′∩ B ²}. Then by above arguments, B′∪ D′ is independent. And in the case that |B′| = |A|, H := G[A ∪ B′∪ C′∪ D′] is an augmenting graph of the form tree⁷ of G. Hence, a maximum independent set of G[V ′] in the case that α(G[V ′]) = |A| gives us an augmenting of the form tree⁷.

As in Lemma 10, we show that G[V ′] is P ₅-free. Indeed, consider an induced P ₄ = (p ₁, p ₂, p ₃, p ₄) in G[V ′], and let a ∈ A be such that p ₁ ∈ K(a). Then none of the vertices p ₃, p ₄ is adjacent to a because K(a) is a clique. But now, p ₂ ∈ K(a), otherwise $\{b^{1}_{1},a^{1}_{1},x,a^{2}_{1},b^{2}_{1},a,p_{1},p_{2},p_{3},p_{4}\}$ induces an S _2,2,5, a contradiction. Hence, if G[V ′] induces a P ₄ = (p ₁, p ₂, p ₃, p ₄), then p ₁ and p ₂ have a common white neighbor, while p ₂ and p ₃ have no common white neighbor, a contradiction to when consider an induced P ₄ = (p ₂, p ₃, p ₄, p ₅) in the P ₅ = (p ₁, p ₂, p ₃, p ₄, p ₅).

All candidates can be found by an exhaustive search in time O(n ¹⁹). For such candidates, V ′ can be built in O(n ³). By the result of Lokshtanov et al. [22], we have the conclusion of the lemma.

Appendix 5: Proof of Theorem 5

So, we modify the concept of augmenting vertex [30] as follows.

Definition 4

Let S be an independent set of a graph G = (V, F) and v ∈ V ∖S, s ∈ N _S(v). We say that v is augmenting for S associated with s if G[N(s) ∩ H(v, S)] contains an independent set S _v,s such that |S _v,s|≥|N _S(v)|.

Moreover, with an addition assumption that a maximum independent set of G[N(s) ∩ H(v, S)] can be found in polynomial time for every s ∈ N _S(v), we can also choose s such that α(G[N(s) ∩ H(v, S)]) is maximum.

Algorithm 4 MISAugVer(G)

Refer to Algorithm 4, where p is a constant defined as in Lemma 3, an extended version of Algorithm Alpha in [29], a maximal independent set of G can be found (say by some greedy method) in time O(n ²). One can compute the set H(v, S) in time O(n ²). Note that an augmenting of at most 2m − 1 vertices can be found in time O(n ^2m+1). Moreover, by Lemmas 6, 10, …, 15, an augmenting graph of the forms mentioned in the while condition can be found in polynomial time. The while loop is repeated at most n time. Hence, we observe the following result, an extension of Theorem 7 in [29].

Lemma 16

Given two integers l and m, an (S _2,2,5 ,banner ₂ ,domino, $M_{m},R^{3}_{l},R^{4}_{l},$ $R^{5}_{l}$ )-free graph G = (V, E), a maximal independent set of G S, and v ∈ V ∖S, if one can find a maximum independent set of G[N(s) ∩ H(v, S)] for every s ∈ N _S(v) in polynomial time, then one can find a maximum independent set of G in polynomial time.

Let G = (V, E) be an (S _2,2,5,banner₂,domino,$M_{m},R^{3}_{l},R^{4}_{l},R^{5}_{l},K^{(h)}$)-free graph with n vertices and S be a maximal independent set of G. Assume that one can solve the MIS problem for (S _2,2,5,banner₂,domino,$M_{m},R^{3}_{l},R^{4}_{l},R^{5}_{l},K$)-free graphs in polynomial time. The goal is to show that one can carry out Step 2 of Algorithm 4 in polynomial time. We use the technique described in [30]. Let us say that a vertex v ∈ V  is a trivial augmenting vertex for S if v is augmenting for S and |N _S(v)|≤ h. Then one can check if a vertex v ∈ V  is a trivial augmenting vertex for S in time O(n ^h+1), by verifying if G[H(v, S)] contains an independent set S ^∗ of |N _S(v)| vertices. Such S ^∗ is called the independent set associated with the augmenting vertex v.

Assume that G admits no trivial augmenting vertex for S and that there exists v ∈ V ∖S augmenting for S (in particular, h < |N _S(v)|). Thus, G[H(v, S)] contains an independent set T with |N _S(v)|≤|T|. Since G is (S _2,2,5,banner₂,domino,M _m)-free together with an additional assumption that G contains no augmenting graph contains at most 2m − 1 vertices, no augmenting graph of the forms tree¹, …, tree⁷, no augmenting (4, p)-extended-chain, no augmenting apple, no augmenting graph that can be reduced to such forms by some redundant set or reduction set, by Lemmas 3 and 4, H′ := (T ∪{v}, N _S(v), E(H′)) is an augmenting bipartite-chain.

Let us write T = {t ₁, …, t _r} (r ≥|N _S(v)|≥ h), with N _S(t _i) ⊂ N _S(t _i+1) for any index i. Since G admits no trivial augmenting vertex for S, one has |N _S(t _k)|≥ k for k = 1, …, h. For any t ∈ H(v;S), let us write M(t) = {w ∈ H(v, S) : N _S(w) ⊃ N _S(t), |N _S(w)|≥ h}. Then T ⊂{t ₁, …, t _h}∪ (M(t _h)∖N({t ₁, …, t _h})). Note that M(t _h) is K-free, otherwise M(t _h) ∪{s ₁, s ₂, …, s _h}∪{v} induces a K ^(h) for s ₁, …, s _h ∈ N _S(t _h), a contradiction.

Now, since Step 2 of Algorithm 4 considers all the vertices in V ∖S, to check if S admits an augmenting vertex one has not to solve the MIS problem in H(v, S) for every v ∈ V ∖S. In fact, for every v ∈ V ∖S, it is sufficient to verify: (i) if v is a trivial augmenting vertex for S, and then (ii) if v is augmenting, by assuming that S admit no trivial augmenting vertex. That can be formalized by the procedure Algorithm 5 [30], whose input is any vertex v of V ∖S which can be executed in time O(n ^h+d+1).

Algorithm 5 Procedure Green (v)

Note that, given an augmenting vertex v (for S), Procedure Green(v) could not recognize it as an augmenting vertex: that can happen whenever H(v, S) contains a trivial augmenting vertex. Now, we give the new definition for augmenting vertex v as following.

Definition 5

Let S be an independent set of a graph G = (V, E), h be an integer, and v ∈ V ∖S, t ₁, t ₂, …, t _h ∈ H[v, S]. We say that v is h-augmenting for S associated with {t ₁, …, t _h}, where N _S(t _i) ⊂ N _S(t _i+1) for every index i, if G[M(t _h)∖N({t ₁, …, t _h})] contains an independent set $S_{v,t_{1},\ldots ,t_{h}}$ such that |S ^∗|≥|N _S(v)| where $S^{*} := S_{v,t_{1},\ldots ,t_{h}} \cup \{t_{1},t_{2},\ldots ,t_{h}\}$. S ^∗ is called the independent set associated with the augmenting vertex v.

To summarize, in order to define an efficient method to solve the MIS problem in (S _2,2,5,banner₂,domino,M _m, K ^(h))-free graphs, one can rewrite Step 2 of Algorithm 4 as in Algorithm 6.

Algorithm 6 New Step 6