Claw-free Graphs. V. Global structure

Maria Chudnovsky^{1} Columbia University, New York NY 10027

Paul Seymour^{2} Princeton University, Princeton NJ 08544

November 16, 2005; revised April 18, 2011

1This research was conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University.

2Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.

Abstract

A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In earlier papers of this series we proved that every claw-free graph either belongs to one of several basic classes that we described explicitly, or admits one of a few kinds of decomposition. In this paper we convert this “decomposition” theorem into a theorem describing the global structure of claw-free graphs.

1 Introduction

The main goal of this series of papers is to prove a theorem describing how to build the “most general” claw-free graph. In earlier papers, particularly in [4], we proved that every claw-free graph either belongs to one of a few basic classes that were we able to describe explicitly, or it admits one of a few kinds of decomposition. The decompositions all have inverses that are constructions producing larger claw-free graphs from smaller ones, so one might think we were done; the most general claw-free graph can be built by iterating these constructions, starting from graphs in our basic classes. But with care we can obtain a much more informative result. For instance, one of our constructions does not need to be iterated; it can be performed just in one round. A second only applies to very restricted classes of graphs, and for such graphs it is essentially the only construction needed. A third does need to be iterated, but the graphs that result from this process have a sort of generalized line graph structure and are better viewed in that light. Some of the constructions cannot be applied to graphs in some basic classes at all. The goal of this paper is to sort out all these issues.

2 Trigraphs

All graphs in this paper are finite and simple, that is, have no loops or parallel edges. As in earlier papers, it is helpful to work with “trigraphs” rather than with graphs. A trigraph G consists of a finite set V (G) of vertices, and a map θ_{G} : V (G)^{2} → {1, 0, −1}, satisfying:

• for all v ∈ V (G), θ_{G}(v, v) = 0

• for all distinct u, v ∈ V (G), θ_{G}(u, v) = θ_{G}(v, u)

• for all distinct u, v, w ∈ V (G), at most one of θ_{G}(u, v), θ_{G}(u, w) = 0.

We call θ_{G} the adjacency function of G. For distinct u, v in V (G), we say that u, v are strongly adjacent if θ_{G}(u, v) = 1, strongly antiadjacent if θ_{G}(u, v) = −1, and semiadjacent if θ_{G}(u, v) = 0. We say that u, v are adjacent if they are either strongly adjacent or semiadjacent, and antiadjacent if they are either strongly antiadjacent or semiadjacent. Also, we say u is adjacent to v and u is a neighbour of v if u, v are adjacent (and a strong neighbour if u, v are strongly adjacent); u is antiadjacent to v and u is an antineighbour of v if u, v are antiadjacent. We denote by F (G) the set of all pairs {u, v} such that u, v ∈ V (G) are distinct and semiadjacent. Thus a trigraph G is a graph if F (G) = ∅.

For a vertex a and a set B ⊆ V (G) \ {a}, we say that a is complete to B or B-complete if a is adjacent to every vertex in B; and that a is anticomplete to B or B-anticomplete if a has no neighbour in B. For two disjoint subsets A and B of V (G) we say that A is complete, respectively anticomplete, to B, if every vertex in A is complete, respectively anticomplete, to B. (We sometimes say A is B-complete, or the pair (A, B) is complete, meaning that A is complete to B.) Similarly, we say that a is strongly complete to B if a is strongly adjacent to every member of B, and so on.

Let G be a trigraph. A clique in G is a subset X ⊆ V (G) such that every two members of X are adjacent, and a strong clique is a subset such that every two of its members are strongly adjacent. A clique with cardinality three is a triangle. A set X ⊆ V (G) is stable if every two of its members are antiadjacent, and strongly stable if every two of its members are strongly antiadjacent. A triad in a trigraph G means a stable set with cardinality three.

We say a trigraph H is a thickening of a trigraph G if for every v ∈ V (G) there is a nonempty subset X_{v} ⊆ V (H), all pairwise disjoint and with union V (H), satisfying the following:

• for each v ∈ V (G), X_{v} is a strong clique of H

• if u, v ∈ V (G) are strongly adjacent in G then X_{u} is strongly complete to X_{v} in H

• if u, v ∈ V (G) are strongly antiadjacent in G then X_{u} is strongly anticomplete to X_{v} in H

• if u, v ∈ V (G) are semiadjacent in G then X_{u} is neither strongly complete nor strongly anticomplete to X_{v} in H.

If X ⊆ V (G), we define the trigraph G|X induced on X as follows. Its vertex set is X, and its adjacency function is the restriction of θ_{G} to X^{2}. We define G \ X = G|(V (G) \ X). Isomorphism for trigraphs is defined in the natural way, and if G, H are trigraphs, we say that G contains H and H is an induced subtrigraph of G if there exists X ⊆ V (G) such that H is isomorphic to G|X.

A claw is a trigraph with four vertices a_{0}, a_{1}, a_{2}, a_{3}, such that {a_{1}, a_{2}, a_{3}} is stable and a_{0} is complete to {a_{1}, a_{2}, a_{3}}. If X ⊆ V (G) and G|X is a claw, we often loosely say that X is a claw; and if no induced subtrigraph of G is a claw, we say that G is claw-free. It is easy to check that if H is a thickening of a claw-free trigraph G, then H is also claw-free.

Let us say a trigraph G is connected if there is no partition (V_{1}, V_{2}) of V (G) such that V_{1}, V_{2} ≠ ∅ and V_{1} is strongly anticomplete to V_{2}. To understand all claw-free trigraphs, it evidently suffices to understand those that are connected, because the others can be built from the connected ones by taking disjoint unions in the natural way. We find that connected claw-free trigraphs fall naturally into three classes:

• those that admit a partition of their vertex set into three strong cliques

• those that admit a “nontrivial strip-structure” (defined later), and

• those for which neither of the above holds.

We shall see that for each of the three classes, the trigraphs in that class can be built starting from certain basic trigraphs and piecing them together by means of certain operations; but the basic trigraphs and the operations are different for the three classes, and it is most convenient to treat the three classes separately. Our characterization for the first class is given in 4.1, and for the second and third in 7.2, but let us state rudimentary versions of those results now. What follows is somewhat vague, because we are postponing a number of important definitions, but we hope that it will give the reader a better idea of the goal of this paper. Here is a construction.

• Start with a trigraph G_{0} that is a disjoint union of strong cliques. Take a partition of V (G_{0}) into strongly stable sets X_{1}, …, X_{k}, such that each X_{i} satisfies 1 ≤ |X_{i}| ≤ 2.

• For 1 ≤ i ≤ k, take a trigraph G_{i} (where G_{0}, G_{1}, …, G_{k} are pairwise vertex-disjoint) and a subset Y_{i} ⊆ V (G_{i}) with |Y_{i}| = |X_{i}|. (When we apply this, the pairs (G_{i}, Y_{i}) will be taken from an explicit list of allowed pairs. In particular, G_{i} is claw-free, Y_{i} is strongly stable in G_{i}, and for each vertex in Y_{i}, its neighbour set in G_{i} is a strong clique.) Take the disjoint union of G_{0}, …, G_{k}.

• For 1 ≤ i ≤ k, take a bijection between X_{i} and Y_{i}; and for each x ∈ X_{i} and its mate y ∈ Y_{i}, make the neighbour set of x strongly complete to the neighbour set of y, and then delete x, y. (The order of these operations does not affect the final outcome.)

Then we can state the essentials of our main theorems as follows. (We leave the reader to check that this follows from the full versions 7.2 and 4.1.)

2.1 For every connected claw-free trigraph G, one of the following holds:

• G can be constructed as above, where all the pairs (G_{i}, Y_{i}) are taken from an explicit list described later in the paper (either G_{i} is a three-vertex path and Y_{i} consists of its two ends, or (G_{i}, Y_{i}) is a so-called thickening of a member of one of Z_{1}, …, Z_{15})

• G belongs to one of three classes (the thickenings of members of S_{1}, S_{3}, S_{7}) described explicitly later

• the vertex set of G can be partitioned into three strong cliques. If so, then G can be expressed as a sequence of disjoint pieces, where the adjacency between pieces is specified by a rule given later, and each piece belongs to one of five classes (the thickenings of permutations of members of T C_{1}, …, T C_{5}) described explicitly later.

3 Some trigraphs

Here are some types of trigraphs that will be important for us. These constitute most of the building blocks that we need for the results just mentioned (it is convenient to collect them in one place, although we shall not need them all immediately.)

• Line trigraphs. Let H be a graph, and let G be a trigraph with V (G) = E(H). We say that G is a line trigraph of H if for all distinct e, f ∈ E(H):

– if e, f have a common end in H then they are adjacent in G, and if they have a common end of degree at least three in H, then they are strongly adjacent in G

– if e, f have no common end in H then they are strongly antiadjacent in G.

We say that G ∈ S_{0} if G is isomorphic to a line trigraph of some graph. It is easy to check that any line trigraph is claw-free.

• Trigraphs from the icosahedron. The icosahedron is the unique planar graph with twelve vertices all of degree five. Let it have vertices v_{0}, v_{1}, …, v_{11}, where for 1 ≤ i ≤ 10, v_{i} is adjacent to v_{i+1}, v_{i+2} (reading subscripts modulo 10), and v_{0} is adjacent to v_{1}, v_{3}, v_{5}, v_{7}, v_{9}, and v_{11} is adjacent to v_{2}, v_{4}, v_{6}, v_{8}, v_{10}. Let this graph be G_{0}, regarded as a trigraph (so no pairs are semiadjacent in G_{0}). Let G_{1} be obtained from G_{0} by deleting v_{11}. Let G_{2} be obtained from G_{1} by deleting v_{10}, and possibly making v_{1} semiadjacent to v_{4} or making v_{6} semiadjacent to v_{9} (or both). All these trigraphs (G_{0}, G_{1} and the several possibilities for G_{2} are claw-free); let S_{1} be the class of all such trigraphs.

• The trigraphs S_{2}. Let H be the trigraph with vertex set {v_{1}, …, v_{13}}, with adjacency as follows. v_{1}- ⋯ -v_{6}-v_{1} is a hole in G of length 6. Next, v_{7} is adjacent to v_{1}, v_{2}; v_{8} is adjacent to v_{4}, v_{5} and possibly to v_{7}; v_{9} is adjacent to v_{6}, v_{1}, v_{2}, v_{3}; v_{10} is adjacent to v_{3}, v_{4}, v_{5}, v_{6}, v_{9}; v_{11} is adjacent to v_{3}, v_{4}, v_{6}, v_{1}, v_{9}, v_{10}; v_{12} is adjacent to v_{2}, v_{3}, v_{5}, v_{6}, v_{9}, v_{10}; and v_{13} is adjacent to v_{1}, v_{2}, v_{4}, v_{5}, v_{7}, v_{8}. No other pairs are adjacent, and all adjacent pairs are strongly adjacent except possibly for v_{7}, v_{8} and v_{9}, v_{10}. (Thus the pair v_{7}v_{8} may be strongly adjacent, semiadjacent or strongly antiadjacent; the pair v_{9}v_{10} is either strongly adjacent or semiadjacent.) We say G ∈ S_{2} if G is isomorphic to H \ X, where X ⊆ {v_{7}, v_{11}, v_{12}, v_{13}}.

• Long circular interval trigraphs. Let Σ be a circle, and let F_{1}, …, F_{k} ⊆ Σ be homeomorphic to the interval [0, 1], such that no two of F_{1}, …, F_{k} share an end-point, and no three of them have union Σ. Now let V ⊆ Σ be finite, and let G be a trigraph with vertex set V in which, for distinct u, v ∈ V,

– if u, v ∈ F_{i} for some i then u, v are adjacent, and if also at least one of u, v belongs to the interior of F_{i} then u, v are strongly adjacent

– if there is no i such that u, v ∈ F_{i} then u, v are strongly antiadjacent.

Such a trigraph G is called a long circular interval trigraph. We write G ∈ S_{3} if G is a long circular interval trigraph.

• Modifications of L(K_{6}). Let H be a graph with seven vertices h_{1}, …, h_{7}, in which h_{7} is adjacent to h_{6} and to no other vertex, h_{6} is adjacent to at least three of h_{1}, …, h_{5}, and there is a cycle with vertices h_{1}-h_{2}- ⋯ -h_{5}-h_{1} in order. Let J(H) be the graph obtained from the line graph of H by adding one new vertex, adjacent precisely to those members of E(H) that are not incident with h_{6} in H. Then J(H) is a claw-free graph. Let G be either J(H) (regarded as a trigraph), or (in the case when h_{4}, h_{5} both have degree two in H), the trigraph obtained from J(H) by making the vertices h_{3}h_{4}, h_{1}h_{5} ∈ V (J(H)) semiadjacent. Let S_{4} be the class of all such trigraphs G.

• The trigraphs S_{5}. Let n ≥ 2. Construct a trigraph G as follows. Its vertex set is the disjoint union of four sets A, B, C and {d_{1}, …, d_{5}}, where |A| = |B| = |C| = n, say A = {a_{1}, …, a_{n}}, B = {b_{1}, …, b_{n}} and C = {c_{1}, …, c_{n}}. Let X ⊆ A ∪ B ∪ C with |X ∩ A|, |X ∩ B|, |X ∩ C| ≤ 1. Adjacency is as follows: A, B, C are strong cliques; for 1 ≤ i, j ≤ n, a_{i}, b_{j} are adjacent if and only if i = j, and c_{i} is strongly adjacent to a_{j} if and only if i ≠ j, and c_{i} is strongly adjacent to b_{j} if and only if i ≠ j. Moreover

– a_{i} is semiadjacent to c_{i} for at most one value of i ∈ {1, …, n}, and if so then b_{i} ∈ X

– b_{i} is semiadjacent to c_{i} for at most one value of i ∈ {1, …, n}, and if so then a_{i} ∈ X

– a_{i} is semiadjacent to b_{i} for at most one value of i ∈ {1, …, n}, and if so then c_{i} ∈ X

– no two of A \ X, B \ X, C \ X are strongly complete to each other.

Also, d_{1} is strongly A∪B∪C-complete; d_{2} is strongly complete to A∪B, and either semiadjacent or strongly adjacent to d_{1}; d_{3} is strongly complete to A ∪ {d_{2}}; d_{4} is strongly complete to B ∪ {d_{2}, d_{3}}; d_{5} is strongly adjacent to d_{3}, d_{4}; and all other pairs are strongly antiadjacent. Let the trigraph just constructed be G, and let H = G|(V (G) \ X). Then H is claw-free; let S_{5} be the class of all such trigraphs H.

• Near-antiprismatic trigraphs. Let n ≥ 2. Construct a trigraph H as follows. Its vertex set is the disjoint union of three sets A, B, C, where |A| = |B| = n + 1 and |C| = n, say A = {a_{0}, a_{1}, …, a_{n}}, B = {b_{0}, b_{1}, …, b_{n}} and C = {c_{1}, …, c_{n}}. Adjacency is as follows. A, B, C are strong cliques. For 0 ≤ i, j ≤ n with (i, j) ≠ (0, 0), let a_{i}, b_{j} be adjacent if and only if i = j, and for 1 ≤ i ≤ n and 0 ≤ j ≤ n let c_{i} be adjacent to a_{j}, b_{j} if and only if i ≠ j ≠ 0. a_{0}, b_{0} may be semiadjacent or strongly antiadjacent. All other pairs not specified so far are strongly antiadjacent. Now let X ⊆ A ∪ B ∪ C \ {a_{0}, b_{0}} with |C \ X| ≥ 2. Let all adjacent pairs be strongly adjacent except:

– a_{i} is semiadjacent to c_{i} for at most one value of i ∈ {1, …, n}, and if so then b_{i} ∈ X

– b_{i} is semiadjacent to c_{i} for at most one value of i ∈ {1, …, n}, and if so then a_{i} ∈ X

– a_{i} is semiadjacent to b_{i} for at most one value of i ∈ {1, …, n}, and if so then c_{i} ∈ X

Let the trigraph just constructed be H, and let G = H \ X. Then G is claw-free; let S_{6} be the class of all such trigraphs G. We call such a trigraph G near-antiprismatic.

• Antiprismatic trigraphs. Let us say a trigraph is antiprismatic if for every X ⊆ V (G) with |X| = 4, X is not a claw and there are at least two pairs of vertices in X that are strongly adjacent. If G is a trigraph, let H be the graph with vertex set V (G) in which vertices are adjacent in H if and only if they are antiadjacent in G; then G is antiprismatic if and only if H is what we called a “prismatic” graph in [1, 2] and every semiadjacent pair of vertices of G is what we called a “changeable” edge of H. (See those papers for a definition of “prismatic” and “changeable”.) In these two papers we listed all prismatic graphs and all ways in which an edge of such a graph can be changeable, and so that provides a description of all antiprismatic trigraphs. Let S_{7} be the class of all antiprismatic trigraphs.

4 Three strong cliques

As we said, we plan to tackle the three classes of connected claw-free trigraphs separately; and first we handle the trigraphs G such that V (G) can be partitioned into three strong cliques. A three-cliqued trigraph (G, A, B, C) consists of a trigraph G and three strong cliques A, B, C of G, pairwise disjoint and with union V (G). If G is also claw-free we say that (G, A, B, C) is a three-cliqued claw-free trigraph.

If (G, A, B, C) is a three-cliqued trigraph, and H is a thickening of G, let X_{v} (v ∈ V (G)) be the corresponding strong cliques of H; then ∪_{v∈A}X_{v} is a strong clique A′ say of H, and if we define B′, C′ from B, C similarly, then (H, A′, B′, C′) is a three-cliqued trigraph, that we say is a thickening of (G, A, B, C).

Let n ≥ 0, and for 1 ≤ i ≤ n, let (G_{i}, A_{i}, B_{i}, C_{i}) be a three-cliqued trigraph, where V (G_{1}), …, V (G_{n}) are all nonempty and pairwise vertex-disjoint. Let A = A_{1} ∪ ⋯ ∪ A_{n}, B = B_{1} ∪ ⋯ ∪ B_{n}, and C = C_{1} ∪ ⋯ ∪ C_{n}, and let G be the trigraph with vertex set V (G_{1}) ∪ ⋯ ∪ V (G_{n}) and with adjacency as follows:

• for 1 ≤ i ≤ n, G|V (G_{i}) = G_{i};

• for 1 ≤ i < j ≤ n, A_{i} is strongly complete to V (G_{j})\B_{j}; B_{i} is strongly complete to V (G_{j})\C_{j}; and C_{i} is strongly complete to V (G_{j}) \ A_{j}; and • for 1 ≤ i < j ≤ n, if u ∈ A_{i} and v ∈ B_{j} are adjacent then u, v are both in no triads; and the

same applies if u ∈ B_{i} and v ∈ C_{j}, and if u ∈ C_{i} and v ∈ A_{j}.

In particular, A, B, C are strong cliques, and so (G, A, B, C) is a three-cliqued trigraph; we call the sequence (G_{i}, A_{i}, B_{i}, C_{i}) (i = 1, …, n) a worn hex-chain for (G, A, B, C). When n = 2 we say that (G, A, B, C) is a worn hex-join of (G_{1}, A_{1}, B_{1}, C_{1}) and (G_{2}, A_{2}, B_{2}, C_{2}). Note also that every triad of G is a triad of one of G_{1}, …, G_{n}, and if each G_{i} is claw-free then so is G. If we replace the third condition above by the strengthening

• for 1 ≤ i < j ≤ n, the pairs (A_{i}, B_{j}), (B_{i}, C_{j}) and (C_{i}, A_{j}) are strongly anticomplete

we call the sequence a hex-chain for (G, A, B, C); and if n = 2, (G, A, B, C) is a hex-join of (G_{1}, A_{1}, B_{1}, C_{1}) and (G_{2}, A_{2}, B_{2}, C_{2}).

Here are some examples of three-cliqued claw-free trigraphs.

• A type of line trigraph. Let v_{1}, v_{2}, v_{3} be distinct nonadjacent vertices of a graph H, such that every edge of H is incident with one of v_{1}, v_{2}, v_{3}. Let v_{1}, v_{2}, v_{3} all have degree at least three, and let all other vertices of H have degree at least one. Moreover, for all distinct i, j ∈ {1, 2, 3}, let there be at most one vertex different from v_{1}, v_{2}, v_{3} that is adjacent to v_{i} and not to v_{j} in H. Let A, B, C be the sets of edges of H incident with v_{1}, v_{2}, v_{3} respectively, and let G be a line trigraph of H. Then (G, A, B, C) is a three-cliqued claw-free trigraph; let T C_{1} be the class of all such three-cliqued trigraphs such that every vertex is in a triad.

• Long circular interval trigraphs. Let G be a long circular interval trigraph, and let Σ be a circle with V (G) ⊆ Σ, and F_{1}, …, F_{k} ⊆ Σ, as in the definition of long circular interval trigraph. By a line we mean either a subset X ⊆ V (G) with |X| ≤ 1 , or a subset of some F_{i} homeomorphic to the closed unit interval, with both end-points in V (G). Let L_{1}, L_{2}, L_{3} be pairwise disjoint lines with V (G) ⊆ L_{1} ∪ L_{2} ∪ L_{3}; then (G, V (G) ∩ L_{1}, V (G) ∩ L_{2}, V (G) ∩ L_{3}) is a three-cliqued claw-free trigraph. We denote by T C_{2} the class of such three-cliqued trigraphs with the additional property that every vertex is in a triad.

• Near-antiprismatic trigraphs. Let H be a near-antiprismatic trigraph, and let A, B, C, X be as in the definition of near-antiprismatic trigraph. Let A′ = A \ X and define B′, C′ similarly; then (H, A′, B′, C′) is a three-cliqued claw-free trigraph. We denote by T C_{3} the class of all three-cliqued trigraphs with the additional property that every vertex is in a triad.

• Antiprismatic trigraphs. Let G be an antiprismatic trigraph and let A, B, C be a partition of V (G) into three strong cliques; then (G, A, B, C) is a three-cliqued claw-free trigraph. We denote the class of all such three-cliqued trigraphs by T C_{4}. (In [1] we described explicitly all three-cliqued antiprismatic graphs, and their “changeable” edges; and this therefore provides a description of the three-cliqued antiprismatic trigraphs.) Note that in this case there may be vertices that are in no triads.

• Sporadic exceptions.

– Let H be the trigraph with vertex set {v_{1}, …, v_{8}} and adjacency as follows: v_{i}, v_{j} are strongly adjacent for 1 ≤ i < j ≤ 6 with j − i ≤ 2; the pairs v_{1}v_{5} and v_{2}v_{6} are strongly antiadjacent; v_{1}, v_{6}, v_{7} are pairwise strongly adjacent, and v_{7} is strongly antiadjacent to v_{2}, v_{3}, v_{4}, v_{5}; v_{7}, v_{8} are strongly adjacent, and v_{8} is strongly antiadjacent to v_{1}, …, v_{6}; the pairs v_{1}v_{4} and v_{3}v_{6} are semiadjacent, and v_{2} is antiadjacent to v_{5}. Let A = {v_{1}, v_{2}, v_{3}}, B = {v_{4}, v_{5}, v_{6}} and C = {v_{7}, v_{8}}. Let X ⊆ {v_{3}, v_{4}}; then (H \ X, A \ X, B \ X, C) is a three-cliqued claw-free trigraph, and all its vertices are in triads.

– Let H be the trigraph with vertex set {v_{1}, …, v_{9}}, and adjacency as follows: the sets A = {v_{1}, v_{2}}, B = {v_{3}, v_{4}, v_{5}, v_{6}, v_{9}} and C = {v_{7}, v_{8}} are strong cliques; v_{9} is strongly adjacent to v_{1}, v_{8} and strongly antiadjacent to v_{2}, v_{7}; v_{1} is strongly antiadjacent to v_{4}, v_{5}, v_{6}, v_{7}, semiadjacent to v_{3} and strongly adjacent to v_{8}; v_{2} is strongly antiadjacent to v_{5}, v_{6}, v_{7}, v_{8} and strongly adjacent to v_{3}; v_{3}, v_{4} are strongly antiadjacent to v_{7}, v_{8}; v_{5} is strongly antiadjacent to v_{8}; v_{6} is semiadjacent to v_{8} and strongly adjacent to v_{7}; and the adjacency between the pairs v_{2}v_{4} and v_{5}v_{7} is arbitrary. Let X ⊆ {v_{3}, v_{4}, v_{5}, v_{6}}, such that

∗ v_{2} is not strongly anticomplete to {v_{3}, v_{4}} \ X

∗ v_{7} is not strongly anticomplete to {v_{5}, v_{6}} \ X

∗ if v_{4}, v_{5} ∉ X then v_{2} is adjacent to v_{4} and v_{5} is adjacent to v_{7}.

Then (H \ X, A, B \ X, C) is a three-cliqued claw-free trigraph.

We denote by T C_{5} the class of such three-cliqued trigraphs (given by one of these two constructions) with the additional property that every vertex is in a triad.

If (G, A, B, C) is a three-cliqued trigraph, and {A′, B′, C′} = {A, B, C}, then (G, A′, B′, C′) is also a three-cliqued trigraph, that we say is a permutation of (G, A, B, C). Now we can state our theorem about three-cliqued claw-free trigraphs.

4.1 Every three-cliqued claw-free trigraph admits a worn hex-chain into terms each of which is a thickening of a permutation of a member of one of T C_{1}, …, T C_{5}.

5 Decompositions

Our next goal is the proof of 4.1, in the section following this. The main part of the proof is an application of the decomposition theorem of [4], and before we can apply that we need to state it precisely, and in particular to describe the decompositions that it uses; and that is the purpose of this section.

Two strongly adjacent vertices of a trigraph G are called twins if (apart from each other) they have the same neighbours in G, and the same antineighbours, and if there are two such vertices, we say “G admits twins”. If X ⊆ V (G) is a strong clique and every vertex in V (G)\X is either strongly complete or strongly anticomplete to X, we call X a homogeneous set. Thus, G admits twins if and only if some homogeneous set has more than one member.

Let A, B be disjoint subsets of V (G). The pair (A, B) is called a homogeneous pair in G if A, B are strong cliques, and for every vertex v ∈ V (G) \ (A ∪ B), v is either strongly A-complete or strongly A-anticomplete and either strongly B-complete or strongly B-anticomplete. Let (A, B) be a homogeneous pair, such that A is neither strongly complete nor strongly anticomplete to B, and at least one of A, B has at least two members. In these circumstances we call (A, B) a W-join.

Next, suppose that V_{1}, V_{2} is a partition of V (G) such that V_{1}, V_{2} are nonempty and V_{1} is strongly anticomplete to V_{2}. We call the pair (V_{1}, V_{2}) a 0-join in G. Thus, G admits a 0-join if and only if it is not connected.

Next, suppose that V_{1}, V_{2} is a partition of V (G), and for i = 1, 2 there is a subset A_{i} ⊆ V_{i} such that:

• A_{i}, V_{i} \ A_{i} ≠ ∅ for i = 1, 2

• A_{1} ∪ A_{2} is a strong clique, and

• V_{1} \ A_{1} is strongly anticomplete to V_{2}, and V_{1} is strongly anticomplete to V_{2} \ A_{2}.

In these circumstances, we say that (V_{1}, V_{2}) is a 1-join.

Next, suppose that V_{0}, V_{1}, V_{2} are disjoint subsets with union V (G), and for i = 1, 2 there are subsets A_{i}, B_{i} of V_{i} satisfying the following:

• V_{0} ∪A_{1} ∪A_{2} and V_{0} ∪B_{1} ∪B_{2} are strong cliques, and V_{0} is strongly anticomplete to V_{i} \(A_{i} ∪B_{i}) for i = 1, 2;

• for i = 1, 2, A_{i} ∩ B_{i} = ∅ and A_{i}, B_{i} and V_{i} \ (A_{i} ∪ B_{i}) are all nonempty; and

• for all v_{1} ∈ V_{1} and v_{2} ∈ V_{2}, either v_{1} is strongly antiadjacent to v_{2}, or v_{1} ∈ A_{1} and v_{2} ∈ A_{2}, or v_{1} ∈ B_{1} and v_{2} ∈ B_{2}.

We call the triple (V_{0}, V_{1}, V_{2}) a generalized 2-join, and if V_{0} = ∅ we call the pair (V_{1}, V_{2}) a 2-join.

Finally, we say that G admits a hex-join if there are three strong cliques A, B, C such that (G, A, B, C) is a three-cliqued trigraph that is expressible as a hex-join. Let us say that a trigraph G is indecomposable if it does not admit twins, a W-join, a 0-join, a 1-join, a generalized 2-join, or a hex-join. (In [4] we were careful only to use “nondominating” W-joins, but now it no longer matters.) The main theorem of [4] is the following.

5.1 Every indecomposable claw-free trigraph belongs to S_{0} ∪ ⋯ ∪ S_{7}.

We shall also need the following theorem of [4].

5.2 Let G be claw-free, and let B_{1}, B_{2}, B_{3} be strong cliques in G. Let B = B_{1} ∪ B_{2} ∪ B_{3}. Suppose that:

• B ≠ V (G),

• there are two triads T_{1}, T_{2} ⊆ B with |T_{1} ∩ T_{2}| = 2, and

• there is no triad T in G with |T ∩ B| = 2.

Then either

• there exists V ⊆ B with T_{1}, T_{2} ⊆ V such that V is a union of triads, and G is a hex-join of G|V and G|(V (G) \ V), where (V ∩ B_{1}, V ∩ B_{2}, V ∩ B_{3}) is the corresponding partition of V into strong cliques, or

• there is a homogeneous set with at least two members, included in one of B_{1}, B_{2}, B_{3}, such that all its members are in triads, or

• there is a homogeneous pair (V_{1}, V_{2}) with max(|V_{1}|, |V_{2}|) ≥ 2, such that V_{1} is a subset of one of B_{1}, B_{2}, B_{3} and V_{2} is a subset of another.

6 Proof of the three-cliques result

We need several lemmas. First, we observe:

6.1 Let G be a trigraph.

• Let u, v ∈ V (G) be twins. If G\{u} is a thickening of a trigraph H, then G is also a thickening of H. If (G, A, B, C) is a three-cliqued graph and u, v belong to the same member of A, B, C, say A, and (G \ {u}, A \ {u}, B, C) is a thickening of a three-cliqued trigraph, then (G, A, B, C) is a thickening of the same three-cliqued trigraph.

• Let (P, Q) be a W-join, let p ∈ P and q ∈ Q, and let G′ be obtained from G by deleting (P \ {p}) ∪ (Q \ {q}) and making p, q semiadjacent. If G′ is a thickening of some trigraph H, then G is also a thickening of H. If (G, A, B, C) is a three-cliqued trigraph and P ⊆ A and Q ⊆ B, and (G′, A \ (P \ {p}), B \ (Q \ {q}), C) is a thickening of a three-cliqued trigraph, then (G, A, B, C) is a thickening of the same three-cliqued trigraph.

• If (G, A, B, C) is a three-cliqued trigraph expressible as a worn hex-join of (G_{i}, A_{i}, B_{i}, C_{i}) for i = 1, 2, and for i = 1, 2, (G_{i}, A_{i}, B_{i}, C_{i}) admits a worn hex-chain with all terms in some class C, then (G, A, B, C) also admits a worn hex-chain with all terms in C.

Proof. For the first statement, note that since u, v are twins, it follows that no vertex is semiadjacent to v. Now suppose that G \ {u} is a thickening of H, and let X_{w} (w ∈ V (H)) be the corresponding partition of V (G \ {u}) into strong cliques. Let v ∈ X_{w} say. Then X_{w} ∪ {u} is a strong clique of G, and if we replace X_{w} by X_{w} ∪ {u}, the partition of V (G) we obtain shows that G is a thickening of H. The statement for three-cliqued trigraphs follows similarly.

For the second statement, G′ is a thickening of H; let X_{w} (w ∈ V (H)) be the corresponding partition of V (G′). Since p, q are semiadjacent in G′, they do not belong to the same clique; say p ∈ X_{u} and q ∈ X_{v}. Since X_{u}, X_{v} are neither strongly complete nor strongly anticomplete, it follows that u, v are semiadjacent in H. If we replace X_{u}, X_{v} by (X_{u}\{p})∪P and (X_{v} \{q})∪Q respectively, the partition of V (G) we obtain shows that G is a thickening of H. The statement for three-cliqued trigraphs follows similarly.

For the third statement, by hypothesis for i = 1, 2 (G_{i}, A_{i}, B_{i}, C_{i}) admits a worn hex-chain with all terms in C; and the concatenation of the two corresponding sequences is a worn hex-chain of (G, A, B, C) with all terms in C. This proves 6.1.

6.2 Let (G, A, B, C) be a three-cliqued claw-free trigraph, and suppose that G admits a 0-, 1- or generalized 2-join, and does not admit a hex-join, and every vertex of G belongs to a triad. Then (G, A, B, C) is a permutation of a thickening of a member of T C_{1} ∪ T C_{2} ∪ T C_{3} ∪ T C_{5}.

Proof. Suppose G admits a 0-join (V_{1}, V_{2}) say. Thus V_{1}, V_{2} ≠ ∅, V_{1} ∩ V_{2} = ∅, V_{1} ∪ V_{2} = V (G), and V_{1} is strongly anticomplete to V_{2}. Since each of A, B, C is a strong clique, each is a subset of one of V_{1}, V_{2}, so we may assume that V_{1} = A ∪ B and V_{2} = C. If A, B ≠ ∅, G is a thickening of the trigraph H with three vertices a, b, c, in which a, b are antiadjacent and c is strongly antiadjacent to both a, b. Since (H, {a}, {b}, {c}) ∈ T C_{2}, in this case the claim holds. If say B = ∅, then A = V_{1} is a nonempty strong clique, and now G is a thickening of a two-vertex trigraph, and again the theorem holds.

Next, suppose that G admits a 1-join and no 0-join, and let V (G) be the union of the four disjoint nonempty sets Y_{1}, Y_{2}, Z_{1}, Z_{2}, where Z_{1} ∪ Z_{2} is a strong clique, and Y_{1} is strongly anticomplete to Y_{2} ∪ Z_{2}, and Y_{2} is strongly anticomplete to Y_{1} ∪ Z_{1}. Since Y_{1}, Y_{2} ≠ ∅, we may assume that A ∩ Y_{1}, C ∩ Y_{2} ≠ ∅, and so A ⊆ Y_{1} ∪ Z_{1} and C ⊆ Y_{2} ∪ Z_{2}. Suppose that B ∩ Y_{1} ≠ ∅. Then also B ⊆ Y_{1}∪Z_{1}, and so Y_{2}∪Z_{2} = C. Let A′ be the set of vertices in A∩Y_{1} with a neighbour in B∩Z_{1}, and let B′ be the set of vertices in B ∩ Y_{1} with a neighbour in A ∩ Z_{1}. Since (B ∩ Z_{1}) ∪ Z_{2} ∪ A′ ∪ (B ∩ Y_{1}) includes no claw, it follows that A′ is strongly complete to B ∩ Y_{1}, and similarly B′ is strongly complete to A ∩ Y_{1}. If A ∩ Z_{1} = ∅, then B′ = ∅ and (G, A, B, C) is a thickening of a member of T C_{2} with at most six vertices, so we may assume that A ∩ Z_{1} and similarly B ∩ Z_{1} are nonempty. Since the members of Z_{2} belong to triads, it follows that A ∩ Y_{1} is not strongly complete to B ∩ Y_{1}. But then (G, A, B, C) is a thickening of a member of T C_{5}. This completes the argument when B ∩Y_{1} ≠ ∅, and so we may assume that B ⊆ Z_{1} ∪Z_{2}. Hence Y_{1} ⊆ A and Y_{2} ⊆ C; and (G, A, B, C) is a thickening of a member of T C_{2} with at most six vertices.

Now suppose that G admits a generalized 2-join and no 0- or 1-join. Let V_{0}, V_{1}, V_{2} be disjoint subsets with union V (G) as in the definition of 2-join, choosing them with V_{0} nonempty if possible. For i = 1, 2, let V_{i} be the union of the three disjoint nonempty sets X_{i}, Y_{i}, Z_{i}, where X_{1} is strongly complete to X_{2}, and Y_{1} to Y_{2}, and otherwise V_{1} is strongly anticomplete to V_{2}; and V_{0} is strongly complete to X_{1}, X_{2}, Y_{1}, Y_{2} and strongly anticomplete to Z_{1}, Z_{2}.

(1) If one of A, B, C has nonempty intersection with both V_{1}, V_{2} then the theorem holds.

For suppose that B intersects both V_{1}, V_{2} say. It follows that B is a subset of one of X_{1} ∪ X_{2} ∪ V_{0}, Y_{1} ∪ Y_{2} ∪ V_{0}, and we may assume the first from the symmetry. Since Z_{1}, Z_{2} are both nonempty, and are strongly anticomplete, we may assume that Z_{1} ⊆ A and Z_{2} ⊆ C. Hence every vertex in (X_{1} ∪ X_{2} ∪ V_{0}) \ B is strongly complete to B, and since every vertex is in a triad it follows that B = X_{1} ∪ X_{2} ∪ V_{0}, and therefore A = Y_{1} ∪ Z_{1} and C = Y_{2} ∪ Z_{2}. For i = 1, 2, every vertex in X_{i} with a neighbour in Y_{i} is strongly complete to Z_{i}, since otherwise Y_{i} ∪ X_{i} ∪ Z_{i} ∪ Y_{3−i} includes a claw. Moreover, Z_{1} is not strongly anticomplete to X_{1} since G does not admit a 1-join; and similarly Z_{2} is not strongly anticomplete to X_{2}. For i = 1, 2, no vertex in X_{i} is strongly complete to Y_{i} since every vertex in X_{i} is in a triad. Consequently if V_{0} = ∅ then (G, A, B, C) is a thickening of a member of T C_{2}, and if V_{0} ≠ ∅ then (G, A, B, C) is a thickening of a member of T C_{5}. This proves (1).

In view of (1) we may assume that A, B ⊆ V_{0} ∪ V_{1}, and so V_{2} ⊆ C. Since Z_{2} ≠ ∅ and every vertex of V_{0} ∪V_{1} is strongly anticomplete to Z_{2}, it follows that C = V_{2}, and therefore A∪B = V_{0} ∪V_{1}.

(2) If A ∩ Z_{1} is strongly anticomplete to B \ Z_{1}, and B ∩ Z_{1} is strongly anticomplete to A \ Z_{1}, then the theorem holds.

For since Z_{1} ≠ ∅, we may assume that A ∩ Z_{1} ≠ ∅. Since

(Y_{1} ∩ A) ∪ (Z_{1} ∩ A) ∪ (X_{1} ∩ B) ∪ Y_{2}

includes no claw, it follows that Y_{1} ∩ A is strongly anticomplete to X_{1} ∩ B, and similarly X_{1} ∩ A is strongly anticomplete to Y_{1} ∩ B. Since A ∩ Z_{1} ≠ ∅ it follows that A ∩ V_{0} = ∅, and so V_{0} ⊆ B. If V_{0} ≠ ∅, then B ∩ Z_{1} = ∅, and Z_{1} ⊆ A, and so (G, A, C, B) is a thickening of a member of T C_{3}. On the other hand, if V_{0} = ∅, then (G, A, B, C) is a thickening of a member of T C_{1}. This proves (2).

(3) Let b ∈ B ∩ Z_{1}. Then

• V_{0} ⊆ A;

• if b has a neighbour in A ∩ (X_{1} ∪ Y_{1}), then b is strongly complete to A ∩ Z_{1};

• if b has a neighbour in A ∩ (X_{1} ∪ Y_{1}) and A ∩ X_{1}, A ∩ Y_{1} are both nonempty then b is strongly complete to A ∩ V_{1}.

For since b ∈ B is strongly anticomplete to V_{0} it follows that B ∩ V_{0} = ∅, and so V_{0} ⊆ A. This proves the first assertion, and for the other two we may assume that b is adjacent to some a ∈ A∩X_{1} say. Since {a, b} ∪ X_{2} ∪ (A ∩ (Y_{1} ∪ Z_{1})) includes no claw, it follows that b is strongly complete to A ∩ (Y_{1} ∪ Z_{1}), and in particular, this proves the second assertion. For the third, let a′ ∈ A ∩ Y_{1}; then b is adjacent to a′, and so by the same argument with X_{1}, Y_{1} exchanged, it follows that b is strongly complete to A ∩ (V_{1} \ Y_{1}) and therefore to A ∩ V_{1}. This proves (3).

(4) If B ∩ Z_{1} is not strongly anticomplete to A ∩ (X_{1} ∪ Y_{1}), and both A ∩ X_{1}, A ∩ Y_{1} are nonempty, then the theorem holds.

For let P be the set of vertices in B∩Z_{1} that are strongly complete to A∩V_{1}, and let Q = (B∩Z_{1})\P. From (3), every vertex in Q is strongly anticomplete to A ∩ (X_{1} ∪ Y_{1}), and so P ≠ ∅ by hypothesis. Consequently some vertex of P is in a triad, and therefore ∅ ≠ V_{0} ⊆ A, and so A ∩ Z_{1} = ∅. Since the vertices of X_{2} are in triads, it follows that Q ≠ ∅. Since (B ∩ X_{1}) ∪ Q ∪ (A ∩ Y_{1}) ∪ X_{2} includes no claw, it follows that B ∩ X_{1} is strongly anticomplete to A ∩ Y_{1}, and similarly A ∩ X_{1} is strongly anticomplete to B ∩ Y_{1}. But then (G, B, C, A) is a thickening of a member of T C_{3}. This proves (4).

(5) We may assume that V_{0} = ∅ and A ∩ Z_{1}, B ∩ Z_{1} ≠ ∅.

For in view of (2) and (4), we may assume that A ∩ X_{1} is not strongly anticomplete to B ∩ Z_{1}, and A ∩ Y_{1} = ∅. Since vertices in X_{2} are in triads, it follows that X_{2} is not strongly complete to A, and so A ∩ Z_{1} ≠ ∅. By (3) it follows that V_{0} = ∅. This proves (5).

(6) If A ∩ X_{1} is not strongly anticomplete to B ∩ Y_{1} then the theorem holds.

For let A_{1} be the set of vertices in A ∩ X_{1} with a neighbour in B ∩ Y_{1}, and let B_{1} be the set of vertices in B ∩ Y_{1} with a neighbour in A ∩ X_{1}. Since A_{1} ∪ B_{1} ∪ (A ∩ Z_{1}) ∪ X_{2} includes no claw, it follows that B_{1} is strongly complete to A ∩ Z_{1}, and similarly A_{1} is strongly complete to B ∩ Y_{1}. Since A ∩ Z_{1} ≠ ∅, we may assume by (4) that B ∩ X_{1} = ∅, and similarly A ∩ Y_{1} = ∅. Then the sets

X_{1} \ A_{1}, A_{1}, A ∩ Z, B ∩ Z, B_{1}, Y_{1} \ B_{1}, Y_{2}, Z_{2}, X_{2}

(in circular order) show that (G, A, B, C) is a thickening of a member of T C_{2}. This proves (6).

In view of (2) and (4), we may assume that A ∩ X_{1} is not strongly anticomplete to B ∩ Z_{1}, and A ∩ Y_{1} = ∅. Since Y_{1} ≠ ∅, it follows that B ∩ Y_{1} ≠ ∅, and so by (4) with A, B exchanged, we may assume that A ∩ Z_{1} is strongly anticomplete to B ∩ X_{1}.

(7) If A ∩ Z_{1} is not strongly anticomplete to B ∩ Y_{1}, then the theorem holds.

For then by (4) we may assume that B ∩ X_{1} = ∅, and by (6) we may assume that A ∩ X_{1} is strongly anticomplete to B ∩ Y_{1}. Every member of B ∩ Z_{1} with a neighbour in A ∩ X_{1} is strongly complete to A ∩ Z_{1}; and every member of A ∩ Z_{1} with a neighbour in B ∩ Y_{1} is strongly complete to B ∩ Z_{1}. But then (G, A, B, C) is a thickening of a member of T C_{2}. This proves (7).

Thus by (7) we may assume that A ∩ Z_{1} is strongly anticomplete to B ∩ Y_{1}, and by (6) that A ∩ X_{1} is strongly anticomplete to B ∩ Y_{1}. Hence (B ∩ X_{1}, A ∪ (B ∩ Z_{1}), C ∪ (B ∩ Y_{1})) is a generalized 2-join, and so B ∩ X_{1} = ∅, from the choice of V_{0}, V_{1}, V_{2}. Since by (3) every vertex in B ∩ Z_{1} is either strongly anticomplete to A ∩ X_{1} or strongly complete to A ∩ Z_{1}, it follows that (G, A, B, C) is a thickening of a member of T C_{2}. This completes the proof of 6.2.

Next we need the following.

6.3 Let (G, A, B, C) be a three-cliqued claw-free graph, such that G belongs to one of the classes S_{0}, …, S_{7}, and G does not admit a hex-join, and every vertex of G is in a triad. Then (G, A, B, C) is a permutation of a thickening of a member of T C_{1} ∪ ⋯ ∪ T C_{5}.

Proof. First suppose that G ∈ S_{0}; let G be a line trigraph of some graph H. Since A is a strong clique, either there is a vertex a ∈ V (H) such that every edge in A is incident with a, or there is a set of three vertices of H such that every edge in A joins two of these vertices. The same holds for B, C. Suppose that there exist a, b, c ∈ V (H) such that a is incident with every edge in A, and b with B, and c with C. Let X be the set of edges of H with both ends in {a, b, c}. If X = ∅, then a, b, c are pairwise nonadjacent in H, and (G, A, B, C) is a thickening of a permutation of a member of T C_{1} ∪ ⋯ ∪ T C_{4}. (To see this, let us temporarily omit the condition that a, b, c have degree at least three, in the definition of T C_{1}, and let T C′_{1} be the class of trigraphs that we thereby define. It is easy to see that (G, A, B, C) is a thickening of a a member of T C′_{1}; but any member of T C′_{1} not in T C_{1} is a permutation of a member of T C_{2} ∪ T C_{3} ∪ T C_{4}, as can easily be verified using 6.2.) Thus we may assume that X ≠ ∅. If no edge in X is semiadjacent in G to any member of E(H) \ X, then G admits a hex-join (take the cliques A \ X, B \ X, C \ X together with the singleton subsets of X), a contradiction. Thus we may assume that e = ab ∈ X say is semiadjacent in G to f = ad ∈ E(H)\X. Since H is a line trigraph, it follows that a has degree two in H, and d ≠ a, b, c. If e ∉ B, then since e is strongly complete to B, it follows that e is in no triad, a contradiction; so e ∈ B. Hence A = {f}, and so every vertex of G is in a triad with a. Consequently d has degree one in H. But then (G, A, B, C) is a permutation of a thickening of a member of T C_{2}.

Next suppose that a ∈ V (H) is incident with all edges in A, and b ∈ V (H) is incident with all edges in B, and |C| = 3 and the three edges in C form a triangle with vertex set Z say. For each z ∈ Z, the edges of H incident with z are pairwise strongly adjacent in G; for if z has degree at least three, this is true since G is a line trigraph, and if z has degree two then it is true since C is a strong clique. Since every edge of C is in a triad, it follows that a, b ∉ Z. Suppose that e ∈ A is incident with a, b in H. Since e is in a triad, it is antiadjacent to some f ∈ B, and since e, f are both incident with b in H it follows that b has degree two in H and e, f are semiadjacent in G. Consequently B = {f}, and so every edge of H different from f is antiadjacent to f in G. Let f be incident with b, c say. Since the edges of C are antiadjacent to f, we deduce that c ∉ Z, and so c has degree one in H. But then (G, A, B, C) is a permutation of a thickening of a member of T C_{2}. We may therefore assume that a, b are not adjacent in H. Consequently A is the set of all edges of H incident with a, and similarly for B, b. Since the edges of C belong to triads, there is an edge of H incident with no vertex in Z and incident with exactly one of a, b, say with a. If also there is such an edge incident with b, then (G, A, B, C) is a thickening of a member of T C_{3} ∪ T C_{4}; so we may assume that every edge of H incident with b is incident with a vertex in Z. Then no edge of A incident with a vertex in Z belongs to a triad of G, and so H is disconnected, and (G, A, B, C) is a thickening of a member of T C_{2}.

Next suppose that a ∈ V (H) is incident with all edges in A, and the edges in B and in C both form triangles of H. Let Y ⊆ V (H) with |Y | = 3 so that the three members of B each join two vertices of Y, and define Z similarly for C. Since every member of B is in a triad of G, it follows that a ∉ Y, and |Y ∩ Z| ≤ 1, and similarly a ∉ Z. If Y ∩ Z = ∅ then (G, A, B, C) is a thickening of a member of T C_{2}, so we may assume that Y ∩ Z = {y} say. But then (V_{0}, V_{1}, V_{2}) is a generalized 2-join, where V_{0} is the set of (at most one) edge of H between a, y, and V_{1} is the set of edges of H with an end in Y \ {y}, and V_{2} = V (G) \ (V_{0} ∪ V_{1}). From 6.2 the claim follows.

Finally, suppose that all three of A, B, C consist of three edges forming a triangle of H; and so |E(H)| = 9. Let the vertex sets of these three triangles of H be X, Y, Z respectively. Since every edge of H is in a triad of G, it follows that |X ∩ Y | ≤ 1, and similarly |X ∩ Z|, |Y ∩ Z| ≤ 1. If at most one vertex of X belongs to Y ∪ Z, then G admits a 0- or 1-join and the result follows from 6.2; so we may assume that X ∩ Y = {z} and Y ∩ Z = {x} and X ∩ Z = {y} say, where x, y, z are all distinct. But then the edge of C incident with x, y in H belongs to no triad of G, a contradiction. This completes the proof when G ∈ S_{0}.

No trigraph in S_{1} ∪ S_{2} has a vertex set that can be partitioned into three cliques, so next we assume that G ∈ S_{3}. Let Σ be a circle, and let V, F_{1}, …, F_{k} ⊆ Σ be as in the definition of long circular interval trigraph, where V (G) = V. Define “line” as before; we claim that there is a line L with L ∩ V (G) = A. For this is trivial if |A| ≤ 1, so we assume |A| ≥ 2, and since every two members of A are adjacent and therefore both belong to some one of F_{1}, …, F_{k}, there is a line L with both endpoints in A. Choose such a line with L ∩ V (G) maximal. We claim that L ∩ V (G) = A. For first, suppose that there exists a ∈ A with a ∉ L. Let L have endpoints a_{1}, a_{2} say, and let L ⊆ F_{1} say. From the maximality of L, a ∉ F_{1}, and since a, a_{1} are adjacent, there exists i with a, a_{1} ∈ F_{i}; i = 2 say. From the maximality of L and since F_{1} ∪ F_{2} ≠ Σ, it follows that a_{2} ∉ F_{2}. Similarly, since a, a_{2} are adjacent, we may assume that a, a_{2} ∈ F_{3} and a_{1} ∉ F_{1}. But then F_{1} ∪ F_{2} ∪ F_{3} = Σ, a contradiction. This proves that A ⊆ L. Now suppose that there exists b ∈ L ∩ V (G) with b ∉ A, say b ∈ B. Then b is strongly adjacent to all members of A, since A ⊆ F_{1} and b is in the interior of F_{1}; and so b is in no triad, a contradiction. Thus L ∩ V (G) = A. Similarly there are lines for B, C; they are pairwise disjoint and have union V (G), and so (G, A, B, C) ∈ T C_{2}.

No trigraph in S_{4} has a vertex set that is the union of three cliques, so next we assume that G ∈ S_{5}. Let d_{1}, …, d_{5} be as in the definition of S_{5}; let P, Q, R be the sets of vertices different from {d_{1}, …, d_{5}} adjacent to d_{3} and not d_{4}, d_{4} and not d_{3}, and neither of d_{3}, d_{4}, respectively (that is, the sets called A, B, C in the definition of S_{4}). Since d_{1} is in a triad, it follows that d_{1}, d_{2} are semiadjacent. We may assume that d_{5} ∈ A, and so A ⊆ {d_{3}, d_{4}, d_{5}}; and so d_{2} ∉ A; we may assume that d_{2} ∈ B. Hence R ⊆ C, since d_{2}, d_{5} are both anticomplete to R. Let P_{1} be the set of vertices in P with an antineighbour in R, and define Q_{1} ⊆ Q similarly. Then P_{1} ∪ Q_{1} ⊆ B, and so is a strong clique. On the other hand, since d_{3} is in a triad, it follows that Q_{1} ≠ ∅, and similarly P_{1} ≠ ∅; and since every vertex in P has at most one neighbour in Q and vice versa, we deduce that |P_{1}| = |Q_{1}| = 1. Let P_{1} = {p_{1}} and Q_{1} = {q_{1}}. Hence B = {p_{1}, q_{1}, d_{2}}; so A = {d_{3}, d_{4}, d_{5}} and C = {d_{1}} ∪ (P \ P_{1}) ∪ (Q \ Q_{1}) ∪ R. Let R_{1} be the set of vertices in R with an antineighbour in P ∪ Q, necessarily in {p_{1}, q_{1}}. From the definition of S_{4} it follows that R_{1} is strongly anticomplete to both P_{1}, Q_{1}, and |R_{1}| ≤ 1; and R_{1} ≠ ∅ since P_{1}, Q_{1} ≠ ∅. Let R_{1} = {r_{1}} say. Then A \ {d_{5}} is the set of neighbours of d_{5}, and C \ {r_{1}} is the set of neighbours of r_{1}; and since ({d_{2}}, {d_{1}} ∪ (R \ R_{1})) is a homogeneous pair, it follows that (G, A, B, C) is a permutation of a thickening of a member of T C_{3} (taking d_{5}, r_{1} as the vertices called a_{0}, b_{0} in the definition of T C_{3}).

Next, we assume that G ∈ S_{6}. Let a_{0}, b_{0} be as in the definition of S_{6}. Since they are antiadjacent, we may assume that a_{0} ∈ A and b_{0} ∈ B. (Note that A, B, C here refer to the three cliques of our three-cliqued graph, and may be different from the sets called A, B, C in the definition of S_{6}.) Hence every vertex adjacent to a_{0} except b_{0} is strongly complete to A, and since every vertex is in a triad, it follows that every such vertex belongs to A. So in fact the sets called A, B, C here are the same as the sets called A, B, C in the definition of S_{6}, and therefore (G, A, B, C) ∈ T C_{3}.

Finally, we assume that G ∈ S_{7}. Then (G, A, B, C) ∈ T C_{4} from the definition of T C_{4}. This proves 6.3.

Proof of 4.1.

Let (G, A, B, C) be a three-cliqued claw-free graph; we prove that the result holds for (G, A, B, C) by induction on |V (G)|. By 6.1, we may assume that

(1) No two members of the same set A, B, C are twins; and there is no W-join (X, Y) with X a subset of one of A, B, C and Y a subset of another; and (G, A, B, C) is not expressible as a worn hex-join.

(2) There is no choice of cliques P, Q, R with the following properties: (G, P, Q, R) is a three-cliqued trigraph, expressible as a hex-join of two three-cliqued trigraphs (G_{1}, P_{1}, Q_{1}, R_{1}) and (G_{2}, P_{2}, Q_{2}, R_{2}), and P_{1} ⊆ A, Q_{1} ⊆ B, R_{1} ⊆ C, and V (G_{1}) is a union of triads.

For suppose that such P, Q, R exist. Now P_{2} ∩ C is strongly complete to R_{1} since R_{1} ⊆ C and C is a strong clique; and yet P_{2} is strongly anticomplete to R_{1} from the definition of a hex-join. Since R_{1} is nonempty (because V (G_{1}) is a nonempty union of triads) it follows that P_{2} ∩ C = ∅, and similarly Q_{2} ∩ A and R_{2} ∩ B are empty. Let Y = V (G_{1}) and let

X = (A ∩ R_{2}) ∪ (B ∩ P_{2}) ∪ (C ∩ Q_{2}).

Let Z = V (G_{2}) \ X. Suppose that X ≠ ∅; we claim that (G, A, B, C) is a worn hex-join of (G|X, X ∩ A, X ∩ B, X ∩ C) and (G \ X, A \ X, B \ X, C \ X). To see this, we observe that both of these are three-cliqued trigraphs; and certainly X ∩ A is strongly complete to A \ X since A is a strong clique. We must therefore check that X ∩ A is complete to C \ X, and that if u ∈ X ∩ A and v ∈ B \ X are adjacent then u, v are both not in triads. (Also we must check similar statements with A replaced by B, C, which follow from the symmetry.) Since P_{2} ∩ C = ∅, it follows that (X ∩ A) ∪ (Z ∩ C) ⊆ R_{2}, and since R_{2} is a strong clique we deduce that X ∩ A is strongly complete to Z ∩C; and from definition of a hex-join, X ∩A is strongly complete to Y ∩C. Thus X ∩A is strongly complete to C \ X. Now suppose that u ∈ X ∩ A and v ∈ B \ X are adjacent. Then v ∉ Y ∩ B from the definition of a hex-join, and so v ∈ B ∩ Z. Suppose that u ∈ T for some triad T. Since T ∩ C ≠ ∅, and u is strongly complete to C \ X, it follows that there exists c ∈ T ∩ X ∩ C; since c is strongly complete to B \ X (by the argument above, with A, B, C replaced by B, C, A), it follows that T ⊆ X; and then {v} ∪ T is a claw, a contradiction. Thus u is in no triad, and similarly v is in no triad. This proves our claim; but that is contradictory to (1). Hence X = ∅, and similarly Z = ∅, a contradiction since V (G_{2}) ≠ ∅. Thus there do not exist such P, Q, R. This proves (2).

(3) We may assume that G admits no hex-join, and every vertex of G is in a triad.

For if G is antiprismatic then the theorem holds. We assume then that there are two triads T_{1}, T_{2} with |T_{1} ∩ T_{2}| = 2. Suppose that some vertex v is in no triad, with v ∈ A say. Then (1) and (2) contradict 5.2 applied to the three cliques A\{v}, B, C. Thus every vertex is in a triad. Suppose that G admits a hex-join (V_{1}, V_{2}); then every triad is a subset of one of V_{1}, V_{2}, and we may assume that T_{1}, T_{2} ⊆ V_{1}, and again (1) and (2) contradict 5.2 applied to the three cliques A ∩ V_{1}, B ∩ V_{1}, C ∩ V_{1}. This proves (3).

If G admits a 0, 1- or generalized 2-join, the result holds by 6.2; so we may assume that G is indecomposable. By 5.1, G ∈ S_{0} ∪⋯∪S_{7}. But then the result follows from 6.3. This proves 4.1.

7 Statement of the main theorem

We have completed the description of the claw-free trigraphs G such that V (G) is the union of three strong cliques, and now we begin the study of the others. Our goal in this section is to state the counterpart of 4.1.

A vertex v of a trigraph is simplicial if N ∪ {v} is a strong clique, where N is the set of all neighbours of v. Let us say (G, Z) is a stripe if G is a claw-free trigraph, and Z ⊆ V (G) is a set of simplicial vertices, such that Z is strongly stable and no vertex has two neighbours in Z.

Let (G′, Z′) be a stripe, and let G be a thickening of G′, with sets X_{v} (v ∈ V (G′)), such that |X_{z}| = 1 for each z ∈ Z′. Let Z = ∪_{z∈Z′}X_{z}. Then (G, Z) is also a stripe, and we say it is a thickening of (G′, Z′).

Let (G, A, B, C) be a three-cliqued claw-free trigraph, and let z ∈ A such that z is strongly anticomplete to B ∪C. Let V_{1}, V_{2}, V_{3} be three disjoint sets of new vertices, and let G′ be the trigraph obtained by adding V_{1}, V_{2}, V_{3} to G with the following adjacencies:

• V_{1} and V_{2} ∪ V_{3} are strong cliques

• V_{1} is strongly complete to B ∪ C and strongly anticomplete to A

• V_{2} is strongly complete to C ∪ A and strongly anticomplete to B

• V_{3} is strongly complete to A ∪ B and strongly anticomplete to C.

(The adjacency between V_{1} and V_{2} ∪ V_{3} is unspecified.) It follows that G′ is a claw-free trigraph, and z is a simplicial vertex of it. In this case we say that (G′, z) is a hex-expansion of (G, A, B, C).

Here are some types of stripes. We call the corresponding sets of pairs (G, Z) Z_{1}–Z_{15}, and we define Z_{0} to be the set of all members of Z_{1}–Z_{15} that are not thickenings of members of Z_{1}–Z_{15} with fewer vertices.

Z_{1}: Let G be a trigraph with vertex set {v_{1}, …, v_{n}}, such that for 1 ≤ i < j < k ≤ n, if v_{i}, v_{k} are adjacent then v_{j} is strongly adjacent to both v_{i}, v_{k}. We call G a linear interval trigraph. (Every linear interval trigraph is also a long circular interval trigraph.) Also, let n ≥ 2, let v_{1}, v_{n} be strongly antiadjacent, and let there be no vertex adjacent to both v_{1}, v_{n}, and no vertex semiadjacent to either v_{1} or v_{n}. Let Z = {v_{1}, v_{n}}.

Z_{2}: Let G ∈ S_{6}, let a_{0}, b_{0} etc. be as in the definition of S_{6}, with a_{0}, b_{0} strongly antiadjacent, and let Z = {a_{0}, b_{0}}.

Z_{3}: Let H be a graph, and let h_{1}-h_{2}-h_{3}-h_{4}-h_{5} be the vertices of a path of H in order, such that h_{1}, h_{5} both have degree one in H, and every edge of H is incident with one of h_{2}, h_{3}, h_{4}. Let G be obtained from a line trigraph of H by making the edges h_{2}h_{3} and h_{3}h_{4} of H (vertices of G) either semiadjacent or strongly antiadjacent to each other in G. Let Z = {h_{1}h_{2}, h_{4}h_{5}}.

Z_{4}: Let G be the trigraph with vertex set {a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}} and adjacency as follows: {a_{0}, a_{1}, a_{2}}, {b_{0}, b_{1}, b_{2}, b_{3}}, {a_{2}, c_{1}, c_{2}} and {a_{1}, b_{1}, c_{2}} are strong cliques; b_{2}, c_{1} are strongly adjacent; b_{2}, c_{2} are semiadjacent; b_{3}, c_{1} are semiadjacent; and all other pairs are strongly antiadjacent. Let Z = {a_{0}, b_{0}}.

Z_{5}: Let G ∈ S_{2}, and let v_{1}, …, v_{13}, X, H be as in the definition of S_{2}, where G = H \ X; let v_{7}, v_{8} be strongly antiadjacent in H, and let Z = {v_{7}, v_{8}} \ X.

Z_{6}: Let G be a long circular interval trigraph, and let Σ, F_{1}, …, F_{k} be as in the corresponding definition. Let z ∈ V (G) belong to at most one of F_{1}, …, F_{k}, and not be an endpoint of any of F_{1}, …, F_{k}. Then z is a simplicial vertex of G; let Z = {z}.

Z_{7}: Let G ∈ S_{4}, let H, h_{1}, …, h_{7} be as in the definition of S_{4}, let e be the edge h_{6}h_{7} of H, and let Z = {e}.

Z_{8}: Let G ∈ S_{5}, let d_{1}, …, d_{5}, A, B, C be as in the definition of S_{5}, and let Z = {d_{5}}.

Z_{9}: Let G have vertex set partitioned into five sets {z}, A, B, C, D, with |A| = |B| > 0, say A = {a_{1}, …, a_{n}} and B = {b_{1}, …, b_{n}} where n ≥ 1, such that

• {z} ∪ D is a strong clique and z is strongly antiadjacent to A ∪ B ∪ C,

• A ∪ C and B ∪ C are strong cliques,

• for 1 ≤ i ≤ n, a_{i}, b_{i} are antiadjacent, and every vertex in D is strongly adjacent to exactly one of a_{i}, b_{i} and strongly antiadjacent to the other, and

• for 1 ≤ i < j ≤ n, {a_{i}, b_{i}} is strongly complete to {a_{j}, b_{j}}.

(The adjacency between C and D is arbitrary.) Every such trigraph G is antiprismatic. Let Z = {z}.

Z_{10}: Let G′ be the trigraph with vertex set {a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}, d} and adjacency as follows: A = {a_{0}, a_{1}, a_{2}, d}, B = {b_{0}, b_{1}, b_{2}, b_{3}}, C = {c_{1}, c_{2}} and {a_{1}, b_{1}, c_{2}} are strong cliques; a_{2} is strongly adjacent to b_{0} and semiadjacent to b_{1}; b_{2}, c_{2} are semiadjacent; b_{2}, c_{1} are strongly adjacent; b_{3}, c_{1} are either semiadjacent or strongly adjacent; b_{0}, d are either semiadjacent or strongly adjacent; and all other pairs are strongly antiadjacent. Then (G′, A, B, C) is a threecliqued trigraph (not clawfree) and a_{0} is a simplicial vertex of G′. Let X ⊆ {a_{2}, b_{2}, b_{3}, d} such that either a_{2} ∈ X or {b_{2}, b_{3}} ⊆ X, let Z = {a_{0}}, and let (G, Z) be a hex-expansion of (G′ \ X, A \ X, B \ X, C).

Z_{11}: Let G_{1} ∈ S_{6}, and let a_{0}, b_{0}, A, B, C, A′, B′, C′ be as in the definition of S_{6}, with a_{0}, b_{0} semiadjacent. Let G_{2} be obtained from G_{1} by adding a new vertex z strongly complete to A and strongly anticomplete to B ∪C, and possibly making a_{0}, b_{0} strongly adjacent, and let Y ⊆ {a_{0}}; then (G_{2}\Y, (A\Y)∪{z}, B, C) is a three-cliqued trigraph and z is a simplicial vertex of G_{2}\Y. Let Z = {z}, and let (G, Z) be a hex-expansion of (G_{2} \ Y, (A \ Y) ∪ Z, B, C).

Z_{12}: Let H, v_{1}, …, v_{9}, X be as in the second construction of T C_{5}, where v_{2}, v_{4} are adjacent. Add a new vertex z to H, strongly adjacent to v_{3}, v_{4}, v_{5}, v_{6}, v_{9}, forming H_{2} say. Then

(H_{2} \ X, {v_{3}, v_{4}, v_{5}, v_{6}, v_{9}, z} \ X, {v_{7}, v_{8}}, {v_{1}, v_{2}})

is a three-cliqued trigraph and z is a simplicial vertex of H_{2} \ X. Let Z = {z}, and let (G, Z) be a hex-expansion of this three-cliqued trigraph.

Z_{13}: Let (H, V (H) ∩ L_{1}, V (H) ∩ L_{2}, V (H) ∩ L_{3}) ∈ T C_{2}, where Σ, F_{1}, …, F_{k}, L_{1}, L_{2}, L_{3} are as in the corresponding definition. Let z ∈ L_{1} belong to exactly one of F_{1}, …, F_{k}, say F_{1}; thus L_{1} ⊆ F_{1}. Let z belong to the interior of F_{1}. Thus z is a simplicial vertex of H. Let Z = {z}, and let (G, Z) be a hex-expansion of (H, V (H) ∩ L_{1}, V (H) ∩ L_{2}, V (H) ∩ L_{3}).

Z_{14}: Let v_{0}, v_{1}, v_{2}, v_{3} be distinct vertices of a graph H, such that: v_{1} is the only neighbour of v_{0} in H; every vertex of H different from v_{0}, v_{1}, v_{2}, v_{3} is adjacent to both v_{2}, v_{3}, and at most one of them is nonadjacent to v_{1}; and v_{1}, v_{2}, v_{3} are pairwise nonadjacent, and each has degree at least three. For i = 1, 2, 3, let A_{i} be the set of edges of H incident with v_{i}, and let z be the edge v_{0}v_{1}. Let G_{1} be a line trigraph of H; thus (G_{1}, A_{1}, A_{2}, A_{3}) is a three-cliqued claw-free trigraph, and z is a simplicial vertex of G_{1}. Let Z = {z}, and let (G, Z) be a hex-expansion of (G_{1}, A_{1}, A_{2}, A_{3}).

Z_{15}: Let v_{1}, …, v_{8}, H, A, B, C, X be as in the first construction of T C_{5}. Then (H, A, B, C) is a three-cliqued trigraph and v_{8} is a simplicial vertex of H; let Z = {v_{8}}, and let (G, Z) be a hex-expansion of (H, A, B, C).

These, and thickenings of them, will be the building blocks of our theorem describing how to construct all the connected claw-free trigraphs that admit a strip-structure. Now we explain how these building blocks fit together.

A hypergraph H consists of a finite set V (H), a finite set E(H), and an incidence relation between V (H) and E(H) (that is, a subset of V (H) × E(H)). For the statement of the main theorem, we only need hypergraphs such that every member of E(H) is incident with either one or two members of V (H) (thus, these hypergraphs are graphs if we permit “graphs” to have loops and parallel edges), but it is helpful for the proof, later, to permit general hypergraphs. If F ∈ E(H) we write \overline{F} to denote the set of all h ∈ V (H) incident with F.

Let G be a trigraph. A strip-structure (H, η) of G consists of a hypergraph H with E(H) ≠ ∅, and a function η mapping each F ∈ E(H) to a subset η(F) of V (G), and mapping each pair (F, h) with F ∈ E(H) and h ∈ \overline{F} to a subset η(F, h) of η(F), satisfying the following conditions.

(SD1) The sets η(F) (F ∈ E(H)) are nonempty and pairwise disjoint and have union V (G).

(SD2) For each h ∈ V (H), the union of the sets η(F, h) for all F ∈ E(H) with h ∈ \overline{F} is a strong clique of G.

(SD3) For all distinct F_{1}, F_{2} ∈ E(H), if v_{1} ∈ η(F_{1}) and v_{2} ∈ η(F_{2}) are adjacent in G, then there exists h ∈ \overline{F_{1}} ∩ \overline{F_{2}} such that v_{1} ∈ η(F_{1}, h) and v_{2} ∈ η(F_{2}, h).

(SD4) For each F ∈ E(H), the family η(F, h) (h ∈ \overline{F}) is a circus in η(F).

(We postpone the definition of a “circus” to the next section, and the reader should ignore condition (SD4) through the remainder of this section.)

Let (H, η) be a strip-structure of a trigraph G, and let F ∈ E(H), where \overline{F} = \{h_{1}, …, h_{k}\}. Let v_{1}, …, v_{k} be new vertices, and let J be the trigraph obtained from G|η(F) by adding v_{1}, …, v_{k}, where v_{i} is strongly complete to η(F, h_{i}) and strongly anticomplete to all other vertices of J. We call (J, {v_{1}, …, v_{k}}) the strip of (H, η) at F. (Thus, it is uniquely defined except for the choice of the new vertices v_{1}, …, v_{k}, and we speak of “the” strip at F without serious ambiguity.) These strips are not necessarily stripes; but soon we will only need to consider strip-structures in which every strip is either a stripe or is very simple.

This provides a way to piece together claw-free trigraphs to make larger claw-free trigraphs, because of the following.

7.1 Let (H, η) be a strip-structure of a trigraph G. If J is claw-free for every strip (J, Z) of this strip-structure, then G is claw-free.

Proof. Suppose that {a, b, c, d} is a claw in G, where a is adjacent to b, c, d and {b, c, d} is stable. By (SD1), we may choose F ∈ E(H) with a ∈ η(F). Let \overline{F} = \{h_{1}, …, h_{k}\}, and let J be the strip at F, with new vertices v_{1}, …, v_{k}. We shall show that J contains a claw. If b, c, d ∈ η(F) then {a, b, c, d} is a claw of J, so we may assume that b ∉ η(F). Choose F_{1} ∈ E(H) with b ∈ η(F_{1}); thus F_{1} ≠ F. Since a, b are adjacent, we may assume by (SD3) that h_{1} ∈ \overline{F} ∩ \overline{F_{1}} and a ∈ η(F, h_{1}) and b ∈ η(F_{1}, h_{1}). Neither of c, d belongs to η(F, h_{1}) by (SD2) since they are antiadjacent to b; and if they are both in η(F) \ η(F, h_{1}) then {a, v_{1}, c, d} is a claw of J, so we may assume that c ∉ η(F). Choose F_{2} ∈ E(H) with c ∈ η(F_{2}). Then F_{2} ≠ F, and there exists h ∈ \overline{F} ∩ \overline{F_{2}} with a ∈ η(F, h) and c ∈ η(F_{2}, h). Since b, c are antiadjacent, it follows that c ∉ η(F_{1}, h_{1}), and so h ≠ h_{1} and we may assume that h = h_{2}. If d ∈ η(F) \ (η(F, h_{1}) ∪ η(F, h_{2})), then {a, v_{1}, v_{2}, d} is a claw in J, so we assume not; and certainly d ∉ η(F, h_{1}) ∪ η(F, h_{2}) since it is antiadjacent to b, c. Hence d ∉ η(F), and we deduce that there exists F_{3} ∈ E(H) \ \{F \} and h_{3} ∈ \overline{F} ∩ \overline{F_{3}} with a ∈ η(F, h_{3}) and d ∈ η(F_{3}, h_{3}). Also by the same argument, h_{3} ≠ h_{1}, h_{2}; but then {a, v_{1}, v_{2}, v_{3}} is a claw in J. This proves 7.1.

We say a strip-structure (H, η) is nontrivial if |E(H)| ≥ 2. Now we can at least state the counterpart of 4.1, which together with 4.1 has been the goal of this series of papers, although we are not ready to prove it yet.

7.2 Let G be a connected claw-free trigraph, such that V (G) is not the union of three strong cliques. Then either

• G is a thickening of a member of S_{1} ∪ S_{3} ∪ S_{7}, or

• G admits a nontrivial strip-structure such that for each strip (J, Z), 1 ≤ |Z| ≤ 2, and either – |V (J)| = 3 and |Z| = 2, or

– (J, Z) is a thickening of a member of Z_{0}.

8 Optimal strip-structures

We have not yet explained condition (SD4); let us do so now. Let G be a trigraph, let Y ⊆ V (G), and let X_{i} (1 ≤ i ≤ k) be a family of subsets of Y. We say that this family is a circus in Y if

(CS1) For 1 ≤ i ≤ k and all x ∈ X_{i}, the set of all neighbours of x in Y \ X_{i} is a strong clique.

(CS2) For 1 ≤ i < j ≤ k, X_{i} ∩ X_{j} is strongly anticomplete to Y \ (X_{i} ∪ X_{j}).

(CS3) For 1 ≤ h < i < j ≤ k, X_{h} ∩ X_{i} ∩ X_{j} = ∅.

It is easy to see that condition (SD4) is equivalent (assuming that G is claw-free) to assuming that all the strips are claw-free; and since in the statement of 7.2, all the strips are claw-free anyway, deleting (SD4) from the definition of a strip-structure would have no effect on the meaning of 7.2. The reason for retaining (SD4) is to facilitate the proof of 7.2; because our proof method is to choose a nontrivial strip-structure (H, η) (with all strips claw-free), that cannot be “refined” any further, and prove that it has the properties we require. And the reason for using “circus” instead of just saying that the strips are claw-free is because we thereby avoid having to refer to the extra vertices v_{1}, …, v_{k}.

If (H, η) is a strip-structure, its nullity is the number of pairs (F, h) with F ∈ E(H) and h ∈ \overline{F} such that η(F, h) = ∅. For a fixed trigraph G, a strip-structure (H, η) of G is said to be optimal if there is no strip-structure (H′, η′) of G with |E(H′)| ≥ |E(H)|, such that either |E(H′)| > |E(H)|, or the nullity of (H′, η′) is strictly smaller than that of (H, η). Every strip-structure (H, η) of G satisfies |E(H)| ≤ |V (G)| (since the sets η(F) (F ∈ E(H)) are nonempty and pairwise disjoint), and every trigraph admits a strip-structure (H, η) where H is a hypergraph with |V (H)| = 0 and |E(H)| = 1, and so every trigraph admits an optimal strip-structure. As we shall see, optimal strip-structures have a number of attractive properties.

If a strip-structure (H, η) also satisfies the following condition, we call the strip-structure purified:

• for each F ∈ E(H), either all the sets η(F, h) (h ∈ \overline{F}) are pairwise disjoint, or |\overline{F} | = 2 and |η(F)| = 1 and η(F, h_{1}) = η(F, h_{2}) = η(F) where \overline{F} = \{h_{1}, h_{2}\}.

In other words, all the corresponding strips are either stripes or spots, where a spot is a pair (J, Z) such that J has three vertices say v, z_{1}, z_{2}, and v is strongly adjacent to z_{1}, z_{2}, and z_{1}, z_{2} are strongly antiadjacent, and Z = {z_{1}, z_{2}}.

8.1 Let G be a claw-free trigraph. Then every optimal strip-structure of G has nullity zero and is purified.

Proof. Let (H, η) be an optimal strip-structure of G. Let F ∈ E(H), and let \overline{F} = \{h_{1}, …, h_{k}\}. Suppose first that η(F, h_{1}) = ∅. Let H′ be the hypergraph obtained from H by making F not incident with h_{1}, and leaving the incidence of all other pairs unchanged. For each F_{0} ∈ E(H) let η′(F_{0}) = η(F_{0}), and for each h incident with F_{0} in H′, let η′(F_{0}, h) = η(F_{0}, h). Then (H′, η′) is a strip-structure of G, and E(H′) = E(H), and its nullity is smaller than that of (H, η), contrary to the optimality of (H, η). This proves that (H, η) has nullity zero.

Now again let F ∈ E(H) with \overline{F} = \{h_{1}, …, h_{k}\}, and suppose that k ≥ 2 and η(F, h_{1})∩η(F, h_{2}) ≠ ∅. Write W = η(F, h_{1})∩η(F, h_{2}). Define (H′, η′) as follows. Let F′ ∉ V (H)∪E(H) be a new element. Then

• V (H′) = V (H), and E(H′) = E(H) ∪ {F′}

• for each F_{0} ∈ E(H) and h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H;

• F′ is incident in H′ with h_{1}, h_{2} and with no other member of V (H);

• for each F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• η′(F) = η(F) \ W;

• for i = 1, 2, η′(F, h_{i}) = η(F, h_{i}) \ W, and for 3 ≤ i ≤ k, η′(F, h_{i}) = η(F, h_{i});

• η′(F′) = η′(F′, h_{1}) = η′(F′, h_{2}) = W. We see that for 3 ≤ i ≤ k, η′(F, h_{i}) ⊆ η′(F), since no vertex belongs both to W and to some η(F, h_{i}) with i ≥ 3 from (CS3). Also, from (CS2), W is strongly anticomplete to η(F)\(η(F, h_{1})∪η(F, h_{2})), and so (H′, η′) satisfies (SD3). But from the optimality of (H, η), (H′, η′) cannot be a strip-structure of G, and therefore does not satisfy (SD1); and so η′(F) = ∅, that is, η(F, h_{1}) = η(F, h_{2}) = η(F), and in particular, η(F) is a strong clique. Since (H, η) has zero nullity, it follows that k = 2.

Suppose that |η(F)| > 1, and choose a partition (X_{1}, X_{2}) of η(F) with X_{1}, X_{2} ≠ ∅. Define (H′, η′) as follows. Let F′ ∉ V (H) ∪ E(H) be a new element. Then

• V (H′) = V (H), and E(H′) = E(H) ∪ {F′}

• for each F_{0} ∈ E(H) and h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H;

• F′ is incident in H′ with h_{1}, h_{2} and with no other member of V (H);

• for each F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• η′(F) = η′(F, h_{1}) = η′(F, h_{2}) = X_{1} and η′(F′) = η′(F′, h_{1}) = η′(F′, h_{2}) = X_{2}. Then (H′, η′) is a strip-structure of G, contrary to the optimality of (H, η). Hence |η(F)| = 1, and therefore (H, η) is purified. This proves 8.1.

9 Unbreakable stripes

Let us say a trigraph G admits a pseudo-1-join if there is a partition V_{1}, V_{2} of V (G), and for i = 1, 2 there is a subset A_{i} ⊆ V_{i} such that:

• for i = 1, 2, V_{1}, V_{2} are not strongly stable • A_{1} ∪ A_{2} is a strong clique, and

• V_{1} \ A_{1} is strongly anticomplete to V_{2}, and V_{1} is strongly anticomplete to V_{2} \ A_{2}. It is easy to check that if G admits a 1-join and no 0-join, then it admits a pseudo-1-join, and the converse is false.

Let us say that G admits a pseudo-2-join if there is a partition V_{0}, V_{1}, V_{2} of V (G) (where V_{0} may be empty), and for i = 1, 2 there are disjoint subsets A_{i}, B_{i} of V_{i} satisfying the following:

• V_{0} ∪A_{1} ∪A_{2} and V_{0} ∪B_{1} ∪B_{2} are strong cliques, and V_{0} is strongly anticomplete to V_{i} \(A_{i} ∪B_{i}) for i = 1, 2;

• for i = 1, 2, V_{i} is not strongly stable; and

• for all v_{1} ∈ V_{1} and v_{2} ∈ V_{2}, either v_{1} is strongly antiadjacent to v_{2}, or v_{1} ∈ A_{1} and v_{2} ∈ A_{2}, or

v_{1} ∈ B_{1} and v_{2} ∈ B_{2}. Again, if G admits a 2-join or generalized 2-join then it admits a pseudo-2-join, and the converse is not true.

Finally, let us say G admits a biclique if there is a partition V_{1}, V_{2}, V_{3}, V_{4} of V (G), and

• V_{1} ≠ ∅, and V_{1} ∪ V_{2}, V_{1} ∪ V_{3} are strong cliques

• V_{1} is strongly anticomplete to V_{4}

• either |V_{1}| ≥ 2, or V_{2} ∪ V_{3} is not a strong clique

• V_{2} ∪ V_{3} ∪ V_{4} is not strongly stable

• if v_{2} ∈ V_{2} and v_{3} ∈ V_{3} are adjacent then they have the same neighbours in V_{4} and neither of them is semiadjacent to any member of V_{4}.

It is convenient to say that a stripe (J, Z) is a clique if V (J) is a strong clique. A stripe (J, Z) is said to be unbreakable if

• J does not admit a 0-join, a pseudo-1-join, a pseudo-2-join or a biclique,

• there are no twins u, v ∈ V (J) \ Z,

• there is no W-join (A, B) in J such that Z ∩ A, Z ∩ B = ∅, and

• Z is the set of all vertices that are simplicial in J. The reason for interest in this concept is the following. 9.1 Every claw-free trigraph admits a strip-structure such that all its strips are either spots or cliques or thickenings of unbreakable stripes.

Proof. Let G be a claw-free trigraph, and let (H, η) be an optimal strip-structure. Let F ∈ E(H), and let (J, Z) be the corresponding strip. We claim that either (J, Z) is a spot or a clique or a thickening of an unbreakable stripe. We may assume that (J, Z) is not a spot; so by 8.1 (J, Z) is a stripe; and we may assume it is not a clique. Let \overline{F} = \{h_{1}, …, h_{k}\}, and let Z = \{v_{1}, …, v_{k}\} as usual.

(1) J does not admit a 0-join.

For suppose that J admits a 0-join (V_{1}, V_{2}). For j = 1, 2, let Q_{j} = Z ∩ V_{j}, and

P_{j} = {h_{i} : 1 ≤ i ≤ k and v_{i} ∈ V_{j}}.

Since (V_{1}, V_{2}) is a 0-join, it follows that P_{1} ∩ P_{2} = ∅ and P_{1} ∪ P_{2} = {h_{1}, …, h_{k}}. If V_{1} = Q_{1}, then since V_{1} ≠ ∅, we may assume that v_{1} ∈ Q_{1}; and since (H, η) has nullity zero, v_{1} has a neighbour in J, which is necessarily in V_{1} and not in Q_{1}, a contradiction. Thus V_{1} \ Q_{1} ≠ ∅, and similarly V_{2} \ Q_{2} ≠ ∅.

Let (H′, η′) be defined as follows. Let F′_{1}, F′_{2} be new elements not in V (H) ∪ E(H). Then

• V (H′) = V (H) and E(H′) = (E(H) \ {F }) ∪ {F′_{1}, F′_{2}};

• for each F_{0} ∈ E(H) \ {F } and h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H;

• for j = 1, 2 and h ∈ V (H), F′_{j} is incident with h in H′ if and only if h ∈ P_{j};

• for all F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• for j = 1, 2, η′(F′_{j}) = V_{j} \ Q_{j}; and

• for j = 1, 2 and h ∈ P_{j}, η′(F′_{j}, h) = η(F, h).

Then (H′, η′) is a strip-structure of G, contradicting the optimality of (H, η). This proves (1).

(2) J does not admit a pseudo-1-join.

For suppose that it does; then there is a partition (V_{1}, V_{2}) of V (J), and for i = 1, 2, a subset A_{i} ⊆ V_{i}, such that:

• for i = 1, 2, V_{i} is not strongly stable

• A_{1} ∪ A_{2} is a strong clique, and

• V_{1} \ A_{1} is strongly anticomplete to V_{2}, and V_{1} is strongly anticomplete to V_{2} \ A_{2}.

Since J does not admit a 0-join, it follows that A_{i} ≠ ∅ for i = 1, 2. For j = 1, 2, since V_{j} is not strongly stable, there is a vertex of V_{j} that is not in Z. Suppose first that none of v_{1}, …, v_{k} belong to A_{1} ∪ A_{2}. For j = 1, 2, let Q_{j} = V_{j} ∩ Z, and let

P_{j} = {h_{i} : 1 ≤ i ≤ k and v_{i} ∈ V_{j}}.

It follows that P_{1} ∩ P_{2} = ∅ and P_{1} ∪ P_{2} = {h_{1}, …, h_{k}}, and V_{j} \ Q_{j} ≠ ∅ for j = 1, 2, as we already saw. Let (H′, η′) be defined as follows. Let F′_{1}, F′_{2}, h′ be new elements not in V (H) ∪ E(H). Then • V (H′) = V (H) ∪ {h′} and E(H′) = (E(H) \ {F }) ∪ {F′_{1}, F′_{2}};

• for each F_{0} ∈ E(H) \ {F } and h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H;

• no member of E(H) is incident with h′ in H′;

• for j = 1, 2 and h ∈ V (H), F′_{j} is incident with h in H′ if and only if h ∈ P_{j};

• for j = 1, 2, F′_{j} is incident with h′;

• for all F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• for j = 1, 2, η′(F′_{j}) = V_{j} \ Q_{j};

• for j = 1, 2 and h ∈ P_{j}, η′(F′_{j}, h) = η(F, h); and

• for j = 1, 2, η′(F′_{j}, h′) = A_{j}.

We claim that (H′, η′) is a strip-structure of G. Certainly for each h_{i} ∈ P_{j}, η′(F′_{j}, h_{i}) = η(F, h_{i}) ⊆ V_{j} \ Q_{j} = η′(F′_{j}) since v_{i} ∉ A_{j}. Also, (SD1),(SD2),(SD3) are clear (note that since (V_{1}, V_{2}) is a pseudo-1-join, (SD2) and (SD3) are satisfied for pairs of vertices both in η(F)); let us check (SD4). It suffices to check that the family η′(F′_{1}, h) (h ∈ P_{1} ∪ {h′}) is a circus in η′(F′_{1}). Choose a_{2} ∈ A_{2}; then a_{2} is strongly anticomplete to η′(F′_{1}) \ η′(F′_{1}, h′). Let v ∈ η′(F′_{1}, h′); since η(F, h) (h ∈ Z) is a circus in η(F), it suffices to check that

• the set of neighbours of v in η′(F′_{1}) \ η′(F′_{1}, h′) is a strong clique

• if v ∈ η′(F′_{1}, h) for some h ∈ P_{1}, then every neighbour of v in η′(F′_{1}) belongs to η′(F′_{1}, h) ∪ η′(F′_{1}, h′)

• v belongs to η′(F′_{1}, h) for at most one h ∈ P_{1}.

The first assertion holds since v is adjacent to a_{2}, and G is claw-free. The second holds since v is adjacent to a_{2} and the family η(F, h) : (h ∈ \overline{F}) satisfies (CS1); and the third holds since (H, η) is purified. Consequently, (H′, η′) is a strip-structure of G, contradicting the optimality of (H, η).

Next, suppose that one of v_{1}, …, v_{k} belong to A_{1} ∪ A_{2}, v_{1} ∈ A_{1} say. Since A_{1} ∪ A_{2} is a strong clique, and v_{1}, …, v_{k} are pairwise antiadjacent and no two of them have a common neighbour (since (H, η) is purified), it follows that v_{2}, …, v_{k} ∉ A_{1} ∪A_{2} and are strongly anticomplete to A_{1} ∪A_{2}. Also, v_{1} is strongly anticomplete to (V_{1} ∪V_{2})\(A_{1} ∪A_{2}), since every vertex in this set has an antineighbour in A_{1} ∪ A_{2} and v_{1} is simplicial. For j = 1, 2, let Q_{j} = Z ∩ V_{j} and let

P_{j} = {h_{i} : 2 ≤ i ≤ k and v_{i} ∈ V_{j}}.

Then P_{1} ∩ P_{2} = ∅ and P_{1} ∪ P_{2} = {h_{2}, …, h_{k}}. As we already saw, V_{1} \ (Q_{1} ∪ {v_{1}}), V_{2} \ Q_{2} ≠ ∅. Define (H′, η′) as follows. Let F′_{1}, F′_{2} be two new elements not in V (H) ∪ E(H). Then

• V (H′) = V (H) and E(H′) = (E(H) \ {F }) ∪ {F′_{1}, F′_{2}};

• for each F_{0} ∈ E(H) \ {F } and h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H; • for j = 1, 2 and h ∈ V (H), F′_{j} is incident with h in H′ if and only if h ∈ P_{j} ∪ {h_{1}};

• for all F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• η′(F′_{1}) = V_{1} \ (Q_{1} ∪ {v_{1}}) and η′(F′_{2}) = V_{2} \ Q_{2};

• for j = 1, 2 and h ∈ P_{j}, η′(F′_{j}, h) = η(F, h); and

• η′(F′_{1}, h_{1}) = A_{1} \ {v_{1}} and η′(F′_{2}, h_{1}) = A_{2}.

Note that A_{1} \ {v_{1}}, A_{2} ≠ ∅ since J does not admit a 0-join; so we can prove as before that (H′, η′) is a strip-structure of G, contradicting the optimality of (H, η). This proves (2).

(3) J does not admit a pseudo-2-join.

For suppose that it does. The previous case divided into two subcases depending whether one of v_{1}, …, v_{k} belongs to A_{1} ∪ A_{2} or not, and the same happens for pseudo-2-joins, except there are more subcases. Let us therefore handle them all simultaneously. We have three sets V_{0}, V_{1}, V_{2} as in the definition of a pseudo-2-join, where V_{0} may be empty. Also, for i = 1, 2 we will have subsets A_{i}, B_{i} of V_{i} as in the definition of pseudo-2-join. We may assume that J does not admit a pseudo-1-join, and so A_{1}, A_{2}, B_{1}, B_{2} are all nonempty. Possibly one vertex in A_{1} ∪ A_{2} belongs to Z (at most one since {v_{1}, …, v_{k}} is stable), and if say v_{1} ∈ Z ∩(A_{1} ∪A_{2}) then v_{1} has no neighbours in (V_{1} ∪V_{2})\(A_{1} ∪A_{2}) since A_{1}, A_{2} are nonempty and v_{1} is simplicial. The same applies to B_{1}, B_{2}. Also none of v_{1}, …, v_{k} belong to V_{0} since V_{0} is complete to A_{1} and to B_{2}, and A_{1} is not complete to B_{2}. For i = 1, 2, since V_{i} is not strongly stable, at least one vertex of V_{i} does not belong to {v_{1}, …, v_{k}}.

For i = 1, 2, let Q_{i} = Z ∩ (V_{i} \ (A_{i} ∪ B_{i})); and let Q_{3} = Z ∩ (A_{1} ∪ A_{2}) and Q_{4} = Z ∩ (B_{1} ∪ B_{2}). For i = 1, 2, let C_{i} = A_{i} \ Q_{3}, let D_{i} = B_{i} \ Q_{4}, and let W_{i} = V_{i} \ Z. In summary, then, we have a partition V_{0}, W_{1}, W_{2}, Q_{3}, Q_{4} of V (J), and for i = 1, 2 there are subsets C_{i}, D_{i}, Q_{i} of W_{i} satisfying the following:

• Q_{1} ∪ Q_{2} ∪ Q_{3} ∪ Q_{4} = Z, and |Q_{3}|, |Q_{4}| ≤ 1

• V_{0} ∪ C_{1} ∪ C_{2} ∪ Q_{3} and V_{0} ∪ D_{1} ∪ D_{2} ∪ Q_{4} are strong cliques, and V_{0} is strongly anticomplete to W_{i} \ (C_{i} ∪ D_{i}) for i = 1, 2;

• for i = 1, 2, the sets C_{i}, D_{i}, Q_{i} are pairwise disjoint, and W_{i} \ Q_{i} ≠ ∅;

• for all w_{1} ∈ W_{1} and w_{2} ∈ W_{2}, either w_{1} is strongly antiadjacent to w_{2}, or w_{1} ∈ C_{1} and w_{2} ∈ C_{2}, or w_{1} ∈ D_{1} and w_{2} ∈ D_{2};

• Q_{3} is strongly anticomplete to W_{1} ∪ W_{2} \ (C_{1} ∪ C_{2}), and Q_{4} is strongly anticomplete to W_{1} ∪ W_{2} \ (D_{1} ∪ D_{2}).

Since J does not admit a pseudo-1-join, it follows that C_{1}, C_{2}, D_{1}, D_{2} are all nonempty. Define (H′, η′) as follows. Let F′_{1}, F′_{2} be two new elements. If Q_{3} = ∅ let h′_{1} be another new element, and otherwise let h′_{1} = h_{i} where Q_{3} = {v_{i}}. If Q_{4} = ∅ let h′_{2} be another new element, and otherwise let h′_{2} = h_{i} where Q_{4} = {v_{i}}. If V_{0} ≠ ∅ let F′_{3} be another new element. Then • V (H′) = V (H) ∪ {h′_{1}, h′_{2}}, and E(H′) = (E(H) \ {F }) ∪ {F′_{1}, F′_{2}, F′_{3}} if F′_{3} exists, and otherwise

E(H′) = (E(H) \ {F }) ∪ {F′_{1}, F′_{2}};

• for F_{0} ∈ E(H) \ {F } and each h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H;

• for F_{0} ∈ E(H) \ {F }, F_{0} is not incident with any of h′_{1}, h′_{2} that are not in V (H);

• for j = 1, 2, F′_{j} is incident with h ∈ V (H′) if and only if h ∈ Q_{j} ∪ {h′_{1}, h′_{2}};

• if F′_{3} exists, F′_{3} is incident with h′_{1}, h′_{2} and with no other member of V (H′);

• for all F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• for j = 1, 2, η′(F′_{j}) = W_{j} \ Q_{j};

• for j = 1, 2 and h ∈ P_{j}, η′(F′_{j}, h) = η(F, h);

• for j = 1, 2, η′(F′_{j}, h′_{1}) = C_{j}, and η′(F′_{j}, h′_{2}) = D_{j}; and

• if F′_{3} exists, η′(F′_{3}) = η′(F′_{3}, h′_{1}) = η′(F′_{3}, h′_{2}) = V_{0}. Since C_{1}, C_{2}, D_{1}, D_{2} are all nonempty, we can prove as before that (H′, η′) is a strip-structure of G, contradicting the maximality of (H, η). This proves (3).

(4) J does not admit a biclique. For suppose it does; then there is a partition V_{1}, V_{2}, V_{3}, V_{4} of V (J), such that

• V_{1} ≠ ∅, and V_{1} ∪ V_{2}, V_{1} ∪ V_{3} are strong cliques

• V_{1} is strongly anticomplete to V_{4}

• either |V_{1}| ≥ 2, or V_{2} ∪ V_{3} is not a strong clique

• V_{2} ∪ V_{3} ∪ V_{4} is not strongly stable

• if v_{2} ∈ V_{2} and v_{3} ∈ V_{3} are adjacent then they have the same neighbours in V_{4} and the same

antineighbours in V_{4}. Choose such V_{1}, …, V_{4} with V_{1} maximal. Suppose first that V_{2} ∪ V_{3} is a strong clique. Then |V_{1}| ≥ 2 by hypothesis, and so J admits a pseudo-1-join, since V_{1} and V_{2} ∪V_{3} ∪V_{4} are both not strongly stable, a contradiction. Thus V_{2} ∪ V_{3} is not a strong clique, and in particular, V_{2}, V_{3} are both nonempty.

For i = 1, …, 4, let Q_{i} = V_{i} ∩ Z. Hence Q_{1} = ∅. Morover, not both Q_{2}, Q_{3} are nonempty, since (H, η) is purified; and so we may assume that Q_{3} = ∅. Also |Q_{2}| ≤ 1 since Z is stable. Define (H′, η′) as follows. Let F′, h′_{1} be new elements. If Q_{2} = ∅ let h′_{2} be another new element, and otherwise let h′_{2} = h_{i} where Q_{2} = {v_{i}}. Then

• E(H′) = E(H) ∪ {F′} and V (H′) = V (H) ∪ {h′_{1}, h′_{2}};

• for F_{0} ∈ E(H) and each h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H; • for F_{0} ∈ E(H) \ {F }, F_{0} is not incident with h′_{1}, and not with h′_{2} if h′_{2} ∉ V (H);

• F is incident with h′_{1}, h′_{2}; and F′ is incident with h′_{1}, h′_{2} and with no other member of V (H′);

• for all F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• η′(F) = (V_{2} ∪ V_{3} ∪ V_{4}) \ (Q_{2} ∪ Q_{4}), and η(F′) = V_{1};

• η′(F, h′_{1}) = V_{3}, η′(F, h′_{2}) = V_{2} \ Q_{2}, and for all other h ∈ V (H′) incident with F, η′(F, h) = η(F, h);

• η′(F′, h′_{1}) = η′(F′, h′_{2}) = V_{1}.

We claim that (H′, η′) is a strip-structure of G, and since η′(F′) ≠ ∅ and η′(F) ≠ ∅ (since V_{2} ∪V_{3} ∪V_{4} is not strongly stable), it suffices to show that the family

(η′(F, h) : h is incident with F in H′)

is a circus in G|η′(F). Since (η(F, h) : h ∈ \overline{F}) is a circus in η(F) (where \overline{F} denotes the set of vertices of H incident with F in H), and η′(F, h′_{1}) ∩ η′(F, h′_{2}) = ∅, it suffices to check that:

• for j = 1, 2 and x ∈ η′(F, h′_{j}), the neighbours of x in η′(F) \ η′(F, h′_{j}) are a strong clique

• for j = 1, 2 and h ∈ \overline{F} \ \{h′_{1}, h′_{2}\}, if x ∈ η′(F, h) ∩ η′(F, h′_{j}) then x is strongly anticomplete to η′(F) \ (η′(F, h) ∪ η′(F, h′_{j}))

• for j = 1, 2, if x ∈ η′(F, h′_{j}) then x belongs to η′(F, h) for at most one h ∈ \overline{F} \ \{h′_{1}, h′_{2}\}.

The third assertion is clear since (H, η) is purified. For the first assertion, let x ∈ η′(F, h′_{j}) where j ∈ {1, 2}. Then x has a neighbour in V_{1}, and this neighbour is anticomplete to V_{4}, and so the set of neighbours of x in V_{4} is a strong clique. Let {j, k} = {1, 2}. If y ∈ V_{k} is adjacent to x, then x, y have the same neighbours in V_{4}, from the definition of a biclique, and so the set of neighbours of x in V_{k} ∪ V_{4} is a strong clique. This proves the first assertion.

Now let us check the second assertion. First let j = 1; then x ∈ V_{3}∩η(F, h) where h ∈ \overline{F} \\{h′_{1}, h′_{2}\}; h = h_{1} say. Then v_{1} ∈ V_{4}, and x is adjacent in J to v_{1}, and v_{1} is anticomplete to V_{1}. Since x has a neighbour in V_{1}, and its neighbours in η(F) \ η(F, h) are a strong clique, it follows that every neighbour of x in V_{4} is in η(F, h). From the final condition in the definition of a biclique, all neighbours of x in V_{2} are adjacent in J to v_{1}, and therefore belong to η(F, h). Thus the second assertion holds when j = 1. Now let j = 2. If h′_{2} ∉ V (H), then the same proof applies, exchanging h′_{1}, h′_{2}; so we assume that h′_{2} ∈ V (H). But then x is strongly anticomplete to η(F) \ (η(F, h) ∪ η(F, h′_{2})), since (η(F, h) : h ∈ \overline{F}) is a circus in η(F), and again the second assertion holds. Hence (H′, η′) is a strip-structure of G, contradicting the maximality of (H, η). This proves (4).

(5) Z is the set of all simplicial vertices of J.

For suppose that some v ∈ V (J) \ Z is simplicial. Suppose first that v is adjacent in J to one of v_{1}, …, v_{k}, say to v_{1}. Since v_{1}, v are both simplicial in J, they are twins; let N be the set of vertices of J different from v, v_{1} and adjacent to v. Then {v, v_{1}} and N are strong cliques, and {v, v_{1}} is strongly complete to N and strongly anticomplete to V (J)\(N ∪{v, v_{1}}). Since ({v, v_{1}}, V (J)\{v, v_{1}}) is not a pseudo-1-join by (2), it follows that V (J)\{v, v_{1}} is strongly stable; in particular, {v, v_{1}}∪N = V (J), since any vertex not in {v, v_{1}} ∪ N would have no neighbours and J would admit a 0-join; and so V (J) is a strong clique, a contradiction.

This proves that v is antiadjacent to v_{1}, …, v_{k}. Let N be the set of neighbours of v in J. Define (H′, η′) as follows. Let F′, h′ be new elements; then

• V (H′) = V (H) ∪ {h′} and E(H′) = E(H) ∪ {F′};

• for F_{0} ∈ E(H) and each h ∈ V (H), F_{0} is incident with h in H′ if and only if they are incident in H;

• F′ is incident with h′ and with no other vertex of H′;

• for F_{0} ∈ E(H), F_{0} is incident with h′ if and only if F_{0} = F;

• for all F_{0} ∈ E(H) \ \{F \}, η′(F_{0}) = η(F_{0}) and η′(F_{0}, h) = η(F_{0}, h) for all h ∈ \overline{F_{0}};

• η′(F) = η(F) \ {v}, and η(F′) = {v};

• η′(F, h′) = N, and for all other h ∈ V (H′) incident with F, η′(F, h) = η(F, h);

• η′(F′, h′) = {v}.

Note that η(F) ≠ {v} since V (J) is not a strong clique, and so η′(F) ≠ ∅. It follows that (H′, η′) is a strip-structure of G, contrary to the optimality of (H, η). This proves (5).

Choose a stripe (J′, Z′) with |V (J′)| minimum such that (J, Z) is a thickening of (J′, Z′), and let X_{v} (v ∈ V (J′)) be the corresponding subsets. Hence no two vertices in V (J′) \ Z′ are twins in J′, and there is no W-join (A, B) in J′ with Z′ ∩ A, Z′ ∩ B = ∅. Moreover, by (1) – (4) it follows that J′ does not admit a 0-join, a pseudo-1-join, a pseudo-2-join, or a biclique, since J does not. If v is a simplicial vertex of J′ with v ∉ Z′, then every vertex in X_{v} is simplicial in J, contrary to (5). Thus Z′ is the set of all simplicial vertices of J′. This proves that (J, Z) is a thickening of an unbreakable stripe, and so completes the proof of 9.1.

Thus, in order to prove 7.2 it would suffice to identify all the unbreakable stripes and check that they are consistent with 7.2, and that is the goal of the remainder of the paper.

10 Preliminaries on unbreakable stripes

We begin with some useful lemmas about unbreakable stripes. First, we have

10.1 If (G, Z) is an unbreakable stripe, then G does not admit twins.

Proof. Suppose that u, v are twins of G; then one of u, v ∈ Z since (G, Z) is unbreakable. Let u ∈ Z say; thus u is simplicial. Since u, v are twins it follows that v is simplicial, and therefore v ∈ Z since Z is the set of all simplicial vertices of G. But then Z is not stable, a contradiction. This proves 10.1.

Second, we observe:

10.2 Let (G, Z) be an unbreakable stripe with |V (G)| > 2, such that V (G) is the union of two strong cliques. Then |V (G)| ≤ 4 and (G, Z) ∈ Z_{1} ∪ Z_{6}.

Proof. By 10.1, G does not admit twins. Let A, B be strong cliques in G with A ∪ B = V (G), chosen with A ∩ B maximal. Then A, B ≠ V (G) since G does not admit twins. Since (A, B \ A) is a homogeneous pair, and one of |A|, |B \ A| > 1, and (G, Z) is unbreakable, it follows that Z ≠ ∅. Any two members of A ∩ B are twins, so |A ∩ B| ≤ 1. From the maximality of A ∩ B, every member of A \ B has an antineighbour in B \ A, and vice versa. Therefore no vertex in A ∩ B is simplicial, and so Z ⊆ V (G) \ (A ∩ B). Suppose that A ∩ B ≠ ∅. Then since the four sets A ∩ B, A \ B, B \ A, ∅ do not form a biclique, it follows that (A \ B) ∪ (B \ A) is strongly stable. Since A is a strong clique, it follows that |A \ B| = 1, and similarly |B \ A| = 1. Then |V (G)| = 3, and |Z| = 1 (since no two members of Z have a common neighbour), and (G, Z) ∈ Z_{6}. Thus we may assume that A ∩ B = ∅. Let a ∈ Z, say a ∈ A. If a has a neighbour b ∈ B, then since a is simplicial, it follows that b is strongly complete to A, contrary to the maximality of A ∩ B. So a is strongly anticomplete to B, and so (A \ {a}, B) is a homogeneous pair. If Z = {a} then since (G, Z) is unbreakable, it follows that |A| ≤ 2 and |B| = 1 and again (G, Z) ∈ Z_{6}. We may therefore assume that there exists b ∈ Z with b ≠ a. Since Z is strongly stable, it follows that b ∈ B, and as before b is strongly anticomplete to A, and |Z| = 2. Since (A \ {a}, B \ {b}) is a homogeneous pair, it follows that |A|, |B| ≤ 2, and (G, Z) ∈ Z_{1}. This proves 10.2.

And third, we have:

10.3 Let (G, Z) be an unbreakable stripe with |V (G)| > 2. If G is a thickening of a line trigraph then V (G) is the union of two strong cliques and therefore (G, Z) ∈ Z_{1} ∪ Z_{6}.

Proof. Let G′ be a line trigraph of some graph H say, and let G be a thickening of G′; let X_{v} (v ∈ V (G′) be the corresponding subsets of V (G). Since G admits no 0-join, it follows that H is connected. Suppose first that some vertex h of H has degree two; let e = hx and f = hy be the two edges of H incident with h. In particular, if some two vertices of G′ are semiadjacent, choose h such that e, f are semiadjacent in G′. Let P be the set of all edges of H incident with x and with neither of h, y, and similarly let Q be the set of all edges of H incident with y and with neither of h, x. Write A_{1} = X_{e}, B_{1} = X_{f}, A_{2} = ⋃_{p∈P} X_{p}, and B_{2} = ⋃_{q∈Q} X_{q}. Let V_{1} = A_{1} ∪ B_{1}, and V_{0} = X_{t} if there is an edge t of H incident with x, y, and otherwise V_{0} = ∅. Let V_{2} = V (G) \ (V_{1} ∪ V_{0}). We claim that A_{1} ∪ A_{2} ∪ V_{0} is a strong clique. Suppose not; then x has degree two in H (from the definitions of a line trigraph and thickening), and e is semiadjacent in G′ to some edge of H incident with x. Consequently e is not semiadjacent to f in G′, since F (G′) is a matching, contrary to our choice of h. This proves that A_{1} ∪ A_{2} ∪ V_{0} and similarly B_{1} ∪ B_{2} ∪ V_{0} are strong cliques. Since e, f are both incident with x in H, it follows that e, f are adjacent in G′, and therefore A ∪ B is not strongly stable in G. Since G does not admit a pseudo-2-join, it follows that V_{2} is strongly stable; but then V_{2} = A_{2} ∪ B_{2}, since G does not admit a 0-join, and therefore V (G) is the union of two strong cliques and the result follows from 10.2.

We may assume therefore that no vertex of H has degree two; and so no pair of vertices of G′ are semiadjacent. Consequently no pair of vertices of G are semiadjacent. If every edge of H is incident with a vertex of degree one, then since H is connected, it follows that some vertex of H is incident with every edge of H, and so G′ and hence G is a strong clique and the result follows from 10.2.

Thus we may assume that there is an edge e = uv of H such that u, v both have degree at least three in H. Let P, Q be the sets of edges of H incident with u and not v, and with v and not u, respectively. Let V_{1} = X_{e}, V_{2} = ⋃_{p∈P} X_{p}, V_{3} = ⋃_{q∈Q} X_{q}, and V_{4} = V (G) \ (V_{1} ∪ V_{2} ∪ V_{3}). Then V_{1} ≠ ∅, and V_{1} ∪ V_{2}, V_{1} ∪ V_{3} are strong cliques; V_{1} is strongly anticomplete to V_{4}; since |P | ≥ 2, V_{2} is not strongly stable; if v_{2} ∈ V_{2} and v_{3} ∈ V_{3} are adjacent then they belong to sets X_{p}, X_{q} where p ∈ P and q ∈ Q share an end in H, and therefore v_{2}, v_{3} have the same neighbours in V_{4}; and since there exist p ∈ P and q ∈ Q with no common end in H, it follows that V_{2} ∪ V_{3} is not a strong clique. Consequently G admits a biclique, a contradiction. This proves 10.3.

We also need the following observation:

10.4 For every claw-free trigraph G, if G does not admit a 0-join, 1-join or generalized 2-join, then either G is a thickening of an indecomposable member of S_{0} ∪ ⋯ ∪ S_{7}, or G admits a hex-join.

Proof. We proceed by induction on |V (G)|. Suppose first that G contains twins u, v, and let G′ = G \ {v}. Then G′ is claw-free, and does not admit a 0-join, 1-join or generalized 2-join (for adding a twin to a trigraph that admits a 0-,1- or generalized 2-join produces a trigraph that still admits the same decomposition). From the inductive hypothesis, either G′ is a thickening of a member of ∈ S_{0} ∪ ⋯ ∪ S_{7} (and therefore so is G, by 6.1), or G′ admits a hex-join (and therefore so does G). Therefore we may assume that G does not admit twins.

Suppose that G admits a W-join (A, B). Choose a ∈ A and b ∈ B, and let G′ be obtained from G by deleting (A \ {a}) ∪ (B \ {b}) and making a, b semiadjacent. Then G′ is claw-free and does not admit a 0-join, 1-join or generalized 2-join, (for if say G′ admits a generalized 2-join (V_{0}, V_{1}, V_{2}), then since a, b are semiadjacent, they do not belong to V_{0}, and belong to the same one of V_{1}, V_{2}, and restoring A, B in place of a, b yields a generalized 2-join in G, a contradiction). From the inductive hypothesis, either G′ is a thickening of a member of S_{0} ∪⋯∪S_{7} (and therefore so is G, by 6.1), or G′ admits a hex-join (and therefore so does G). Consequently we may assume that G does not admit a W-join, and hence is indecomposable. But then the result holds by 5.1. This proves 10.4.

Our approach to 7.2 is via the following.

10.5 Let (G, Z) be an unbreakable stripe. Then either

• |V (G)| ≤ 4 and V (G) is the union of two strong cliques, or

• G is a thickening of an indecomposable member of S_{i} for some i ∈ {1, …, 7}, or

• G admits a hex-join.

Proof. Choose a trigraph G′ with |V (G′)| minimum such that G is a thickening of G′. Suppose first that G′ is indecomposable. By 5.1, G′ ∈ S_{i} for some i ∈ {0, …, 7}. If i ≥ 1 then the theorem holds, so we may assume that i = 0. By 10.2 and 10.3, |V (G)| ≤ 4 and V (G) is the union of two strong cliques, and the theorem holds.

Thus we may assume that G′ is not indecomposable. Since (G, Z) is unbreakable, G does not admit a 0-join, 1-join or generalized 2-join, and hence neither does G′. From the minimality of |V (G′)| and 6.1, G′ does not admit twins or a W-join. Thus G′ admits a hex-join, and therefore so does G. This proves 10.5.

11 Simplicial vertices in indecomposable trigraphs

We need to study the simplicial vertices of indecomposable trigraphs in S_{i} where 1 ≤ i ≤ 7; and it is convenient to study which vertices are “near-simplicial”, at the same time. Let us say a vertex of a trigraph G is near-simplicial if v is semiadjacent to some vertex, and N^{∗} is a strong clique, where N^{∗} is the set of strong neighbours of v. The following answers the question above, except for S_{3}, which will be handled in a different way later.

11.1 Let G ∈ S_{i} for some i ∈ {1, 2, 4, 5, 6, 7}, and suppose that G is indecomposable, and V (G) is not expressible as the union of two strong cliques. Let z be a simplicial or near-simplicial vertex of G.

• If z is simplicial, let Z be the set of all simplicial vertices of G; then |Z| ≤ 2 and (G, Z) ∈ Z_{j} for some j ∈ {2, 5, 7, 8, 9}.

• If z ∈ V (G) is near-simplicial, semiadjacent to z′ say, let Z = {z, z′}; then (G′, Z) ∈ Z_{2} ∪ Z_{5}, where G′ is the trigraph obtained from G by making z, z′ strongly antiadjacent.

Proof. First, let v_{0}, …, v_{11} and G_{0}, G_{1}, G_{2} be as in the definition of S_{1}. Then no vertex of G_{0}, G_{1} is simplicial or near-simplicial. Moreover, each of v_{0}, …, v_{9} has two strong neighbours in G (and therefore in G_{2}) different from v_{10}, v_{11}, that are antiadjacent; and consequently no vertex of G_{2} is simplicial or near-simplicial. Hence G ∉ S_{1}.

Next, suppose that G ∈ S_{2}, and let H, v_{1}, …, v_{13} and X ⊆ {v_{7}, v_{11}, v_{12}, v_{13}} be as in the definition of S_{2} (where G = H \ X). From the hole v_{1}- ⋯ -v_{6}-v_{1}, it follows that no vertex is simplicial or nearsimplicial except possibly v_{7} or v_{8}. Thus Z ⊆ {v_{7}, v_{8}}. If z is simplicial then (G, Z) ∈ Z_{5}, and if say z = v_{8} ∈ Z is near-simplicial then z′ = v_{7} ∉ X and v_{7}, v_{8} are semiadjacent, and (G′, {v_{7}, v_{8}}) ∈ Z_{5}, where G′ is obtained by making v_{7}, v_{8} strongly antiadjacent.

Next suppose that G ∈ S_{4}. Let H, J(H) and h_{1}, …, h_{7} be as in the definition of S_{4}, and let w be the vertex of G that is not an edge of H. The edges of the cycle h_{1}- ⋯ -h_{5}-h_{1} of H form a hole in G, and so w is not simplicial or near-simplicial in G, and nor is any edge of H with both ends in {h_{1}, …, h_{5}}. The edge h_{i}h_{6} (where 1 ≤ i ≤ 5) is strongly adjacent in G to the edges h_{6}h_{7} and h_{i}h_{i+1}, and so is not simplicial or near-simplicial in G. Thus z is the edge h_{6}h_{7}, and z is simplicial and Z = {z}, and (G, Z) ∈ Z_{7}.

Next suppose that G ∈ S_{5}. Let n, A, B, C, D, X etc. be as in the definition of S_{5}. We may assume (by decreasing n) that X contains at most two of a_{i}, b_{i}, c_{i} for 1 ≤ i ≤ n. Since d_{1}, d_{3} are antiadjacent, it follows that no vertex in A is simplicial or near-simplicial, and similarly none in B. Since A \ X is not strongly complete to B \ X, it follows that d_{1}, d_{2} are not simplicial or near-simplicial; and since d_{2}, d_{5} are antiadjacent it follows that d_{3}, d_{4} are not simplicial or near-simplicial. Suppose that c_{1} is simplicial or near-simplicial in G, and in particular c_{1} ∉ X. Since c_{1} is strongly complete to (A \ {a_{1}}) ∩ X and to (B \ {b_{1}}) ∩ X, and A \ X is not complete to B \ X, we may assume that a_{1}, b_{2} ∉ X. Since c_{2}, b_{2} are antiadjacent, c_{2} ∈ X. If n ≥ 3 then a_{3} ∈ X (since a_{3}, b_{2} are antiadjacent), so a_{2} ∉ X (since |A ∩ X| ≤ 1), and hence b_{3} ∈ X (since b_{3}, a_{2} are antiadjacent), and so c_{3} ∉ X (since X contains at most two of a_{3}, b_{3}, c_{3}), and therefore ({d_{2}}, {d_{1}, c_{3}}) is a homogeneous pair, a contradiction. Thus n = 2 and C \ X = {c_{1}}. Since C \ X is not strongly complete to B \ X, it follows that b_{1} ∉ X, and so c_{1} is strongly antiadjacent to a_{1}, b_{1}. Hence c_{1} is simplicial, and no vertex of G is near-simplicial, and therefore Z = {c_{1}, d_{5}}; but then (G, Z) ∈ Z_{2}. Thus we may assume that no member of C is simplicial or near-simplicial, and so Z = {d_{5}} and (G, Z) ∈ Z_{8}.

Next suppose that G ∈ S_{6}, and let H, a_{0}, b_{0}, A, B, C, X etc. be as in the definition of S_{6}. Thus G = H \ X. Since |C \ X| ≥ 2 and every member of A \ {a_{0}} has at most one antineighbour in C, it follows that no member of A \ {a_{0}} is simplicial or near-simplicial in G, and similarly for B \ {b_{0}}. Suppose that c_{1} ∈ C \ X is simplicial or near-simplicial in G. Since |C \ X| ≥ 2, we may assume that c_{2} ∈ C \ X. Since c_{1} is strongly adjacent in H to c_{2}, a_{2}, b_{2}, and the strong neighbours of c_{1} in G are a strong clique, it follows that a_{2}, b_{2} ∈ X. Hence any two members of C \ (X ∪ {c_{1}}) are twins in G, and so |C \ X| = {c_{1}, c_{2}}, since G is indecomposable. Let A′ = A \ (X ∪ {a_{0}, a_{1}}), and B′ = B \ (X ∪ {b_{0}, b_{1}}). Since G does not admits a 1-join, it follows that A′ ∪ B′ ≠ ∅. But

{a_{0}, a_{1}} \ X, {b_{0}, b_{1}} \ X, {c_{1}, c_{2}}, A′, B′, ∅

are pairwise disjoint strong cliques, with union V (G), and since A′ is strongly complete to {a_{0}, a_{1}}\X and to {c_{1}, c_{2}}, and strongly anticomplete to {b_{0}, b_{1}} \ X, and similarly for B′, it follows that G is the hex-join of G|(A′ ∪ B′) and G \ (A′ ∪ B′), a contradiction. Thus no member of C \ X is simplicial or near-simplicial in G, and so z ∈ {a_{0}, b_{0}}. If z is simplicial then a_{0}, b_{0} are strongly antiadjacent, and Z = {a_{0}, b_{0}}, and (G, Z) ∈ Z_{2}; and if z is near-simplicial, then a_{0}, b_{0} are semiadjacent, and (G′, {a_{0}, b_{0}}) ∈ Z_{2}, where G′ is obtained from G by making a_{0}, b_{0} strongly antiadjacent.

Finally, suppose that G ∈ S_{7}. Let z ∈ Z, and let D, D^{∗} be the sets of neighbours and strong neighbours of z respectively; then D^{∗} is a strong clique. Since G is antiprismatic, every vertex in V (G)\(D∪{z}) has at most one antineighbour in the same set; let V (G)\(D∪{z}) = A∪B∪C, where A, B, C are disjoint, A = {a_{1}, …, a_{n}}, B = {b_{1}, …, b_{n}}, and for 1 ≤ i ≤ n a_{i}, b_{i} are antiadjacent, and otherwise every two members of A ∪ B ∪ C are strongly adjacent. Suppose first that z is nearsimplicial, semiadjacent to z′ say; then Z = {z, z′} and D \ D^{∗} = {z′}. If n > 0 then {z, z′, a_{1}, b_{1}} is a claw; so n = 0. Let N be the set of all neighbours of z′ different from z. Then the following sets are six strong cliques, pairwise disjoint and with union V (G):

{z}, {z′}, C \ N, C ∩ N, D \ N, D ∩ N.

Moreover z is strongly complete to D \ N, D ∩ N and strongly anticomplete to C ∩ N; z′ is strongly complete to C ∩ N, D ∩ N and strongly anticomplete to D \ N; and C \ N is strongly complete to C ∩ N, D \ N (the latter since G is antiprismatic) and strongly anticomplete to D ∩ N (since {z, z′} ∪ (C \ N) ∪ (D ∩ N) includes no claw). Since G does not admit a hex-join, we deduce that C ∩ N, D \ N, D ∩ N are all empty. Since G does not admit a 0-join, it follows that C \ N = ∅, and so V (G) = {z, z′} and V (G) is the union of two strong cliques, a contradiction. This proves that z is simplicial, and so D = D^{∗}. Since V (G) is not the union of the two strong cliques C, D ∪ {v}, it follows that n > 0. For 1 ≤ i ≤ n and each d ∈ D, since {d, z, a_{i}, b_{i}} is not a claw it follows that d is strongly antiadjacent to one of a_{i}, b_{i}, and strongly adjacent to the other and to z since G is antiprismatic. Thus (G, {z}) ∈ Z_{9}. Every vertex in D is strongly adjacent to z and to one of a_{1}, b_{1}, and so is not simplicial or near-simplicial. No vertex in C is simplicial or near-simplicial since every such vertex is strongly adjacent to a_{1}, b_{1} and they are antiadjacent. Suppose that say a_{1} is simplicial or near-simplicial. Then n = 1, since if n > 1 then a_{1} would be strongly adjacent to both a_{2}, b_{2}. Let P be the set of vertices in D adjacent to a_{1}, and Q = D \ P; then D ≠ ∅ (since G does not admit a 0-join), and the six cliques

P, Q, C, {b_{1}}, {a_{1}}, {z}

show that G is expressible as a hex-join of G|{z, a_{1}, b_{1}} and G|(C ∪ D), a contradiction. Thus no vertex except z is simplicial or near-simplicial, so Z = {z} and (G, Z) ∈ Z_{9}. This proves 11.1.

12 Unbreakable thickenings of basic trigraphs

Our current objective is to catalogue all the unbreakable stripes (G, Z) where G is a thickening of a member of one of S_{1}, …, S_{7}. We begin with:

12.1 Let (G, Z) be an unbreakable stripe, such that Z ≠ ∅. If G is a thickening of a long circular interval trigraph then (G, Z) ∈ Z_{1} ∪ Z_{6}.

Proof. Let G be a thickening of a long circular interval trigraph G′, and let X_{v} (v ∈ V (G′)) be the corresponding subsets of V (G). By 10.1, G does not admit twins. By theorem 2.1 of [3], we may choose G′ such that:

(1) For every semiadjacent pair u, v of vertices of G′, every vertex in X_{u} has a neighbour and an antineighbour in X_{v} and vice versa.

Let Z = {z_{1}, …, z_{t}}, and for 1 ≤ i ≤ t let z′_{i} ∈ V (G′) such that z_{i} ∈ X_{z′_{i}}. The vertices z′_{1}, …, z′_{t} are all distinct since Z is stable in G; let Z′ = {z′_{1}, …, z′_{t}}.

(2) |X_{v}| = 1 for all v ∈ V (G′).

For suppose that |X_{v}| > 1 for some v ∈ V (G′). Since G does not admit twins, it follows that some vertex in V (G) \ X_{v} is neither strongly complete nor strongly anticomplete to X_{v}; and hence v is semiadjacent in G′ to some u ∈ V (G′). If there exists z ∈ Z ∩ X_{u}, then by (1) z has a neighbour y ∈ X_{v}, and by (1) again y has an antineighbour x ∈ X_{u}; but then x, y are both adjacent to z, and antiadjacent to each other, contradicting that z is simplicial. Thus Z ∩ X_{u} = ∅, and similarly Z ∩ X_{v} = ∅. But (X_{u}, X_{v}) is a W-join in G, contradicting that (G, Z) is unbreakable. This proves (2).

From (2), it follows that G is isomorphic to G′, and in particular, G is a long circular interval trigraph; let Σ and F_{1}, …, F_{k} be as in the definition of S_{3}. Let the vertices of G be v_{1}, …, v_{n} in cyclic order in Σ. We may assume that |Z| ≥ 2, for otherwise (G, Z) ∈ Z_{6} and the theorem holds. Thus we may assume that v_{1}, v_{i} ∈ Z, where 2 ≤ i ≤ n. Suppose first that v_{1}, v_{n} are antiadjacent, and therefore strongly antiadjacent (since v_{1} ∈ Z). Then G is a linear interval trigraph with vertices v_{1}, …, v_{n} in order. If |Z| = 2 and i = n then (G, Z) ∈ Z_{1}, so we may assume that i < n. For 2 ≤ j ≤ n, since G does not admit a 0-join it follows that {v_{1}, …, v_{j−1}} is not strongly anticomplete to {v_{j}, …, v_{n}}, and so v_{j−1}, v_{j} are adjacent for 2 ≤ j ≤ n. In particular v_{1}, v_{2} are adjacent, and so i ≥ 3. Choose h, j with 1 ≤ h < i < j ≤ n minimum and maximum such that v_{i} is adjacent to v_{h}, v_{j}. Thus {v_{1}, …, v_{h−1}} is strongly anticomplete to {v_{i}, …, v_{n}} (since v_{h−1} is strongly antiadjacent to v_{i}), and similarly {v_{h}, …, v_{i−1}} is strongly anticomplete to {v_{j+1}, …, v_{n}}, and {v_{h}, …, v_{j}} is a strong clique (since v_{i} is simplicial). Hence G admits a pseudo-1-join, a contradiction. Thus if v_{1}, v_{n} are antiadjacent then the theorem holds. We may assume therefore that v_{1}, v_{n} are strongly adjacent, and similarly v_{1}, v_{2} are strongly adjacent (and so 3 ≤ i ≤ n − 1), and v_{i} is strongly adjacent to v_{i−1}, v_{i+1}. Choose g with 1 < g < i maximum such that v_{1}, v_{g} are adjacent, and m with i < m ≤ n minimum such that v_{1}, v_{m} are adjacent. Choose h, j with 1 < h < i < j ≤ n minimum and maximum such that v_{i} is adjacent to v_{h}, v_{j}. Since no vertex of G′ is adjacent to both v_{1}, v_{i}, it follows that g < h and similarly j < m. Let V_{1} = {v_{1}, …, v_{i−1}} and V_{2} = {v_{i}, …, v_{n}}. Since v_{1}, v_{2} are adjacent, V_{1} is not strongly stable, and similarly V_{2} is not strongly stable. For x_{1} ∈ V_{1} and x_{2} ∈ V_{2}, x_{1}, x_{2} are strongly adjacent if either x_{1} ∈ {v_{1}, …, v_{g}} and x_{2} ∈ {v_{m}, …, v_{n}}, or x_{1} ∈ {v_{h}, …, v_{i−1}} and x_{2} ∈ {v_{i}, …, v_{j}}, and otherwise x_{1}, x_{2} are strongly antiadjacent. Hence G admits a pseudo-2-join, a contradiction. This proves 12.1.

Now we can prove the main result of this section, the following.

12.2 Let (G, Z) be an unbreakable stripe with Z ≠ ∅. Suppose that G is a thickening of an indecomposable member of S_{i}, where i ∈ {1, …, 7}. Then (G, Z) ∈ Z_{0}.

Proof. Let G be a thickening of G′, where G′ ∈ S_{i} is indecomposable, and let the corresponding subsets of V (G) be X_{v} (v ∈ V (G′)). If V (G′) is the union of two strong cliques, then the same is true for G and the theorem holds by 10.2. We assume that V (G′) is not so expressible. By 12.1, we may assume that i ≠ 3.

(1) |X_{v}| = 1 for all v ∈ V (G′).

For suppose not; then since G does not admit twins, we may choose u, v ∈ V (G′), semiadjacent in G′, such that (X_{u}, X_{v}) is a W-join in G′. Since (G, Z) is unbreakable we may assume that there exists z ∈ Z ∩ X_{u}, and so u is near-simplicial in G′. Since G′ is indecomposable, 11.1 implies that u, v are both near-simplicial in G′, and no vertex of G′ is adjacent to both u, v. Since setting V_{1} = X_{u} ∪X_{v}, V_{0} = ∅, and V_{2} = V (G)\V_{1} does not define a pseudo-2-join in G, and V_{1} is not strongly stable in G (from the definition of “thickening”, since u, v are semiadjacent in G′), it follows that V_{2} is strongly stable in G. Since G does not admit a 0-join, it follows that every vertex in V_{2} has a neighbour in V_{1}. But then V (G) is the union of two strong cliques, a contradiction. This proves (1).

From (1), G′ is isomorphic to G, and so G ∈ S_{i}. By 11.1 applied to (G, Z), it follows that (G, Z) belongs to Z_{j} for some j ∈ {2, 5, 7, 8, 9}. This proves 12.2.

13 Unbreakable stripes with hex-joins

It remains to catalogue the unbreakable stripes (G, Z) such that G admits a hex-join. We begin with:

13.1 Let (G, Z) be an unbreakable stripe such that G admits a hex-join. Then |Z| ≤ 2.

Proof. Suppose that |Z| ≥ 3, and let z_{1}, z_{2}, z_{3} ∈ Z be distinct. Let G be a hex-join of G|V_{1} and G|V_{2}. From the symmetry we may assume that at least two of z_{1}, z_{2}, z_{3} belong to V_{1}. Since {z_{1}, z_{2}, z_{3}} is a triad and every triad is a subset of one of V_{1}, V_{2}, it follows that z_{3} ∈ V_{1}. Let v ∈ V_{2}. Then v is antiadjacent to at least two of z_{1}, z_{2}, z_{3}, since (G, Z) is a stripe; and so v therefore belongs to a triad that contains two of z_{1}, z_{2}, z_{3}, and consequently contains a vertex of V_{1}. Hence this triad is not a subset of either of V_{1}, V_{2}, a contradiction. This proves 13.1.

13.2 Let (G, Z) be an unbreakable stripe with |Z| = 2, such that V (G) is the union of three strong cliques. Then (G, Z) ∈ Z_{1} ∪ Z_{2} ∪ Z_{3} ∪ Z_{4}.

Proof. We may assume that V (G) is not the union of two strong cliques, for otherwise the result follows from 10.2. ((G, Z) ∉ Z_{6} since |Z| = 2.) Let Z = {z_{1}, z_{2}}.

(1) The set of vertices in G antiadjacent to both z_{1}, z_{2} is a strong clique of G.

For there are three strong cliques with union V (G), and since z_{1}, z_{2} are antiadjacent, only one of these three cliques does not contain either of z_{1}, z_{2}; and this clique contains all vertices antiadjacent to them both. This proves (1).

(2) There is no W-join (X, Y) in G with z_{1} ∈ X and z_{2} ∈ Y.

For suppose that (A_{1}, B_{1}) is a W-join with z_{1} ∈ A_{1} and z_{2} ∈ B_{1}. Let V_{1} = A_{1}∪B_{1} and V_{2} = V (G)\V_{1}. Let A_{2}, B_{2} be the sets of vertices in V_{2} strongly complete to A_{1} and strongly complete to B_{1} respectively. Since no vertex is adjacent to both z_{1}, z_{2}, it follows that A_{2} ∩ B_{2} = ∅. Every vertex in V_{2} with a neighbour in A_{1} belongs to A_{2}, and similarly for B_{1}; and A_{1} ∪ A_{2}, B_{1} ∪ B_{2} are strong cliques since z_{1}, z_{2} are simplicial. Since (A_{1}, B_{1}) is a W-join and G does not admit a pseudo-2-join, it follows that V_{2} is strongly stable, and so V_{2} = A_{2} ∪ B_{2} since G admits no 0-join. But then V (G) is the union of two strong cliques, a contradiction. This proves (2).

Let G′ be the trigraph obtained from G by making z_{1}, z_{2} semiadjacent. Since z_{1}, z_{2} are simplicial in G, it follows that G′ is claw-free. If (X, Y) is a W-join of G′, then since z_{1}, z_{2} are semiadjacent, it follows that z_{1} ∈ X if and only if z_{2} ∈ Y, and so by (2), and since (G, Z) is unbreakable, G′ does not admit a W-join. By theorem 11.1 of [4] applied to G′, z_{1}, z_{2}, we deduce that one of the six outcomes of that theorem hold. The first is contrary to what we just showed; the second implies that (G, Z) ∈ Z_{1}; the third contradicts 10.3; the fourth implies that (G, Z) ∈ Z_{3}; since G′ does not admit a generalized 2-join, the fifth implies that (G, Z) ∈ Z_{4}; and the sixth implies that (G, Z) ∈ Z_{2}. This proves 13.2.

13.3 Let (G, Z) be an unbreakable stripe with |Z| = 1, such that V (G) is the union of three strong cliques. Then (G, Z) ∈ Z_{0}.

Proof. We proceed by induction on |V (G)|. Let Z = {z}, and let N be the set of neighbours of Z. Thus, N ∪ {z} is a strong clique. Let R = V (G) \ (N ∪ {z}). We may assume that R is not a strong clique, for otherwise the result follows from 10.2. Hence |V (G)| ≥ 4.

(1) Every vertex in N has a neighbour in R.

For by 10.1, no vertex in N is a twin of z. This proves (1).

An anticomponent of R means a maximal subset of R that cannot be partitioned into two nonempty subsets that are strongly complete to each other. Let D_{1}, …, D_{k} be the anticomponents of R; then D_{1}, …, D_{k} are pairwise disjoint and have union R, and are all strongly complete to each other. Since R is not a strong clique, at least one of D_{1}, …, D_{k} has more than one vertex.

Now V (G) is the union of three strong cliques. Since one of these cliques contains z and therefore is a subset of N ∪ {z}, it follows that R can be partitioned into two strong cliques, say L, M. Thus V (G) is partitioned into three strong cliques L, M, N ∪ {z}.

Let T be the union of all triads of G, and S = V (G) \ T. Thus z ∈ T, and T ∩ R is the union of all the sets D_{1}, …, D_{k} that have more than one member.

(2) If n ∈ N ∩ S, then for all i with 1 ≤ i ≤ k such that |D_{i}| > 1, n is strongly complete to one of L ∩ D_{i}, M ∩ D_{i} and strongly anticomplete to the other. Moreover, R \ T is strongly anticomplete to N ∩ T.

For let x, y ∈ D_{i} be antiadjacent. Now n is not adjacent to both x, y (since {n, z, x, y} is not a claw) and n is not antiadjacent to both x, y (since {n, x, y} is not a triad, because n ∈ S). Hence n is strongly adjacent to one of x, y and strongly antiadjacent to the other. In particular, if x′ ∈ D_{i} and x′, y are antiadjacent, then n is either strongly complete or strongly anticomplete to {x, x′}. This proves the first assertion of (2). For the second, let n ∈ N ∩ T and r ∈ R \ T. Then n is in a triad with two members of T ∩ R, and r is adjacent to these two members of T ∩ R and therefore strongly antiadjacent to n (since G is claw-free). This proves (2).

(3) We may assume that N ∩ T ≠ ∅.

For suppose not. Thus N ⊆ S, and by (2), for all i with 1 ≤ i ≤ k such that |D_{i}| > 1, every vertex in N is either strongly complete to D_{i} ∩ L and strongly anticomplete to D_{i} ∩ M, or vice versa. Thus if |D_{i}| > 1 then (L ∩ D_{i}, M ∩ D_{i}) is a homogeneous pair, and so |L ∩ D_{i}|, |M ∩ D_{i}| = 1 since (G, Z) is unbreakable. It follows that (G, Z) ∈ Z_{9}, and the theorem holds. This proves (3).

(4) There is exactly one value of i with 1 ≤ i ≤ k such that |D_{i}| > 1.

For there is at least one such value, since R is not a strong clique; suppose there are two. By (3), there exists n ∈ N with two antineighbours x_{1}, y_{1} ∈ R, that are antiadjacent to each other. We may assume that x_{1}, y_{1} ∈ D_{1}. Let x_{2} ∈ R \ D_{1}; then x_{2} is adjacent to x_{1}, y_{1}, and therefore strongly antiadjacent to n since {x_{2}, n, x_{1}, y_{1}} is not a claw. So n is strongly anticomplete to R \ D_{1}. We may assume that |D_{2}| > 1, and so n has two antineighbours in D_{2} that are antiadjacent; and so by exchanging D_{1} and D_{2}, it follows that n is strongly anticomplete to R \ D_{2}, and therefore to R. But this is contrary to (1), and so proves (4).

In view of (4), we may assume that |D_{1}| > 1, and |D_{i}| = 1 for 2 ≤ i ≤ k. Thus T ∩ R = D_{1}.

(5) G|T does not admit twins. If (P, Q) is a W-join in G|T, then z ∈ P ∪ Q, say z ∈ P. Moreover, |P | = 2, say P = {z, p}, and |Q| = 1, say Q = {q}; and q ∈ R ∩ T belongs to one of L ∩ T, M ∩ T and is strongly anticomplete to the other; and q is the unique neighbour of p in R.

For suppose that u, v are twins in G|T. If u, v ∈ N ∪ {z}, then by (2) they are also twins in G, contrary to (1). Thus we may assume that v ∈ R. Since u, v are adjacent, u ≠ z; and since z is therefore strongly complete or strongly anticomplete to both u, v, we deduce that u ∈ R. We may assume that u ∈ L. Since D_{1} is anticonnected, u has an antineighbour m ∈ M ∩ T; and therefore m ≠ v, and m is strongly antiadjacent to both u, v. Consequently v ∉ M, and so u, v ∈ L. But then u, v are twins in G, by (2), contrary to 10.1. This proves the first assertion.

Now suppose that (P, Q) is a W-join in G|T, and suppose first that P, Q ⊆ R. Since (P, Q) is not a W-join in G, and since R \ T is strongly complete to P ∪ Q, we may assume that some vertex of N \ T is neither strongly complete nor strongly anticomplete to Q. By (2) it follows that Q ∩ L, Q ∩ M are both nonempty. Since every vertex in (L ∩ T) \ (P ∪ Q) has a neighbour in Q ∩ L, it follows that (L ∩ T) \ (P ∪ Q) is strongly complete to Q, and similarly (R ∩ T) \ (P ∪ Q) is strongly complete to Q. Now every vertex in Q ∩ L belongs to a triad, and therefore has an antineighbour in M ∩ T, which consequently belongs to P. So no vertex in Q ∩ L is strongly complete to P ∩ M, and similarly no vertex in Q ∩ M is strongly complete to P ∩ L; and in particular, P ∩ L, P ∩ M are both nonempty. By exchanging P, Q we deduce that (R ∩ T) \ (P ∪ Q) is strongly complete to P; and so (R ∩ T) \ (P ∪ Q) is strongly complete to P ∪ Q. Moreover, (P ∩ L) ∪ (Q ∩ M) is strongly complete to (P ∩ M) ∪ (Q ∩ L), since P, Q, L, M are all strong cliques. But this is impossible since D_{1} is an anticomponent.

Consequently not both P, Q are subsets of R. Since P is not strongly complete to Q, not both P, Q are subsets of N ∪ {z}; and since P, Q are both nonempty, we may assume that P ∩ (N ∪ {z}) and Q ∩ R are both nonempty. In particular, z ∉ Q, since Q is a strong clique. We claim that P ⊆ N ∪ {z}; for if z ∈ P then P ⊆ N ∪ {z} since P is a strong clique, and if z ∉ P then since z has a neighbour in P, it follows that z is strongly complete to P, and again P ⊆ N ∪ {z}.

We may assume that there exists q ∈ Q ∩ M. Since D_{1} is anticonnected, q has an antineighbour q′ ∈ L; and hence q′ ∉ Q, since Q is a strong clique. Consequently q′ is strongly anticomplete to Q, and in particular to Q ∩ L; and since L is a strong clique and q′ ∈ L, we deduce that Q ∩ L = ∅.

Suppose that z ∉ P. Since z has an antineighbour in Q, it follows that z is strongly anticomplete to Q, and so Q ⊆ R, and therefore Q ⊆ M. But then (P, Q) is a W-join in G, contrary to (1). This proves that z ∈ P.

Every vertex in (M ∩ T) \ Q has a neighbour in Q ∩ M and is therefore strongly complete to Q; and so M ∩ T is strongly complete to Q ∩ N. But every vertex in Q ∩ N belongs to a triad, and therefore has an antineighbour in M ∩ T. Consequently Q ∩ N = ∅, and so Q ⊆ M. If P = {z}, then |Q| > 1 and Q is a homogeneous set in G|T and hence in G, a contradiction. Thus |P | > 1.

By (2), it follows that (P \ {z}, Q) is a homogeneous pair in G, and so |P | = 2 and |Q| = 1; let P = {z, p} and Q = {q} say. Since (P, Q) is a W-join in G|T, every vertex in R \ Q is strongly anticomplete to P (since every such vertex is antiadjacent to z ∈ P), and so q is the only neighbour of p in R. We claim that L ∩ T is strongly anticomplete to q; for suppose that some y ∈ L ∩ T is adjacent to q. Since y belongs to a triad, it has an antineighbour y′ ∈ M ∩ T; but then {q, p, y, y′} is a claw, a contradiction. This proves that L∩T is strongly anticomplete to q, and therefore proves (5).

(6) There exist j with 1 ≤ j ≤ 5 and (G′, A′, B′, C′) ∈ T C_{j} such that one of the following holds:

• G′ = G|T and {A′, B′, C′} = {(N ∩ T) ∪ {z}, L ∩ D_{1}, M ∩ D_{1}};

• some p ∈ N ∩ T has a unique neighbour q ∈ R; q belongs to one of L ∩ T, M ∩ T and is strongly anticomplete to the other; G′ is the trigraph obtained from G|T by deleting z and making p, q semiadjacent; and {A′, B′, C′} = {N ∩ T, L ∩ D_{1}, M ∩ D_{1}}.

For by (2), there is a partition (S_{1}, S_{2}) of N ∩ S such that S_{1} is strongly complete to L ∩ D_{1} and strongly anticomplete to M ∩ D_{1}, and S_{2} is strongly complete to M ∩ D_{1} and strongly anticomplete to L∩D_{1}. Now (G|T, (N ∩T)∪{z}, L∩D_{1}, M ∩D_{1}) is a three-cliqued claw-free trigraph, and it does not admit a hex-join since every vertex in D_{1} is in a triad containing z, and every vertex in N ∩ T is in a triad meeting D_{1}. Moreover, each of its vertices is in a triad, and so it does not admit a worn hex-join. Hence, by 4.1, (G|T, (N ∩ T) ∪ {z}, L ∩ D_{1}, M ∩ D_{1}) is a permutation of a thickening of a member (G′, A′, B′, C′) of T C_{j} for some j ∈ {1, …, 5}. Let X_{v} (v ∈ V (G′)) be the corresponding subsets, where z ∈ X_{z′} say; then z′ is either simplicial or near-simplicial in G′. If z′ is simplicial in G′, then |X_{v}| = 1 for every v ∈ V (G′) by (5), and so (G|T, (N ∩ T) ∪ {z}, L ∩ D_{1}, M ∩ D_{1}) is a permutation of (G′, A′, B′, C′) and the claim holds. If z′ is near-simplicial in G′, then by (5), |X_{v}| = 1 for each v ∈ V (G′) \ {z′}; X_{z′} = {z, p} where p ∈ N ∩ T has a unique neighbour q ∈ R ∩ T as in (5), and again the claim holds. This proves (6).

Let j and (G′, A′, B′, C′) be as in (6). If the first case of (6) holds, let p = z, and otherwise let p be as in the second case of (6).

(7) If j = 1 then the theorem holds.

For suppose that j = 1. Let H, v_{1}, v_{2}, v_{3}, A, B, C be as in the definition of T C_{1}, where G′ is a line trigraph of H, and A = (N ∩ T) or (N ∩ T) ∪ {z}, and B = L ∩ D_{1}, and C = M ∩ D_{1}. Then p ∈ A and so p is incident with v_{1} in H. Let the ends of p in H be v_{1}, v_{0} say; then v_{0} ≠ v_{2}, v_{3}. Moreover, since p is simplicial or near-simplicial in G′, it follows that every edge of H incident with v_{0} different from p shares an end with every edge incident with v_{1}. Since there are at least three edges incident with v_{1}, it follows that p is the only edge of H incident with v_{0}, and therefore p is simplicial in G′, and so the first case of (6) holds. But then (G, Z) ∈ Z_{14} and the theorem holds. This proves (7).

(8) If j = 2 then the theorem holds.

For let j = 2. It is easy to see that for any trigraph J and y ∈ V (J), if y is a simplicial vertex of J and (J, X, Y, Z) ∈ T C_{2}, then (J, {y}) ∈ Z_{13}. In particular, if the first case of (6) holds, then (G, Z) ∈ Z_{13}; so we may assume that the second case holds, and so p is near-simplicial in G′. Let q be as in (6). Then (G′, N ∩ T, L ∩ D_{1}, M ∩ D_{1}) ∈ T C_{2}; let Σ be a circle with V (G′) ⊆ Σ, and let F_{1}, …, F_{k} ⊆ Σ, as in the definition of long circular interval trigraph. Let L_{1}, L_{2}, L_{3} be pairwise disjoint lines with V (G′) ⊆ L_{1} ∪ L_{2} ∪ L_{3}, and with

V (G′) ∩ L_{1} = N ∩ T, V (G′) ∩ L_{2} = L ∩ D_{1}, V (G′) ∩ L_{3} = M ∩ D_{1}.

Since p, q are semiadjacent in G′, we may assume they are both ends of F_{1} say, and no other F_{i} contains both p, q. But then (G|T, (N ∩ T) ∪ {z}, L ∩ D_{1}, M ∩ D_{1}) ∈ T C_{2}, as we see by inserting z into Σ consecutive with p and not in F_{1}; and so again (G, Z) ∈ Z_{13}. This proves (8).

(9) If j = 3 then the theorem holds.

For let j = 3. Then G′ is a near-antiprismatic trigraph; let H, A, B, C, X, a_{0}, b_{0} be as in the definition of near-antiprismatic trigraph, such that G′ = H \ X, and A′ = A \ X and similarly for B′, C′. As in the proof of 11.1, it follows that a_{0}, b_{0} are the only simplicial or near-simplicial vertices of G′, so we may assume that p = a_{0}. If the first case of (6) holds, then p is simplicial in G′, and a_{0}, b_{0} are strongly antiadjacent in G′, and G′ = G|T; so A = N, and {B, C} = {L ∩ D_{1}, M ∩ D_{1}}. But then (G, {z}) ∈ Z_{11} and the theorem holds. We may therefore assume that the second case of (6) holds, and so p is near-simplicial in G′; so a_{0}, b_{0} are semiadjacent in G′, and q = b_{0}, where q is as in (6). But then (G, {z}) ∈ Z_{11} and the theorem holds. This proves (9).

(10) If j = 4 then the theorem holds.

For suppose that G′ is antiprismatic. Suppose first that G′ = G|T. By (3), there exists n ∈ N ∩ T, and it belongs to a triad {n, x, y}, where x, y ∈ R. But then only one pair of vertices in {n, x, y, z} is strongly adjacent, contradicting that G′ is antiprismatic. Thus the second case of (6) holds, and V (G′) = T \ {z}. Let p, q be as in (6). Then p, q are semiadjacent in G′, and p is strongly adjacent in G′ to only one vertex of each triad of G′ that does not contain p, and since G′ is antiprismatic, there is no such triad, that is, N ∩T = {p}. We may assume that q ∈ M ∩T and q is strongly anticomplete to L ∩ T. If there exists x ∈ M ∩ T different from q, then x has an antineighbour y ∈ L, and only one pair of vertices in {p, q, x, y} are strongly adjacent in G′, contradicting that G′ is antiprismatic. Hence M ∩ T = {q}. If x, y ∈ L ∩ T are distinct, then only one pair of vertices in {p, q, x, y} are strongly adjacent, again a contradiction; so |L ∩ T | = 1. But then (G, {z}) ∈ Z_{13}. This proves (10).

(11) If j = 5 then the theorem holds.

For let H, X, v_{1}, …, v_{8}, A, B, C be as in the first case of the definition of T C_{5}, where

(H \ X, A, B \ X, C) = (G′, A′, B′, C′).

Thus X ⊆ {v_{3}, v_{4}}. Hence v_{1}, v_{3}, v_{4}, v_{6}, v_{7} are not simplicial or near-simplicial in G′, so p is one of v_{2}, v_{5}, v_{8}. Suppose that p = v_{2}. Since v_{1}, v_{4} are semiadjacent in H, it follows that v_{4} ∈ X. If v_{2} is simplicial in G′, then v_{2}, v_{5} are strongly antiadjacent, and G′ = G|T, and so (G, {z}) ∈ Z_{11} and the theorem holds. If v_{2} is not simplicial in G′, then v_{2}, v_{5} are semiadjacent in G′, and G|T is obtained from G′ by adding z strongly adjacent to {v_{1}, v_{2}, v_{3}} \ X and strongly antiadjacent to all other vertices of G′, and possibly making v_{2}, v_{5} strongly adjacent. But then (G, {z}) ∈ Z_{10} and the theorem holds. Hence we may assume that p ≠ v_{2}, and similarly p ≠ v_{5}, and therefore p = v_{8}. Hence p is not semiadjacent to any vertex in G′, and so G′ = G|T. Consequently (G, {z}) ∈ Z_{15}, and the theorem holds.

Now let H, X, v_{1}, …, v_{9}, A, B, C be as in the second case of the definition of T C_{5}, where

(H \ X, A, B \ X, C) = (G′, A′, B′, C′).

Thus X ⊆ {v_{3}, v_{4}, v_{5}, v_{6}} and contains at most one of v_{3}, v_{4} and at most one of v_{5}, v_{6}. Moreover, v_{2} is adjacent in G′ to one of v_{3}, v_{4}, and v_{7} is adjacent to one of v_{5}, v_{6}. Hence none of v_{1}, v_{3}, v_{6}, v_{8}, v_{9} are simplicial or near-simplicial in G′, so from the symmetry we may assume that p is one of v_{2}, v_{4}. Suppose first that p = v_{2}. One of A, B \ X, C consists of {p} together with all strong neighbours of p in G′, and this must be A since p ∈ A; so v_{3} ∈ X (because otherwise v_{3} is a strong neighbour of p in G′ that is not in A), and v_{2} is semiadjacent to v_{4}, and so q = v_{4} and the second case of (6) holds. Then G|T is obtained from G′ by adding a vertex z strongly adjacent to v_{1}, v_{2} and strongly antiadjacent to all other vertices of G′, and possibly making v_{2}, v_{4} strongly adjacent. But then (G, Z) ∈ Z_{10} and the theorem holds.

We may therefore assume that p = v_{4}, and in particular, v_{4} ∉ X. Since v_{4} is simplicial or near-simplicial in G′, it follows that v_{2}, v_{4} are antiadjacent. If they are strongly antiadjacent, then G|T = G′ and (G, Z) ∈ Z_{12}. If they are semiadjacent, then G|T is obtained from G′ by adding a vertex z strongly adjacent to {v_{3}, v_{4}, v_{5}, v_{6}, v_{9}} \ X and strongly antiadjacent to all other vertices of G′, and possibly making v_{2}, v_{4} strongly adjacent. But then again (G, Z) ∈ Z_{12}. This proves (11).

From (6)–(11), this proves 13.3.

Proof of 7.2. Let G be a connected claw-free trigraph such that V (G) is not the union of three strong cliques. By 9.1, there is a strip-structure (H, η) of G such that all its strips are either spots or cliques or thickenings of unbreakable stripes. Suppose first that (H, η) is trivial. Then the unique strip of the strip-structure is (G, ∅), and so this is either a spot or a clique or a thickening of an unbreakable stripe. It is not a spot since |Z| = 2 for every spot (J, Z). If it is a clique then G is a strong clique and hence a thickening of a one-vertex trigraph (which belongs to S_{3} for instance), and the theorem holds. We assume then that (G, ∅) is an unbreakable stripe. But G does not admit a hex-join, since V (G) is not the union of three cliques; and G does not admit twins, a W-join, a 0-join, a 1-join or a generalized 2-join since (G, ∅) is an unbreakable stripe. Thus G is indecomposable. By 5.1, G ∈ S_{i} for some i ∈ {0, …, 7}. If |V (G)| ≤ 2 then G ∈ S_{3} and the theorem holds, so we assume that |V (G)| ≥ 3; and so by 10.3, i > 0. Moreover, G has no simplicial vertex, since (G, ∅) is unbreakable, and so i ≠ 4, 5. Suppose that i ∈ {2, 6}. Then there are two vertices a_{0}, b_{0} of G, either strongly antiadjacent to each other and both simplicial, or semiadjacent to each other and both near-simplicial. The first is impossible since no vertices of G are simplicial. In the second case, let V_{1} = {a_{0}, b_{0}} and V_{0} the set of all vertices in V (G) \ {a_{0}, b_{0}} that are strongly adjacent to both a_{0}, b_{0}, and V_{2} = V (G) \ (V_{0} ∪ V_{1}); since V_{1}, V_{2} are not strongly stable, these define a pseudo-2-join, a contradiction. Thus i ∈ {1, 3, 7} and the theorem holds.

Thus we may assume that (H, η) is nontrivial. Let (J, Z) be a strip of the strip-structure. We must show that either (J, Z) is a spot, or (J, Z) is a thickening of a member of Z_{0}. Suppose then that (J, Z) is not a spot. Certainly Z ≠ ∅ since G is connected and the strip-structure is nontrivial. If (J, Z) is a clique, then |Z| = 1 and (J, Z) is a thickening of a member of Z_{6}. We assume therefore that (J, Z) is not a clique, and so |V (J)| > 2. It follows that (J, Z) is a thickening of an unbreakable stripe (J′, Z′). If V (J′) is the union of two strong cliques, then by 10.2 (J′, Z′) ∈ Z_{1} ∪Z_{6} as required, so we may assume that V (J′) is not the union of two strong cliques. By 10.5 either J′ is a thickening of an indecomposable member of S_{i} for some i ∈ {1, …, 7}, or J′ admits a hex-join. In the first case, by 12.2 we deduce that (J′, Z′) ∈ Z_{0} as required. In the second case, 13.1 implies that |Z′| = 1 or 2. If |Z′| = 2 then 13.2 implies that (J′, Z′) ∈ Z_{0} as required. If |Z′| = 1 then 13.3 implies that (J′, Z′) ∈ Z_{0} again as required. This proves 7.2.

References

[1] Maria Chudnovsky and Paul Seymour, “Claw-free Graphs. I. Orientable prismatic graphs”, J. Combinatorial Theory, Ser. B, 97 (2007), 867–903.

[2] Maria Chudnovsky and Paul Seymour, “Claw-free Graphs. II. Non-orientable prismatic graphs”, J. Combinatorial Theory, Ser. B, 98 (2008) 249–290.

[3] Maria Chudnovsky and Paul Seymour, “Claw-free Graphs. III. Circular interval graphs”, J. Combinatorial Theory, Ser. B, to appear (manuscript, October 2003).

[4] Maria Chudnovsky and Paul Seymour, “Claw-free Graphs. IV. Decomposition theorem”, J. Combinatorial Theory, Ser. B, to appear (manuscript, October 2003).