Claw-free Graphs. III. Circular interval graphs

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

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

October 14, 2003; 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

Construct a graph as follows. Take a circle, and a collection of intervals from it, no three of which have union the entire circle; take a finite set of points V from the circle; and make a graph with vertex set V in which two vertices are adjacent if they both belong to one of the intervals. Such graphs are “long circular interval graphs”, and they form an important subclass of the class of all claw-free graphs. In this paper we characterize them by excluded induced subgraphs. This is a step towards the main goal of this series, to find a structural characterization of all claw-free graphs.

This paper also gives an analysis of the claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices.

1 Introduction

Let G be a graph. (All graphs in this paper are finite and simple.) If X ⊆ V (G), the subgraph G|X induced on X is the subgraph with vertex set X and edge-set all edges of G with both ends in X. (V (G) and E(G) denote the vertex- and edge-sets of G respectively.) We say that X ⊆ V (G) is a claw in G if G|X is isomorphic to the complete bipartite graph K_{1,3}. We say G is claw-free if no X ⊆ V (G) is a claw in G. Our objective in this series of papers is to show that every claw-free graph can be built starting from some basic classes by means of some simple constructions. One important subclass of claw-free graphs are the “long circular interval graphs”, the main topic of this paper.

Let Σ be a circle, and let F_{1}, …, F_{k} ⊆ Σ be “intervals”, that is, each is homeomorphic to the interval [0, 1]. Now let V ⊆ Σ be finite, and let G be the graph with vertex set V in which two vertices are adjacent if and only if some F_{i} contains both of them. Such a graph G is called a circular interval graph. If in addition no three of F_{1}, …, F_{k} have union Σ, we call G a long circular interval graph. (They are not to be confused with what are called “circular arc graphs”; one is a proper subclass of the other.)

Long circular interval graphs are claw-free, and these together with line graphs turn out to be the two “principal” basic classes of claw-free graphs. Our (lengthy) proof of that fact includes a characterization of long circular interval graphs by excluded induced subgraphs, and it is convenient to spin that off into a separate paper, the present paper. Incidentally, one might ask why we insist that no three of the intervals F_{1}, …, F_{k} mentioned above can have union the circle. If we omit this condition, the graphs we produce are still claw-free; but we do not know how to characterize this larger class by excluded induced subgraphs, and for our application we do not need to do so.

One form of our main result is the following (the terms used are defined later in terms of “trigraphs”, but here have their conventional graph-theory meaning).

1.1 Let G be a graph. Then G is a long circular interval graph if and only if no induced subgraph is a claw, net, antinet or (1, 1, 1)-prism, and every hole is dominating, and has no centre.

However, for our application in [1], we need to prove something stronger, connecting the size of the largest hole in G with the type of excluded subgraph that we use. This needs a number of further definitions, and we postpone the precise statement until 3.3.

It is advantageous for the application to work, not just with graphs, but with slightly more general objects that we call “trigraphs”. In a graph, every pair of vertices are either adjacent or nonadjacent, but in a trigraph, some pairs may be “undecided”. For our purposes, we may assume that this set of undecided pairs is a matching. Thus, let us say 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; 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. 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 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.

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

An induced subtrigraph G|X of G is said to be a path from u to v if |X| = n for some n ≥ 1, and X can be ordered as {p_{1}, …, p_{n}}, satisfying

• p_{1} = u and p_{n} = v

• p_{i} is adjacent to p_{i+1} for 1 ≤ i < n, and

• p_{i} is antiadjacent to p_{j} for 1 ≤ i, j ≤ n with i + 2 ≤ j.

We say it has length n − 1. (Thus it has length 0 if and only if u = v.) It is often convenient to describe such a path by the sequence p_{1}-p_{2}- ⋯ -p_{n}. Note that the sequence is uniquely determined by the set {p_{1}, …, p_{n}} and the vertices u, v, because F (G) is a matching.

A hole in G is an induced subtrigraph C with n vertices for some n ≥ 4, whose vertex set can be ordered as {c_{1}, …, c_{n}}, satisfying

• c_{i} is adjacent to c_{i+1} for 1 ≤ i < n, and also c_{n} is adjacent to c_{1}, and

• c_{i} is antiadjacent to c_{j} for 1 ≤ i, j ≤ n with i + 2 ≤ j and (i, j) ≠ (1, n).

Again, it is often convenient to describe C by the sequence c_{1}-c_{2}- ⋯ -c_{n}-c_{1}, and we say it has length n. The sequence is uniquely determined by a knowledge of V (C), up to choice of the first term and up to reversal. An n-hole means a hole of length n. A centre for a hole C is a vertex in V (G) \ V (C) that is adjacent to every vertex of the hole. A hole C is dominating in G if every vertex in V (G) \ V (C) has a neighbour in C.

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}}. (Thus, for example, if a_{0}, a_{1}, a_{2}, a_{3} ∈ V (G), and a_{0}a_{3} and a_{1}a_{2} are semiadjacent pairs, and a_{0}a_{1}, a_{0}a_{2} are strongly adjacent, and a_{1}a_{3}, a_{2}a_{3} are strongly antiadjacent, then G|{a_{0}, a_{1}, a_{2}, a_{3}} is a claw.) 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.

A net is a trigraph with six vertices a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, such that {a_{1}, a_{2}, a_{3}} is a clique and a_{i}, b_{i} are adjacent for i = 1, 2, 3, and all other pairs are antiadjacent. An antinet is the “complement trigraph” of a net; that is, a trigraph with six vertices a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, such that {a_{1}, a_{2}, a_{3}} is stable and a_{i}, b_{i} are antiadjacent for i = 1, 2, 3, and all other pairs are adjacent. A (1, 1, 1)-prism is a trigraph with six vertices a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, such that {a_{1}, a_{2}, a_{3}} and {b_{1}, b_{2}, b_{3}} are cliques, and a_{i}, b_{i} are adjacent for i = 1, 2, 3, and all other pairs are antiadjacent.

Let Σ be a circle, and let F_{1}, …, F_{k} ⊆ Σ be homeomorphic to the interval [0, 1]. Assume that no three of F_{1}, …, F_{k} have union Σ, and no two of F_{1}, …, F_{k} share an end-point. 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.

Let G be a trigraph, and let D be a directed graph. We say that D is a direction of G if V (D) = V (G), and distinct u, v are adjacent in D if and only if they are adjacent in G. If u, v ∈ V (G), we write uv ∈ E(D) to mean that there is an edge of D between u, v, and u is its tail and v its head in D.

Let Σ be a circle, and assign an orientation to it called “clockwise”. Let G be a trigraph, and let ϕ be a map from V (G) into Σ; then for σ ∈ Σ, ϕ^{−1}(σ) denotes the set {v ∈ V (G) : ϕ(v) = σ}. Let D be a direction of G, and suppose that the following conditions are satisfied:

• For each σ ∈ Σ, ϕ^{−1}(σ) is a strong clique of G.

• Every directed cycle in D has length at least four.

• If σ_{1}, σ_{2} ∈ Σ are distinct, there do not exist u_{i}, v_{i} ∈ ϕ^{−1}(σ_{i}) (i = 1, 2) such that u_{1}v_{2}, u_{2}v_{1} ∈ E(D).

• If σ_{1}, σ_{2}, σ_{3} ∈ Σ are distinct and in clockwise order, let X_{i} = ϕ^{−1}(σ_{i}) (i = 1, 2, 3), and suppose that there exist u ∈ X_{1} and v ∈ X_{3} such that uv ∈ E(D). Then X_{2} is strongly complete to X_{1} ∪ X_{3} in G. Moreover, in D the edges between X_{1}, X_{2} all have tail in X_{1}, and the edges between X_{2}, X_{3} all have tail in X_{2}.

• For each σ_{1} ∈ Σ, if |ϕ^{−1}(σ_{1})| > 1 then there exists σ_{2} ∈ Σ with σ_{2} ≠ σ_{1} such that ϕ^{−1}(σ_{1}) is neither strongly complete nor strongly anticomplete to ϕ^{−1}(σ_{2}). Moreover, for any such σ_{2}, every vertex in ϕ^{−1}(σ_{1}) has both a neighbour and an antineighbour in ϕ^{−1}(σ_{2}).

• For each σ_{1} ∈ Σ there is at most one σ_{2} ∈ Σ with σ_{2} ≠ σ_{1} such that ϕ^{−1}(σ_{1}) is neither strongly complete nor strongly anticomplete to ϕ^{−1}(σ_{2}).

We call such a pair (ϕ, D) a metacircular arrangement of G; and if G admits such a pair (ϕ, D) we say that G is metacircular. Note that ϕ can be chosen to be an injection if and only if G is a long circular interval trigraph; so metacircular trigraphs are just a slight variant of long circular interval trigraphs. If (ϕ, D) is a metacircular arrangement of G, and C_{0} is a hole in G, we say that C_{0} is a basis for the arrangement if the points ϕ(v) (v ∈ V (C_{0})) are all distinct.

2 Circle arrangements

Being metacircular implies being claw-free, but it is convenient to relax the definition of “metacircular” further, to a condition which is much easier to recognize, but which no longer implies being claw-free, as follows.

As before, let Σ be a circle, and assign an orientation to it called “clockwise”. If ϕ is a map from V (G) into Σ, we say a triple (u, v, w) of vertices of G is clockwise if ϕ(u), ϕ(v), ϕ(w) are distinct and in clockwise order in Σ. By a circle arrangement of a trigraph G we mean a pair (ϕ, D), where ϕ is a map from V (G) into Σ, and D is a direction of G, satisfying the following conditions:

• for all σ ∈ Σ, ϕ^{−1}(σ) is a strong clique of G

• every directed cycle in D has length at least four

• for every clockwise triple (u, v, w), if uw ∈ E(D) then v is strongly adjacent to u, w in G, and uv, vw ∈ E(D)

• if u, v, w ∈ V (G) and uv, vw ∈ E(D), and ϕ(u) = ϕ(w), then ϕ(u) = ϕ(v).

We call the first condition the first axiom and so on. If C_{0} is a hole in G, we say it is a basis for the circle arrangement if the points ϕ(v) (v ∈ V (C_{0})) are all distinct. The next result implies that to show that a claw-free trigraph is metacircular, it suffices to exhibit a circle arrangement.

2.1 Every claw-free trigraph G that admits a circle arrangement is metacircular; and indeed, for every circle arrangement (ϕ_{0}, D_{0}) of G, there is a metacircular arrangement (ϕ, D) of G such that every basis for (ϕ_{0}, D_{0}) is a basis for (ϕ, D).

Proof. If (ϕ, D) is a circle arrangement of G, we define Σ(ϕ) to be the set of all σ ∈ Σ such that ϕ^{−1}(σ) ≠ ∅. Let (ϕ_{0}, D_{0}) be a circle arrangement of G; and choose a circle arrangement (ϕ, D) such that every basis for (ϕ_{0}, D_{0}) is a basis for (ϕ, D), and |Σ(ϕ)| is maximum with this property. (We call this property the “maximality” of (ϕ, D).) We shall prove that (ϕ, D) is in fact a metacircular arrangement. For a vertex u, let A(u), B(u) be the sets of all v ∈ V (G) such that ϕ(u) ≠ ϕ(v) and uv ∈ E(D) (respectively, vu ∈ E(D)). Let A^{∗}(u) be the set of all v ∈ A(u) such that u, v are strongly adjacent in G, and define B^{∗}(u) similarly. (Thus A^{∗}(u) includes all of A(u) except possibly one vertex.)

(1) For all s ∈ Σ(ϕ), and all X ⊆ ϕ^{−1}(s), let Y = ϕ^{−1}(s) \ X; if X, Y are both nonempty, then there exist x ∈ X and y ∈ Y such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x).

For suppose not. Choose two points r, t of Σ \ Σ(ϕ), immediately before and after s; more precisely, such that r, s, t are in clockwise order, and t, s′, r are in clockwise order for all s′ ∈ Σ(ϕ) \ {s}. For v ∈ V (G), define ϕ′(v) as follows: if v ∈ X, ϕ′(v) = r; if v ∈ Y, ϕ′(v) = t; and otherwise ϕ′(v) = ϕ(v). Define a new direction D′ of G as follows: for each edge e = yx of D with x ∈ X and y ∈ Y, redirect e so that x is its tail. For all other edges e let the tail of e in D′ be the same as its tail in D. We claim that the pair (ϕ′, D′) is a circle arrangement of G. Let us check the axioms. The first axiom clearly holds. For the second, suppose that uv, vw, wu ∈ E(D′). Then one of them does not belong to E(D), say wu, and so w ∈ X and u ∈ Y. Since uv ∈ E(D′) it follows that v ∉ X, and similarly v ∉ Y; and so v ∉ ϕ^{−1}(s). Consequently uv, vw ∈ E(D); but then (ϕ, D) fails to satisfy the fourth axiom, a contradiction. For the third axiom, suppose that (u, v, w) is clockwise (with respect to ϕ′), and uw ∈ E(D′). If at most one of u, v, w belong to ϕ^{−1}(s), then (u, v, w) is also clockwise with respect to ϕ, and uw ∈ E(D), and hence uv, vw ∈ E(D) since (ϕ, D) satisfies the third axiom; but then uv, vw ∈ E(D′) as required. We may therefore assume that at least two of u, v, w belong to ϕ^{−1}(s). Since (u, v, w) is clockwise with respect to ϕ′, at most one of u, v, w is in X and at most one in Y. There are therefore three possibilities: u ∈ X, v ∈ Y and w ∉ ϕ^{−1}(s); or v ∈ X, w ∈ Y and u ∉ ϕ^{−1}(s); or w ∈ X, u ∈ Y and v ∉ ϕ^{−1}(s). In the first case, u, v are strongly adjacent, since X ∪Y is a strong clique; uv ∈ E(D′) from the definition of D′; also, w ∈ A(u), and since the claim of (1) is false, w ∉ A(u) \ A^{∗}(v), and consequently vw ∈ E(D) and v, w are strongly adjacent; and therefore the axiom is satisfied. The second case is similar. The third case cannot occur since uw ∈ E(D′). Thus (ϕ′, D′) satisfies the third axiom. Finally, for the fourth axiom, suppose that u, v, w ∈ V (G) and uv, vw ∈ E(D′), and ϕ′(u) = ϕ′(w). Consequently ϕ(u) = ϕ(w). We claim that ϕ(u) = ϕ(v). For if uv, vw ∈ E(D) then ϕ(u) = ϕ(v), since (ϕ, D) satisfies the fourth axiom; and otherwise X ∪ Y contains v and at least one of u, w, and therefore contains both of u, w since ϕ(u) = ϕ(w), and so again ϕ(u) = ϕ(v). Thus in either case ϕ(u) = ϕ(v) = ϕ(w), and we may therefore assume that u, v, w ∈ X ∪Y. Since ϕ′(u) = ϕ′(w), both u, w belong to X or both to Y; and since uv, vw ∈ E(D′), it follows that v belongs to the same set, and therefore ϕ′(u) = ϕ′(v). This verifies the fourth axiom, and therefore proves that (ϕ′, D′) is a circle arrangement of G. But |Σ(ϕ)| < |Σ(ϕ′)|, since X, Y are nonempty, and every basis for (ϕ, D) is a basis for (ϕ′, D′), contrary to the maximality of (ϕ, D). This proves (1).

(2) If u, v ∈ V (G) and ϕ(u) = ϕ(v) then either A(u) ⊆ A^{∗}(v) or B(u) ⊆ B^{∗}(v).

Suppose not. Then there exist a vertex w ∈ A(u) \ A^{∗}(v) and a vertex x ∈ B(u) \ B^{∗}(v). Consequently, uw, xu ∈ E(D), and ϕ(w), ϕ(x) ≠ ϕ(u) = ϕ(v). The fourth axiom therefore implies that wv, vx ∉ E(D). If v, w are strongly adjacent, it follows that vw ∈ E(D) and so w ∈ A^{∗}(v), a contradiction; so v, w are antiadjacent, and similarly so are v, x. Since ϕ(u) = ϕ(v), the first axiom implies that u, v are adjacent in G. Since {u, v, w, x} is not a claw, it follows that w, x are strongly adjacent in G. By the second axiom, wx ∉ E(D), and so xw ∈ E(D). Now there are three subcases: (x, v, w) is clockwise; (v, x, w) is clockwise; and ϕ(w) = ϕ(x). If (x, v, w) is clockwise, the third axiom implies that v, w are strongly adjacent, a contradiction; if (v, x, w) is clockwise, then (u, x, w) is clockwise, and the third axiom applied to uw implies that ux ∈ E(D), which is false since xu ∈ E(D); and if ϕ(x) = ϕ(w), the fourth axiom is violated. This proves (2).

(3) Let s ∈ Σ(ϕ). Then either A(u) = A^{∗}(v) for all u, v ∈ ϕ^{−1}(s), or B(u) = B^{∗}(v) for all u, v ∈ ϕ^{−1}(s).

For let H be the digraph with vertex set ϕ^{−1}(s), and edge set all pairs (u, v) with u, v ∈ ϕ^{−1}(s) (possibly with u = v) such that B(v) ⊈ B^{∗}(u). Suppose first that some w ∈ V (H) has outdegree zero in H (that is, no edge of H has tail w.) In particular, (w, w) ∉ E(H), and so B(w) = B^{∗}(w). Let X be the set of all vertices x ∈ V (H) such that B(x) = B^{∗}(x) = B(w). If X = V (H) then the claim holds, so we may assume that V (H) ≠ X. By (1), there exist x ∈ X and y ∈ V (G) \ X such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x). Since (w, y) ∉ E(H), it follows that B(y) ⊆ B^{∗}(w) = B^{∗}(x), and so A(x) ⊈ A^{∗}(y). From (2), B(x) ⊆ B^{∗}(y), and therefore B(y) = B^{∗}(y) = B(x) = B(w), contradicting that y ∉ X.

We may therefore assume that every vertex of H has positive outdegree in H. Suppose that H is not strongly connected. Then there is a subset X ⊆ V (H) such that X, V (H) \ X ≠ ∅, and the restriction (denoted H|X) of H to X is strongly connected, and there is no (u, v) ∈ E(H) with u ∈ X and v ∈ V (G) \ X. By (1), there exist x ∈ X and y ∈ V (G) \ X such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x). Since (x, y) ∉ E(H), it follows that B(y) ⊆ B^{∗}(x), and so A(x) ⊈ A^{∗}(y). By (2), B(x) ⊆ B^{∗}(y), and therefore B(x) = B^{∗}(x) = B(y) = B^{∗}(y). If x′ ∈ X and (x′, x) ∈ E(H), then B(y) = B(x) ⊈ B^{∗}(x′), and so (x′, y) ∈ E(H), a contradiction. Hence x has indegree zero in H|X. Since H|X is strongly connected, it follows that |X| = 1, and in particular x has outdegree zero in H|X; but this contradicts that x has positive outdegree in H.

Consequently H is strongly connected. We claim that A(v) ⊆ A^{∗}(u) for all distinct u, v ∈ V (H). To see this, choose a directed path u = h_{1}- ⋯ -h_{k} = v of H. For 1 ≤ i < k, since (h_{i}, h_{i+1}) ∈ E(H), it follows that B(h_{i+1}) ⊈ B^{∗}(h_{i}), and therefore A(h_{i+1}) ⊆ A^{∗}(h_{i}) by (2). Consequently A(v) ⊆ A^{∗}(u), as claimed. Since also A(u) ⊆ A^{∗}(v), it follows that A(u) = A^{∗}(u) = A(v) = A^{∗}(v) for all distinct u, v ∈ V (H). Consequently, if |V (H)| ≥ 2 then (3) holds; and if |V (H)| ≤ 1 then again (3) holds, since F (G) is a matching. This proves (3).

Let s, t ∈ Σ(ϕ) be distinct. We write s ⇒ t if all edges between ϕ^{−1}(s) and ϕ^{−1}(t) are directed in D from ϕ^{−1}(s) to ϕ^{−1}(t).

(4) Let s, t ∈ Σ(ϕ) be different. Then either s ⇒ t or t ⇒ s.

For suppose there exist u, u′ ∈ ϕ^{−1}(s) and v, v′ ∈ ϕ^{−1}(t) such that uv, v′u′ ∈ E(D). By (3) and the symmetry, we may assume that A(u) = A(u′). Since v ∈ A(u) it follows that v ∈ A(u′) and so u′v ∈ E(D). But v′u′ ∈ E(D), contrary to the fourth axiom. This proves (4).

(5) Let r, s, t ∈ Σ(ϕ) be clockwise, and suppose that r ⇒ t. Then r ⇒ s and s ⇒ t. Moreover, either ϕ^{−1}(r) is strongly anticomplete to ϕ^{−1}(t), or ϕ^{−1}(s) is strongly complete to both ϕ^{−1}(r) and ϕ^{−1}(t).

For the first claim, we may assume from the symmetry that r ⇏ s. Choose u ∈ ϕ^{−1}(r) and v ∈ ϕ^{−1}(s), such that vu ∈ E(D). Choose w ∈ ϕ^{−1}(t). Since (s, t, r) is clockwise, the third axiom implies that wu ∈ E(D), contradicting that r ⇒ t. This proves the first claim.

For the second, we may assume that ϕ^{−1}(r) is not strongly anticomplete to ϕ^{−1}(t), and (from the symmetry) not strongly complete to ϕ^{−1}(s). Let X be the set of all u ∈ ϕ^{−1}(r) with an antineighbour in ϕ^{−1}(s), and let Y = ϕ^{−1}(r) \ X. By the third axiom, every vertex of ϕ^{−1}(r) with a neighbour in ϕ^{−1}(t) belongs to Y, and so X, Y are both nonempty. In particular, not all x, y ∈ ϕ^{−1}(r) have A^{∗}(x) = A(y), and so by (3), B^{∗}(x) = B(y) for all x, y ∈ ϕ^{−1}(r). By (1), there exist x ∈ X and y ∈ Y such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x). The first holds, since we just saw that B(y) = B^{∗}(x). Choose z ∈ A(x)\A^{∗}(y), and let ϕ(z) = t′ say. Now t′ ≠ s since y is strongly complete to ϕ^{−1}(s) and r ⇒ s; if (r, s, t′) is clockwise, then the third axiom implies that x is strongly complete to ϕ^{−1}(s), contradicting that x ∈ X; and if (r, t′, s) is clockwise, then since y has a neighbour in ϕ^{−1}(s) and yz ∉ E(D), the third axiom is violated. This proves (5).

Let s, t ∈ Σ(ϕ) be distinct. We say s, t is a mixed pair if ϕ^{−1}(s) is neither strongly complete nor strongly anticomplete to ϕ^{−1}(t).

(6) Let s, t be a mixed pair. Then there exists u ∈ ϕ^{−1}(s) such that u has a neighbour and an antineighbour in ϕ^{−1}(t).

For suppose not. So every vertex in ϕ^{−1}(s) is either strongly complete or strongly anticomplete to ϕ^{−1}(t). Let X be the set of members of ϕ^{−1}(s) that are strongly ϕ^{−1}(t)-complete, and Y the set of those that are strongly ϕ^{−1}(t)-anticomplete. Since s, t is mixed, X, Y are both nonempty. By (4) and the symmetry, we may assume that t ⇒ s. By (1), there exist x ∈ X and y ∈ Y such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x). But B(x) ⊈ B^{∗}(y), since ϕ^{−1}(t) is included in the first set and not the second; and so from (2), A(x) ⊆ A^{∗}(y). Consequently, B(y) ⊈ B^{∗}(x). Choose v ∈ ϕ^{−1}(t) and w ∈ B(y) \ B^{∗}(x). Since B(y) ∩ ϕ^{−1}(t) = ∅, ϕ(w) ≠ t = ϕ(v), and therefore one of (v, w, y), (w, v, y) is clockwise. If (v, w, y) is clockwise then (v, w, x) is clockwise, and yet vx ∈ E(D) and wx ∉ E(D), a contradiction to the third axiom. If (w, v, y) is clockwise then wy ∈ E(D), vy ∉ E(D) again contradicts the third axiom. This proves (6).

(7) For every s ∈ Σ(ϕ) there is at most one t ∈ Σ(ϕ) such that s, t is a mixed pair.

For let s, t_{1}, t_{2} ∈ Σ(ϕ) be distinct, and suppose that the pairs s, t_{1} and s, t_{2} are both mixed. By (3) and the symmetry, we may assume that B^{∗}(x) = B(y) for all x, y ∈ ϕ^{−1}(s). By (6) for i = 1, 2 there exists v_{i} ∈ ϕ^{−1}(t_{i}) with a neighbour u_{i} and an antineighbour u′_{i} in ϕ^{−1}(s). Since v_{i} ∉ B^{∗}(u′_{i}) = B(u_{i}) it follows that v_{i}u_{i} ∉ E(D), and so u_{i}v_{i} ∈ E(D). By (4), s ⇒ t_{i} for i = 1, 2. From the symmetry between t_{1}, t_{2}, we may assume that (s, t_{1}, t_{2}) is clockwise; but then (5) implies that either ϕ^{−1}(s) is strongly anticomplete to ϕ^{−1}(t_{2}), or ϕ^{−1}(s) is strongly complete to ϕ^{−1}(t_{1}), contradicting that the pairs s, t_{1} and s, t_{2} are both mixed. This proves (7).

(8) If s, t is a mixed pair, then every v ∈ ϕ^{−1}(s) has both a neighbour and an antineighbour in ϕ^{−1}(t).

For we may assume that s ⇒ t. Let x, y ∈ ϕ^{−1}(s), and suppose that there exists u ∈ ϕ^{−1}(t) such that x, u are antiadjacent and y, u are adjacent, and there is no u′ ∈ ϕ^{−1}(t) such that x, u′ are adjacent and y, u′ are antiadjacent. We claim that A(x) ⊆ A^{∗}(y) and B(y) ⊆ B^{∗}(x). For suppose that there exists v ∈ A(x)\A^{∗}(y). Now ϕ(v) ≠ s since v ∈ A(x), and ϕ(v) ≠ t since v is adjacent to x and antiadjacent to y; and so s, t, ϕ(v) are all distinct. If s, ϕ(v), t are in clockwise order, then (y, v, u) is clockwise, and the third axiom implies that v ∈ A^{∗}(y), a contradiction. If s, t, ϕ(v) are in clockwise order, then (x, u, v) is clockwise, and the third axiom implies that x, u are strongly adjacent, again a contradiction. This proves that A(x) ⊆ A^{∗}(y). Moreover, A(y) ⊈ A^{∗}(x), since u ∈ A(y) \ A^{∗}(x); so by (2), B(y) ⊆ B^{∗}(x). This proves our claim that A(x) ⊆ A^{∗}(y) and B(y) ⊆ B^{∗}(x).

Let X be the set of all vertices in ϕ^{−1}(s) that are strongly anticomplete to ϕ^{−1}(t), and suppose that X is nonempty. Let Y = ϕ^{−1}(s)\X. Since s, t is a mixed pair, Y ≠ ∅. By (1), there exist x ∈ X and y ∈ Y such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x). But since x is strongly anticomplete to ϕ^{−1}(t) and y is not, it follows that there exists u ∈ ϕ^{−1}(t) such that x, u are antiadjacent and y, u are adjacent, and there is no u′ ∈ ϕ^{−1}(t) such that x, u′ are adjacent and y, u′ are antiadjacent. This contradicts the claim above. Hence X is empty, and so every vertex in ϕ^{−1}(s) has a neighbour in ϕ^{−1}(t).

Now let X be the set of all vertices in ϕ^{−1}(s) that are not strongly complete to ϕ^{−1}(t), and let Y = ϕ^{−1}(s) \ X. Since s, t is a mixed pair, X ≠ ∅. Suppose that Y is nonempty. By (1), there exist x ∈ X and y ∈ Y such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x). But since y is strongly complete to ϕ^{−1}(t) and x is not, it follows that that there exists u ∈ ϕ^{−1}(t) such that x, u are antiadjacent and y, u are adjacent, and there is no u′ ∈ ϕ^{−1}(t) such that x, u′ are adjacent and y, u′ are antiadjacent, again contrary to the claim above. Thus Y = ∅, and so every vertex in ϕ^{−1}(s) has an antineighbour in ϕ^{−1}(t). This proves (8).

(9) If s ∈ Σ and |ϕ^{−1}(s)| > 1, then there exists t ∈ Σ with t ≠ s such that s, t is a mixed pair.

For suppose not; and partition ϕ^{−1}(s) into two nonempty subsets X, Y. By (1), there exist x ∈ X and y ∈ Y such that either A(x) ⊈ A^{∗}(y), or B(y) ⊈ B^{∗}(x). But A(x) = A^{∗}(y) and B^{∗}(x) = B(y) since there is no t satisfying the claim, a contradiction. This proves (9).

By (4), (5), (7), (8), and (9), it follows that (ϕ, D) is a metacircular arrangement of G. This proves 2.1.

3 The main theorem

We begin with some more definitions. Let C be a hole with vertices c_{1}- ⋯ -c_{n}-c_{1} in order. We call the sequence c_{1}- ⋯ -c_{n}-c_{1} an n-numbering of C. Let v ∈ V (G) \ V (C), and let N ⊆ V (C), such that v is adjacent to every member of N and antiadjacent to every member of V (C) \ N. We say that (relative to C):

• v is a hat if N = {c_{i}, c_{i+1}} for some i

• v is a clone if N = {c_{i−1}, c_{i}, c_{i+1}} for some i

• v is a star if n ≥ 5 and N = {c_{i}, c_{i+1}, c_{i+2}, c_{i+3}} for some i

• v is a hub if n ≥ 6 and there exist i, j with 1 ≤ i, j ≤ n such that i − 1, i, i + 1, j − 1, j, j + 1 are all distinct (modulo n) and N = {c_{i}, c_{i+1}, c_{j}, c_{j+1}}

• v is a centre if n ≤ 5 and N = V (C).

If in addition v is strongly adjacent to every member of N and strongly antiadjacent to every member of V (C) \ N, then we say v is a strong hat, clone, star, hub or centre respectively.

Here are two lemmas. The proofs of both are clear, and we omit them.

3.1 Let C be a hole in a claw-free trigraph G, and let v ∈ V (G) \ V (C). Then either:

• v has no neighbours in V (C), or

• v is a hat, clone, star or hub relative to C, or

• C has length ≤ 5 and v is a centre relative to C.

Moreover, if C has vertices c_{1}-c_{2}- ⋯ -c_{n}-c_{1} in order, and v is semiadjacent to say c_{1}, then either v is strongly antiadjacent to one of c_{2}, c_{n} and v is a clone or star relative to C, or n ≤ 5 and v is a centre relative to C.

3.2 Let G be a claw-free trigraph, and let C be a hole in G. Let v_{1}, v_{2} ∈ V (G) \ V (C), and for i = 1, 2, let N_{i}, A_{i} be respectively the sets of neighbours and antineighbours of v_{i} in V (C).

• If there exist x ∈ N_{1} ∩ N_{2} and y ∈ A_{1} ∪ A_{2}, consecutive in C, then v_{1}, v_{2} are strongly adjacent.

• If there exist x, y ∈ N_{1} ∩ A_{2} that are antiadjacent, then v_{1}, v_{2} are strongly antiadjacent.

We need some further definitions. Let C be a hole in a trigraph G, with vertices c_{1}-c_{2}- ⋯ -c_{n}-c_{1} in order. Let v_{1}, …, v_{k} ∈ V (G) \ V (C), and for 1 ≤ i ≤ k let N_{i} ⊆ V (C) such that v_{i} is complete to N_{i} and anticomplete to V (C) \ N_{i}.

• If k = 2 and N_{1} = {c_{i}, c_{i+1}} and N_{2} = {c_{j}, c_{j+1}} for some i, j, and N_{1} ∩ N_{2} = ∅, and v_{1}, v_{2} are adjacent, we call {v_{1}, v_{2}} a hat-diagonal for C.

• If n ≥ 5 and k = 2 and N_{1} = {c_{i}, c_{i+1}} and N_{2} = {c_{i−1}, c_{i}, c_{i+1}, c_{i+2}} for some i, we call {v_{1}, v_{2}} a coronet for C.

• If n ≥ 5 and k = 2 and N_{1} = {c_{i}, c_{i+1}, c_{i+2}, c_{i+3}} and N_{2} = {c_{i+1}, c_{i+2}, c_{i+3}, c_{i+4}} for some i, and v_{1}, v_{2} are antiadjacent, we call {v_{1}, v_{2}} a crown for C.

• If n = 5 or 6 and k = 2 and N_{1} = {c_{i}, c_{i+1}, c_{i+2}, c_{i+3}} and N_{2} = {c_{i+3}, c_{i+4}, c_{i+5}, c_{i+6}} and v_{1}, v_{2} are adjacent, we call {v_{1}, v_{2}} a star-diagonal for C.

• If n = 6 and k = 3 and N_{1} = {c_{i}, c_{i+1}, c_{i+2}, c_{i+3}} and N_{2} = {c_{i+2}, c_{i+3}, c_{i+4}, c_{i+5}} and N_{3} = c_{i−2}, c_{i−1}, c_{i}, c_{i+1}} for some i, and {v_{1}, v_{2}, v_{3}} is a clique, we call {v_{1}, v_{2}, v_{3}} a star-triangle for C.

Now we prove the main result of this paper, the following. (Please note that for some values of n, certain hypotheses of the theorem are vacuous. For instance, if n > 5 then no n-hole has a centre; star-triangles are only possible if n = 6; and so on.)

3.3 Let G be a claw-free trigraph with a hole, and let n be the maximum length of holes in G. Suppose that every n-hole is dominating, and has no hub, coronet, crown, hat-diagonal, star-diagonal, startriangle or centre. Then G is metacircular. Indeed, for every n-hole C, there is a metacircular arrangement (ϕ, D) of G with basis C.

Proof. Let C be an n-hole in G, with a numbering c_{2}-c_{4}-c_{6}- ⋯ -c_{2n}-c_{2} say. Since C is dominating and has no hub or centre, it follows from 3.1 that, relative to C, every vertex of G not in V (C) is either a strong hat, a strong clone, a strong star, or both a hat and a clone, or both a clone and a star.

For every v ∈ V (G), we define π(v) as follows. Let N be the set of neighbours of v in V (C), together with v if v ∈ V (C). Since either v ∈ V (C) or v is a hat, clone or star, there is a unique choice of i ∈ {1, …, 2n} such that N is one of the three sets {c_{i−1}, c_{i+1}}, {c_{i−2}, c_{i}, c_{i+2}}, and {c_{i−3}, c_{i−1}, c_{i+1}, c_{i+3}}. We define π(v) = i.

Let Σ be a circle, with circumference 2n, and let σ_{1}, …, σ_{2n} be equally spaced points of it, in order. For each vertex v of G, we define ϕ(v) = σ_{π(v)}. If u, v ∈ V (G), we define d(u, v) to be the length of the shorter arc of Σ joining ϕ(u), ϕ(v) (or 0, if ϕ(u) = ϕ(v)); thus d(u, v) ≤ n. (For example, d(c_{2}, c_{4}) = 2.)

For i = 1, …, 2n with i even, let C_{i} be the set of all clones v with π(v) = i. (Thus every member of C_{i} is either a strong clone, or both a clone and a hat.) For i odd, let H_{i} and S_{i} be respectively the set of all hats and stars v with π(v) = i. (Every member of H_{i} is a strong hat; and every member of S_{i} is either a strong star, or both a star and a clone.) If n = 4 then the sets S_{i} are all empty, by definition. We read all these subscripts modulo 2n; so for instance H_{2n+1} means H_{1} and so on.

(1) If u, v ∈ V (G) are adjacent and u ∈ V (C) then d(u, v) ≤ 3.

The proof is clear.

(2) If u, v ∈ V (G) are adjacent then d(u, v) ≤ 4.

For since d(u, v) ≤ n, we may assume that n ≥ 5; and by (1) we may assume that u, v ∉ V (C). If either of u, v is a strong hat, then d(u, v) ≤ 4 if u, v have a common neighbour in C, and otherwise the claim follows from 3.2 since there is no hat-diagonal for C; so we assume that u, v both have at least three neighbours in C. Suppose first that u is a star, say u ∈ S_{i} where i is odd. If v is adjacent to c_{i+1}, then

v ∈ S_{i−2} ∪ C_{i−1} ∪ S_{i} ∪ C_{i+1} ∪ S_{i+2} ∪ C_{i+3} ∪ S_{i+4},

and consequently d(u, v) ≤ 4 as required. We assume then that v is strongly antiadjacent to c_{i+1}, and similarly to c_{i−1}. Since {u, v, c_{i−3}, c_{i+1}} is not a claw, it follows that v is strongly adjacent to c_{i−3}, and similarly to c_{i+3}. Since v is not a hub, it follows that n ≤ 6. If n = 6, then v ∈ S_{i+6}, and {u, v} is a star-diagonal for C, a contradiction; while if n = 5, then u ∈ C_{i+5}, and u is a centre for the 5-hole v-c_{i−3}-c_{i−1}-c_{i+1}-c_{i+3}-v, a contradiction. We may therefore assume that u is not a star, and similarly v is not a star. They are therefore both clones; but then d(u, v) ≤ 4 by 3.2. This proves (2).

(3) If u, v ∈ V (G) and d(u, v) ≤ 1 then u, v are strongly adjacent.

For if one of u, v ∈ V (C), this is clear, so we assume both are in V (G) \ V (C). If d(u, v) = 0, then either u, v are both hats, or both clones, or both stars, or one is a star and one is a hat. In the first three cases, u, v are strongly adjacent by 3.2, and in the last case, n ≥ 5 and {u, v} is a coronet for C, a contradiction. Thus if d(u, v) = 0 then the claim holds. We assume then that u ∈ C_{i} and v ∈ H_{i+1} ∪ S_{i+1}. But then u, v are strongly adjacent by 3.2. This proves (3).

If u, v, w ∈ V (G), let us say that v is between u, w if d(u, w) < n, and d(u, v), d(v, w) > 0, and d(u, v) + d(v, w) = d(u, w) (and so ϕ(v) lies on the shorter circle arc between ϕ(u), ϕ(w)).

(4) If u, v, w ∈ V (G) and v is between u, w, and d(u, w) ≥ 4, and u, w are adjacent, then v is strongly adjacent to both u, w.

For then u, w ∉ V (C) by (1), and d(u, w) = 4 by (2). Since d(u, w) < n it follows that n ≥ 5. It suffices from the symmetry to prove that u, v are strongly adjacent, and we therefore assume they are antiadjacent, for a contradiction. Let π(u) = i. We may assume that π(w) = i + 4, and π(v) ∈ {i + 1, i + 2, i + 3}. By (3), π(v) ≠ i + 1, and so π(v) = i + 2 or i + 3. There are two cases, depending whether i is odd or even.

Suppose first that i is even. If π(v) = i + 2, then v, w are antiadjacent, since {w, u, v, c_{i+6}} is not a claw; but then {u, w} is a hat-diagonal for the n-hole obtained from C by replacing c_{i+2} by v, a contradiction. If π(v) = i + 3, then by (3), v, w are adjacent; since {w, u, v, c_{i+6}} is not a claw, v is adjacent to c_{i+6} and hence to c_{i}; and then {u, v} is a crown for the n-hole obtained from C by replacing c_{i+4} by w, a contradiction.

Now suppose that i is odd. Since u, w are adjacent and n ≥ 5, and there is no hat-diagonal, it follows from 3.2 that u, w are both stars, and so u ∈ S_{i}, w ∈ S_{i+4}. If n = 5, then {u, w} is a star-diagonal for C, a contradiction, and so n ≥ 6. If π(v) = i + 2, then by 3.2, v ∉ H_{i+2}, and so v ∈ S_{i+2}; and then {u, v} is a crown for C, a contradiction. If π(v) = i + 3, then v, w are adjacent by (3), but then {w, u, v, c_{i+7}} is a claw, a contradiction. This proves (4).

(5) If u, v, w ∈ V (G) and v is between u, w, and u, w are adjacent, then v is strongly adjacent to both u, w.

For by (4) we may assume that d(u, w) ≤ 3, and by (3) the claim is true if d(u, w) ≤ 2, so we may assume that d(u, w) = 3. Thus exactly one of π(u), π(w) is even; and so from the symmetry we may assume that π(u) is even, π(u) = i say, and π(w) = i + 3, and π(v) is one of i + 1, i + 2. Thus u ∈ C_{i} ∪ {c_{i}} and w ∈ H_{i+3} ∪ S_{i+3}, and v ∈ H_{i+1} ∪ S_{i+1} ∪ C_{i+2} ∪ {c_{i+2}}. Suppose first that v ∈ H_{i+1} ∪ S_{i+1}. Then by (3), u, v are strongly adjacent, and so we may assume that v, w are antiadjacent. Now w is not adjacent to c_{i−2}, since w ∈ H_{i+3} ∪ S_{i+3} (and if n = 4 then w ∈ H_{i+3}, by definition of a star). Since {u, v, w, c_{i−2}} is not a claw, v is adjacent to c_{i−2}, and therefore v ∈ S_{i+1}. Since v, w are antiadjacent, 3.2 implies that w is not a hat, and so w ∈ S_{i+3}; and then {v, w} is a crown for C, a contradiction. Suppose now that v ∈ C_{i+2} ∪{c_{i+2}}. By (1), v, w are strongly adjacent, and so we may assume that u, v are antiadjacent. If w ∈ S_{i+3} then n ≥ 5 and {w, u, v, c_{i+6}} is a claw, a contradiction; and if w ∈ H_{i+3} then w, c_{i} are strongly antiadjacent, and so u ≠ c_{i}, and {u, w} is a hat-diagonal for the n-hole induced on (V (C) \ {c_{i+2}}) ∪ {v}, a contradiction. This proves (5).

(6) If u, v ∈ V (G) are adjacent, then d(u, v) < n.

By (2) we assume that d(u, v) = n = 4. From (1), u, v ∉ V (C), and since n = 4, there are no stars relative to C. Thus u, v are both hats or both clones. If they are both hats, then {u, v} is a hat-diagonal for C, a contradiction. If they are both clones, say u ∈ C_{2}, v ∈ C_{6}, then v is a centre for the 4-hole u-c_{4}-c_{6}-c_{8}-u, a contradiction. This proves (6).

Fix an orientation of Σ, called clockwise. Define a direction D of G as follows. For all distinct u, v ∈ V (G) that are adjacent in G, if ϕ(u) ≠ ϕ(v) then by (6), one of the arcs of Σ between ϕ(u), ϕ(v) has length < n (and therefore the other has length > n). We call this shorter arc the route between ϕ(u), ϕ(v). Let e be the edge of D with ends u, v. Direct e from u to v if moving clockwise along Σ from ϕ(u) to ϕ(v) traverses the route between ϕ(u), ϕ(v); and otherwise direct e from v to u. For each σ ∈ Σ, direct the edges of D with both ends in ϕ^{−1}(σ) in such a way that there is no directed cycle with vertex set in ϕ^{−1}(σ).

(7) Every directed cycle in D has length at least four.

For certainly there is no directed cycle of length at most two. Suppose that a_{1}-a_{2}-a_{3}-a_{1} is a directed cycle of length three. Not all of ϕ(a_{1}), ϕ(a_{2}), ϕ(a_{3}) are equal, and so we may assume that ϕ(a_{2}), ϕ(a_{3}) ≠ ϕ(a_{1}). Thus moving clockwise along Σ from ϕ(a_{1}) to ϕ(a_{2}), and then moving clockwise from ϕ(a_{2}) to ϕ(a_{3}), traverses the route between ϕ(a_{1}), ϕ(a_{2}) and then traverses the route between ϕ(a_{2}), ϕ(a_{3}). Since both these arcs have length < n by (6), it follows that ϕ(a_{2}), ϕ(a_{3}) are different, and ϕ(a_{1}), ϕ(a_{2}), ϕ(a_{3}) are in clockwise order, and the three routes joining pairs of them have union Σ. Since a_{1}, a_{2} are adjacent, it follows that d(a_{1}, a_{2}) ≤ 4 by (2); and similarly d(a_{2}, a_{3}), d(a_{3}, a_{1}) ≤ 4. Since the three routes have union the whole circle of length 2n, it follows 2n ≤ 12, and so n ≤ 6.

Suppose first that n = 6. Then equality holds throughout. Hence we may assume that either π(a_{1}) = 1, π(a_{2}) = 5 and π(a_{3}) = 9, or π(a_{1}) = 2, π(a_{2}) = 6 and π(a_{3}) = 10. In the first case, at most one of a_{1}, a_{2}, a_{3} is a hat, since there is no hat-diagonal; and then 3.2 implies that none of a_{1}, a_{2}, a_{3} is a hat, and so {a_{1}, a_{2}, a_{3}} is a star-triangle for C, a contradiction. In the second case, a_{3}-c_{12}-c_{2}-c_{4}-c_{6}-c_{8}-a_{3} is a 6-hole, and {a_{1}, a_{2}} is a star-diagonal for it, a contradiction. Thus n < 6.

Suppose next that n = 5. Then the sum of d(a_{1}, a_{2}), d(a_{2}, a_{3}) and d(a_{3}, a_{1}) is at least 10, and so we may assume that d(a_{1}, a_{2}) = 4. Suppose that a_{1} is a star, say a_{1} ∈ S_{1}; then we may assume that a_{2} ∈ H_{5} ∪ S_{5}. By 3.2, a_{2} ∉ H_{5}, and if a_{2} ∈ S_{5} then {a_{1}, a_{2}} is a star-diagonal for C, a contradiction. Thus a_{1} is not a star, and similarly a_{2} is not a star. Not both a_{1}, a_{2} are hats, since {a_{1}, a_{2}} is not a hat-diagonal for C. Thus we may assume that a_{1} ∈ C_{2} ∪ {c_{2}}, and a_{2} ∈ C_{6} ∪ {c_{6}}, and therefore

c_{3} ∈ C_{8} ∪ {c_{8}} ∪ H_{9} ∪ S_{9} ∪ C_{10} ∪ {c_{10}}.

Since a_{1}, a_{2} are adjacent, a_{1} ≠ c_{2} and a_{2} ≠ c_{6}. Now a_{3} ≠ c_{8} since c_{8} is not adjacent to a_{1}, and similarly a_{3} ≠ c_{10}. If a_{3} is antiadjacent to c_{2}, then a_{1} is a centre for the 5-hole a_{2}-a_{3}-c_{10}-c_{2}-c_{4}-a_{2}, a contradiction. Thus a_{3} is adjacent to c_{2} and similarly to c_{6}, and so a_{3} ∈ S_{9}. But then {a_{2}, a_{3}} is a star-diagonal for the 5-hole a_{1}-c_{4}-c_{6}-c_{8}-c_{10}-a_{1}, a contradiction. Thus n ≠ 5.

Consequently n = 4. By (6), we may assume that a_{1} ∈ C_{2}∪{c_{2}}, a_{2} ∈ H_{5}, and a_{3} ∈ H_{7}∪C_{8}∪{c_{8}}. Then a_{2} is a centre for the 4-hole a_{1}-c_{4}-c_{6}-a_{3}-a_{1}, a contradiction. This proves (7).

We claim that (ϕ, D) is a circle arrangement of G. The first axiom holds by (3), the second by (7), the third by (5), and the fourth by (6). Hence (ϕ, D) is a circle arrangement of G. Moreover, C is a basis for (ϕ, D), and the result follows from 2.1. This proves 3.3.

Next we prove a corollary of 3.3 that is a little more convenient to apply. We need another definition. Let A, B ⊆ V (G). We call (A, B) a W-join if

• A, B are disjoint nonempty strong cliques of G, and at least one of A, B has at least two members

• every member of V (G) \ (A ∪ B) is either strongly A-complete or strongly A-anticomplete and either strongly B-complete or strongly B-anticomplete, and

• A is neither strongly complete to B nor strongly anticomplete to B.

Indeed, in this paper we find that our W-joins have a stronger property, that

• no member of A is strongly B-complete or strongly B-anticomplete, and no member of B is strongly A-complete or strongly A-anticomplete.

If this property also holds, we call the W-join proper. A W-join (A, B) is coherent if the set of all strongly (A ∪ B)-complete vertices in V (G) \ (A ∪ B) is a strong clique.

3.4 Let G be a claw-free trigraph, with a hole, and let n be the maximum length of holes in G. Suppose that every n-hole is dominating, and has no hub, coronet, crown, hat-diagonal, star-diagonal, star-triangle or centre. Then either G admits a coherent proper W-join, or G is a long circular interval trigraph.

Proof. By 3.3, G is metacircular; choose a metacircular arrangement (ϕ, D) of G. If |ϕ^{−1}(σ)| ≤ 1 for each σ ∈ Σ, then G is a long circular interval trigraph. Thus we may assume that |ϕ^{−1}(σ_{1})| > 1 for some σ_{1} ∈ Σ. By the fifth and sixth conditions in the definition of a metacircular arrangement, there is a unique σ_{2} ∈ Σ with σ_{2} ≠ σ_{1} such that ϕ^{−1}(σ_{1}) is neither strongly complete nor strongly anticomplete to ϕ^{−1}(σ_{2}); and every vertex in ϕ^{−1}(σ_{1}) has both a neighbour and an antineighbour in ϕ^{−1}(σ_{2}), and vice versa. Thus, (ϕ^{−1}(σ_{1}), ϕ^{−1}(σ_{2})) is a proper W-join, and we claim that it is coherent. Let X_{i} = ϕ^{−1}(σ_{i}) (i = 1, 2), and choose v_{i} ∈ X_{i} (i = 1, 2), such that v_{1}, v_{2} are adjacent in G. From the symmetry, we may assume that v_{1}v_{2} ∈ E(D). Let S be the set of all σ ∈ Σ such that σ_{2}, σ_{1}, σ are in clockwise order; and let N be the union of all the sets ϕ^{−1}(σ) (σ ∈ S). Then N is a strong clique, by the fourth condition in the definition of a metacircular arrangement. Let v ∈ V (G) \ (X_{1} ∪ X_{2}) be complete to X_{1} ∪ X_{2}. To prove that (X_{1}, X_{2}) is coherent, it suffices to show that v ∈ N. Now v ∈ ϕ^{−1}(σ_{3}) for some σ_{3} ∈ Σ, and σ_{1}, σ_{2}, σ_{3} are all different. Suppose first that σ_{1}, σ_{2}, σ_{3} are in clockwise order. Since X_{1} is not strongly complete to X_{2}, it follows that v_{1}v ∉ E(D) and vv_{2} ∉ E(D) from the fourth condition in the definition of a metacircular arrangement. Hence v-v_{1}-v_{2}-v is a directed cycle of D, a contradiction. Thus σ_{2}, σ_{1}, σ_{3} are in clockwise order, and so σ_{3} ∈ S, and therefore v ∈ N as required. This proves 3.4.

4 Circular interval graphs

In this section we derive 1.1 from 3.3, but we need several more definitions. We say that a trigraph G is a linear interval trigraph if the vertices of G can be numbered v_{1}, …, v_{n} such that for all i, j with 1 ≤ i < j ≤ n, if v_{i} is adjacent to v_{j} then {v_{i}, v_{i+1}, …, v_{j−1}} and {v_{i+1}, v_{i+2}, …, v_{j}} are strong cliques. (Linear interval trigraphs are a subclass of long circular interval trigraphs, as may easily be checked.)

Two 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”. Let (V_{1}, V_{2}) be 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.

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

• A_{1} ∪ A_{2} is a strong clique, and for i = 1, 2, A_{i}, V_{i} \ A_{i} are both nonempty, and

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

In these circumstances, we say that (V_{1}, V_{2}) is a 1-join. We start with the following lemma.

4.1 Let G be a claw-free trigraph with no hole, that is not a linear interval trigraph. Then G contains a net or antinet. Moreover, either G is an antinet, or G admits a 0-join, a 1-join, or twins.

Proof. We proceed by induction on |V (G)|. If there exist u, v ∈ V (G) that are twins, then the trigraph obtained from G by deleting v is also not a linear interval graph, and the result follows from the inductive hypothesis. Thus we may assume that G does not admit twins. If (V_{1}, V_{2}) is a 0-join, then one of G|V_{1}, G|V_{2} is not a linear interval graph, and again the result follows from the inductive hypothesis. So we may assume that G does not admit a 0-join.

Since G has no hole, the adjacency relation of G defines a chordal graph, and therefore (by a well-known folklore theorem) there is a tree T and a family (T_{v} : v ∈ V (G)) of subtrees of T such that for all distinct u, v ∈ V (G), V (T_{u} ∩ T_{v}) ≠ ∅ if and only if u, v are adjacent in G. Choose such a tree T with |V (T)| minimum.

(1) For every edge st of T, there exist u, v ∈ V (G), strongly antiadjacent, such that T_{u} contains s and not t, and T_{v} contains t and not s.

For let e be the edge st. Let T′ be the tree obtained from T by contracting the edge st. For each v ∈ V (G), let T′_{v} = T_{v} if s, t ∉ V (T_{v}), and otherwise let S be the subtree of T with edge-set E(T_{v}) ∪ {e}, and let T′_{v} be the subtree of T′ obtained from S by contracting e. For all distinct u, v ∈ V (G), if u, v are adjacent then V (T_{u} ∩ T_{v}) ≠ ∅ and so V (T′_{u} ∩ T′_{v}) ≠ ∅; and hence from the minimality of |V (T)|, the converse is false. In other words, there exist strongly antiadjacent u, v ∈ V (G) such that V (T_{u} ∩ T_{v}) = ∅ and V (T′_{u} ∩ T′_{v}) ≠ ∅. This proves (1).

(2) For all distinct u, v ∈ V (G), if u, v are semiadjacent then |V (T_{u} ∩ T_{v})| = 1 and the unique vertex in T_{u} ∩ T_{v} is incident with at most one edge in T_{u}, and with at most one edge in T_{v}.

For suppose first that |V (T_{u} ∩ T_{v})| > 1; then we may choose distinct s, t ∈ V (T_{u} ∩ T_{v}), adjacent in T. By (1), there exist w, x ∈ V (G), strongly antiadjacent, with s ∈ V (T_{w}) \ V (T_{x}) and t ∈ V (T_{x}) \ V (T_{w}). Since the trees T_{u}, T_{w}, T_{x} are distinct, it follows that u, w, x are all distinct, and similarly so are v, w, x; and so u, v, w, x are all different. Since s ∈ V (T_{u} ∩T_{w}), it follows that u, w are adjacent, and similarly the pairs ux, vw, vx are adjacent. Since w-u-x-v-w is not a 4-hole, we deduce that u, v are strongly adjacent. This proves that there is a vertex s ∈ V (T) with V (T_{u} ∩ T_{v}) = {s}. To prove the second assertion, suppose that, say, s is incident with two edges st_{1} and st_{2} of T_{u}. For i = 1, 2, there is by (1) a vertex v_{i} ∈ V (G) such that t_{i} ∈ V (T_{v_{i}}) and s ∉ V (T_{v_{i}}). But then T_{v_{1}}, T_{v_{2}}, T_{v} are pairwise vertex-disjoint, and so v_{1}, v_{2}, v are pairwise strongly antiadjacent, and therefore {u, v, v_{1}, v_{2}} is a claw, a contradiction. This proves (2).

(3) If T is a path then the theorem holds.

For let T be a path, with vertices t_{1}, …, t_{m} in order. For each v ∈ V (G), T_{v} is a nonempty subpath of T, say from t_{a(v)} to t_{b(v)}, where 1 ≤ a(v) ≤ b(v) ≤ m. For distinct u, v ∈ V (G), write u < v if a(u) ≤ a(v) and b(u) ≤ b(v), and if T_{u} = T_{v} then there exists w ∈ V (G) \ {u, v} with T_{w} ≠ T_{u}(= T_{v}) such that either • w is semiadjacent to v with a(w) ≤ a(v) and b(w) ≤ b(v), or

• w is semiadjacent to u with a(u) ≤ a(w) and b(u) ≤ b(w).

We claim that for all distinct u, v ∈ V (G), either u < v or v < u, and not both. For let u, v ∈ V (G) be distinct, and suppose first that a(u), a(v) are distinct, say a(u) < a(v). If also b(u) ≤ b(v) then u < v and v ≮ u as claimed, so we may assume that b(u) > b(v). By (1), there exist x, y ∈ V (G) such that T_{x} contains t_{a(u)} and not t_{a(u)+1}, and T_{y} contains t_{b(u)} and not t_{b(u)−1}. But then {u, v, x, y} is a claw in G, a contradiction. This proves our claim when a(u) ≠ a(v), and similarly it holds when b(u) ≠ b(v). Now we assume that a(u) = a(v) and b(u) = b(v). Hence u, v have the same neighbours, except for each other. Since G does not admit twins, there is a vertex w ≠ u, v that is semiadjacent to one of u, v. Suppose first that a(u) = b(u), and let Z be the set of all z ∈ V (G) with t_{a(u)} ∈ V (T_{z}). Then Z is a clique in G, and since G has no 4-hole, it follows that at most one pair of vertices in Z is semiadjacent. In particular, since u, v, w ∈ Z, it follows that w is the only vertex that is semiadjacent to one of u, v. If a(w) < a(u), then w < u as we already saw, and in particular b(w) = a(u), and just one of the statements u < v and v < u is true, as required. So we may assume that a(w) ≥ a(u), and since t_{a(u)} ∈ V_{w}, it follows that a(w) = a(u). Similarly b(w) = b(u); but then w and one of u, v are twins, a contradiction. This proves the claim if a(u) = b(u). We may therefore assume that a(u) < b(u), and hence from (2) we may assume that a(w) ≤ b(w) = a(u) < b(u). If no other vertex is semiadjacent to one of u, v then the claim holds, so we may assume that there exists x ≠ u, v, w, semiadjacent to one of u, v. As before, let Z be the set of all z ∈ V (G) with t_{a(u)} ∈ V (T_{z}); then at most one pair of vertices in Z is semiadjacent. Since u, v, w ∈ Z, it follows that x ∉ Z, and so b(u) = a(x) ≤ b(x) from (2). Since one of w, x is semiadjacent to u and the other to v (because F (G) is a matching), we deduce that again the claim holds. This proves our claim that for all distinct u, v, either u < v or v < u and not both.

Next we claim that this relation is transitive. For suppose not; then there exist distinct u, v, w ∈ V (G) such that u < v < w < u. Thus a(u) ≤ a(v) ≤ a(w) ≤ a(u), and so a(u) = a(v) = a(w), and similarly b(u) = b(v) = b(w). Since w < u, we may assume that there exists x ∈ V (G) \ {u, w} semiadjacent to w with a(w) ≤ a(x) and b(w) ≤ b(x) and with T_{x} ≠ T_{w}. But then w < v, a contradiction. This proves that the relation is transitive, and therefore is a total order. Hence we may number the vertices of G as v_{1}, …, v_{n} such that v_{i} < v_{j} for 1 ≤ i < j ≤ n.

Now suppose that 1 ≤ h < k ≤ n and v_{h}, v_{k} are adjacent. To prove that G is a linear interval trigraph, we must show that {v_{h}, …, v_{k−1}} and {v_{h+1}, …, v_{k}} are strong cliques, and from the symmetry it suffices to show the former. Let h ≤ i < j ≤ k −1; we shall prove that v_{i}, v_{j} are strongly adjacent. Since h < k and therefore v_{h} < v_{k}, we deduce that a(v_{h}) ≤ a(v_{k}) and b(v_{h}) ≤ b(v_{k}); and since v_{h}, v_{k} are adjacent, it follows that a(v_{k}) ≤ b(v_{h}). Thus

a(v_{h}) ≤ a(v_{k}) ≤ b(v_{h}) ≤ b(v_{k}).

Now h ≤ i < j ≤ k − 1, and so

a(v_{h}) ≤ a(v_{i}) ≤ a(v_{j}) ≤ a(v_{k−1}) ≤ a(v_{k})

and

b(v_{h}) ≤ b(v_{i}) ≤ b(v_{j}) ≤ b(v_{k−1}) ≤ b(v_{k}).

Consequently, a(v_{i}) ≤ a(v_{k}) ≤ b(v_{h}) ≤ b(v_{i}), and similarly a(v_{j}) ≤ a(v_{k}) ≤ b(v_{j}). It follows that a(v_{k}) belongs to both T_{v_{i}} and T_{v_{j}}, and therefore v_{i}, v_{j} are weakly adjacent. Suppose they are not strongly adjacent. Then by (2), a(v_{k}) is the unique vertex in both T_{v_{i}} and T_{v_{j}}, and since a(v_{i}) ≤ a(v_{j}) and b(v_{i}) ≤ b(v_{j}), (2) implies that b(v_{i}) = a(v_{j}). Now

a(v_{j}) ≤ a(v_{k}) ≤ b(v_{h}) ≤ b(v_{i}) = a(v_{j}),

and so a(v_{j}) = a(v_{k}) = b(v_{h}). Suppose that b(v_{j}) < b(v_{k}). Then by (1), there exists u ∈ V (G) such that t_{b(v_{j})} ∉ V (T_{u}) and t_{b(v_{k})} ∈ V (T_{u}). Hence b(v_{j}) < a(u), and so v_{i}, u are antiadjacent; but then v_{i}, v_{j}, u are pairwise antiadjacent (since v_{i}, v_{j} are semiadjacent) and all three are adjacent to v_{k} (because a(v_{k}) belongs to T_{v_{i}} and to T_{v_{j}}, and b(v_{k}) belongs to T_{u}), and therefore {v_{k}, u, v_{i}, v_{j}} is a claw, a contradiction. Thus b(v_{j}) ≥ b(v_{k}), and since j < k it follows that b(v_{j}) = b(v_{k}), and so T_{v_{j}} = T_{v_{k}}. But there exists w ∈ V (G) \ {v_{j}, v_{k}} with T_{w} ≠ T_{v_{j}} and with a(w) ≤ a(v_{j}) and b(w) ≤ b(v_{j}) that is semiadjacent to v_{j}, namely w = v_{i}, and so v_{k} < v_{j}, a contradiction. This proves that v_{i}, v_{j} are strongly adjacent, and so G is a linear interval trigraph. This proves (3).

In view of (3), we may assume that there is a vertex t_{0} of T with d neighbours t_{1}, …, t_{d} in T, where d ≥ 3. Let Y be the set of all v ∈ V (G) such that t_{0} ∈ V (T_{v}); thus, Y is a clique of G. For 1 ≤ i ≤ d, let X_{i} be the set of all v ∈ V (G) such that V (T_{v}) contains t_{i} and not t_{0}, and let Y_{i} be the set of all v ∈ Y with t_{0}, t_{i} ∈ V (T_{v}). By (1), X_{i} ≠ ∅, for 1 ≤ i ≤ d; choose x_{i} ∈ X_{i}. Since t_{i} ∈ V (T_{x_{i}}), it follows that every member of Y_{i} is adjacent to x_{i}.

(4) For 1 ≤ i ≤ d, ∅ ≠ Y_{i} ≠ Y.

For suppose that Y_{1} = ∅ say. Let S_{1}, S_{2} be the two components of T \ e, where e is the edge t_{0}t_{1}. For j = 1, 2, let A_{j} be the set of all v ∈ V (G) such that V (T_{v}) ⊆ V (S_{j}); then since Y_{1} = ∅, A_{1} ∪ A_{2} = V (G). Since each T_{v} has at least one vertex, A_{1} ∩ A_{2} = ∅. Moreover, by (1) A_{1}, A_{2} ≠ ∅; and if v_{1} ∈ A_{1} and v_{2} ∈ A_{2} then V (T_{v_{1}} ∩ T_{v_{2}}) = ∅, and so v_{1}, v_{2} are strongly antiadjacent. It follows that G admits a 0-join, a contradiction. This proves that Y_{i} ≠ ∅, for 1 ≤ i ≤ d. Moreover, by (1) there exists v ∈ V (G) such that T_{v} contains t_{0} and not t_{i}, and therefore v ∈ Y \ Y_{i}; and consequently Y_{i} ≠ Y for 1 ≤ i ≤ d. This proves (4).

(5) For 1 ≤ i < j ≤ d, either Y_{i} ∩ Y_{j} = ∅ or Y_{i} ∪ Y_{j} = Y; and for 1 ≤ i < j < k ≤ d, Y_{i} ∩ Y_{j} ∩ Y_{k} = ∅.

For if y ∈ Y_{i} ∩ Y_{j} and y′ ∈ Y \ (Y_{i} ∪ Y_{j}), then {y, y′, x_{i}, x_{j}} is a claw, a contradiction; and if y ∈ Y_{i} ∩ Y_{j} ∩ Y_{k}, then {y, x_{i}, x_{j}, x_{k}} is a claw, a contradiction. This proves (5).

(6) Either Y_{1}, …, Y_{d} are pairwise disjoint, or d = 3 and every vertex of Y is in exactly two of the sets Y_{1}, Y_{2}, Y_{3}.

For if i, j ∈ {1, …, d} are distinct, let us say that the pair (i, j) is big if Y_{i} ∩ Y_{j} ≠ ∅. We claim that if (i, j) is big, then (i, k) is big for all k ∈ {1, …, d} with k ≠ i. For suppose not; then j ≠ k, and Y_{k} ∩ Y_{i} = ∅. Since Y_{i} ∩ Y_{j} ≠ ∅, (5) implies that Y_{i} ∪ Y_{j} = Y, and therefore Y_{k} ⊆ Y_{j}, contrary to (4) and (5) (applied to the pair j, k). This proves our claim. Hence either no pair is big, or every pair is big. In the first case the claim holds, so we assume the second. By the final statement of (5), no vertex of Y belongs to three of the sets Y_{1}, …, Y_{d}; and yet by the first assertion of (5), the sets Y \ Y_{i} (1 ≤ i ≤ d) are pairwise disjoint, and so every vertex in Y is in at least d−1 of the set Y_{1}, …, Y_{d}. Consequently d = 3 and the second statement of (6) holds. This proves (6).

(7) Y is a strong clique.

For suppose that u, v ∈ Y are antiadjacent. Suppose first that for some i, u, v ∉ Y_{i}. Choose y_{i} ∈ Y_{i}; then {y_{i}, x_{i}, u, v} is a claw, a contradiction. So each of Y_{1}, …, Y_{d} contains one of u, v, and in particular Y_{1}, …, Y_{d} are not pairwise disjoint, since d ≥ 3; and so by (6), d = 3 and every vertex of Y is in exactly two of the sets Y_{1}, Y_{2}, Y_{3}. We may therefore assume that u ∈ Y_{1} ∩ Y_{3} and v ∈ Y_{2} ∩ Y_{3}, say. By (1) there exists y ∈ V (G) such that V (T_{y}) contains t_{0} and not t_{3}; but then u-y-v-x_{3}-u is a 4-hole, a contradiction. This proves (7).

For 1 ≤ i ≤ d, let S_{i} be the component of T \ {t_{0}} that contains t_{i}; and let V_{i} be the set of all v ∈ V (G) with T_{v} a subtree of S_{i} \ {t_{i}}. It follows that Y and the sets X_{i}, V_{i} (1 ≤ i ≤ d) are pairwise disjoint and have union V (G).

(8) If Y_{1}, …, Y_{d} are pairwise disjoint, then G contains a net and G admits a 1-join.

For suppose that Y_{1}, …, Y_{d} are pairwise disjoint. Choose y_{i} ∈ Y_{i} for i = 1, 2, 3; then the trigraph induced on {x_{1}, x_{2}, x_{3}, y_{1}, y_{2}, y_{3}} is a net, so G contains a net. Moreover, Y is a strong clique, and we claim that

(V_{1} ∪ X_{1} ∪ Y_{1}, V (G) \ (V_{1} ∪ X_{1} ∪ Y_{1}))

is a 1-join. To show this, it suffices to check that if u ∈ V_{1} ∪ X_{1} ∪ Y_{1} and v ∈ V (G) \ (V_{1} ∪ X_{1} ∪ Y_{1}) then u, v are strongly anticomplete unless u ∈ Y_{1} and v ∈ Y. Since v ∉ V_{1} ∪ X_{1} ∪ Y_{1}, it follows that T_{v} ⊈ S_{1} and t_{1} ∉ V (T_{v}); and so T_{v} is disjoint from S_{1}. If T_{u} ⊆ S_{1} then T_{u} ∩T_{v} is empty and therefore u, v are strongly antiadjacent as required, so we may assume that T_{u} ⊈ S_{1}. Consequently u ∈ Y_{1}, and t_{0}, t_{1} ∈ V (T_{u}). Since Y_{1}, Y_{2}, …, Y_{d} are pairwise disjoint, it follows that u does not belong to Y_{2} ∪ ⋯ ∪ Y_{d}, and therefore t_{2}, …, t_{d} ∉ V (T_{u}). If t_{0} ∉ V (T_{v}), then again T_{u}, T_{v} are disjoint and the claim follows; and if t_{0} ∈ V (T_{v}), then v ∈ Y and again the claim holds. Thus in this case G admits a 1-join. This proves (8).

In view of (6) and (8), we may therefore assume that d = 3 and every vertex in Y is in exactly two of Y_{1}, Y_{2}, Y_{3}. Choose y_{i} ∈ Y_{i} for i = 1, 2, 3; then the trigraph induced on {x_{1}, x_{2}, x_{3}, y_{1}, y_{2}, y_{3}} is an antinet, so G contains an antinet. Moreover, for every v ∈ V (G), if t_{0} ∈ V (T_{v}) then t_{0} is incident with exactly two edges of T_{v}. We may also assume that the same is true for every vertex of T with degree at least three. We deduce that

• every vertex of T has degree at most three

• for every v ∈ V (G), T_{v} is a path in T, and both its ends (or its end, if it is a path of length zero) have degree at most two in T

• for every two edges of T that have a common end of degree three in T, there exists v ∈ V (G) such that both these edges belong to T_{v} (this follows from (4)).

(9) If u, v ∈ V (G) and V (T_{u} ∩ T_{v}) ≠ ∅, then T_{u} contains an end of T_{v} and vice versa.

For suppose that no end of T_{u} belongs to T_{v}. Then u ≠ v, and since some vertex of T_{u} belongs to T_{v}, it follows that T_{u} has length at least two; let its ends be s, t. By (1), there exists w ∈ V (G) such that V (T_{u} ∩ T_{w}) = {s}, and there exists x ∈ V (G) such that V (T_{u} ∩ T_{x}) = {t}. In particular, T_{v}, T_{w}, T_{x} are pairwise disjoint, and so {u, v, w, x} is a claw, a contradiction. This proves (9).

(10) If v ∈ V (T) and some vertex of T_{v} has degree three in T, then T_{v} is a path of length two.

For let t_{0} ∈ V (T_{v}) have degree three in T. Then t_{0} is an internal vertex of the path T_{v}; let T_{v} have ends s_{1}, s_{2}, and let P_{1}, P_{2} be the paths of T between t_{0} and s_{1}, s_{2} respectively. Thus T_{v} = P_{1} ∪ P_{2}. Let t_{1}, t_{2}, t_{3} be the neighbours of t_{0} in T, where t_{i} ∈ V (P_{i}) for i = 1, 2. Certainly P_{v} has length at least two; suppose it has length at least three. Then from the symmetry we may assume that P_{1} has length at least two. Thus t_{1} ≠ s_{1}; let t′_{1} be the neighbour of t_{1} in P_{1} different from t_{0}. From (1), there exists u ∈ V (G) such that T_{u} contains t_{1} and not t′_{1}. By (9), one of s_{1}, s_{2} belongs to T_{u}, and therefore s_{2} ∈ V (T_{u}), and so P_{2} is a path in T_{u}. Choose w ∈ V (G) such that T_{w} contains t_{1}, t_{0}, t_{3} (such a vertex exists, by the displayed statements above). Then by (9), some end of T_{v} belongs to T_{w}, and so s_{1} ∈ V (T_{w}). Also, some end of T_{w} belongs to T_{v}, and therefore s_{1} is an end of T_{w}. By (9) again, some end of T_{w} belongs to T_{u}, and this is impossible, since s_{1} ∉ V (T_{u}) (because t′_{1} ∉ V (T_{u})), and the other end of T_{w} is separated from T_{u} by the edge t_{0}t_{3}. This proves (10).

Now choose t_{0} ∈ V (T) with degree three, and define Y and t_{i}, Y_{i}, X_{i}, V_{i} (i = 1, 2, 3) as in (4)–(8). We see that if u ∈ V_{1} and v ∈ Y_{1} then T_{u}, T_{v} are disjoint (by (10)); and so V_{1} is strongly anticomplete to Y_{1} and hence to V (G) \ (V_{1} ∪ X_{1}). Moreover, X_{1} is strongly anticomplete to V (G) \ (V_{1} ∪ X_{1} ∪ Y_{1}) (for if u ∈ X_{1} and v ∈ V (G) \ (V_{1} ∪ X_{1} ∪ Y_{1}) then T_{u}, T_{v} are separated in T by the edge t_{0}t_{1}). Third, we claim that X_{1} ∪ Y_{1} is a strong clique. For suppose that u, v ∈ X_{1} ∪ Y_{1} are antiadjacent. By (7), not both u, v ∈ Y, and so we may assume that u ∈ X_{1}, and v ∉ Y_{2}. Choose y_{2} ∈ Y_{1} ∩Y_{2}, and x_{2} ∈ X_{2} (these exist, by (4) and (1)); then {y_{2}, x_{2}, u, v} is a claw, a contradiction. This proves that X_{1} ∪ Y_{1} is a strong clique. Since V_{1} ∪ X_{1} ∪ Y_{1} ≠ V (G), it follows that if V_{1} ≠ ∅ then (V_{1} ∪ X_{1}, V (G) \ (V_{1} ∪ X_{1})) is a 1-join as required; so we may assume that V_{1} = ∅, and similarly V_{2} = V_{3} = ∅. Since X_{1} ∪ Y_{1} is a strong clique, all members of X_{1} are twins, and so |X_{1}| = 1, and similarly |X_{2}| = |X_{3}| = 1; and since also Y is a strong clique, all members of Y_{i} are twins for i = 1, 2, 3, and so |Y_{i}| = 1 (i = 1, 2, 3). But then G is an antinet, as required. This proves 4.1.

Now we prove 1.1, which we restate (note that this is a theorem about graphs, not trigraphs):

4.2 Let G be a graph. Then G is a long circular interval graph if and only if no induced subgraph is a claw, net, antinet or (1, 1, 1)-prism, and every hole is dominating and has no centre.

Proof. The “only if” statement is easy, and we omit it. For the “if” part, let G be a graph such that no induced subgraph is a claw, net, antinet or (1, 1, 1)-prism, and such that every hole in G is dominating and has no centre. By 4.1, we may assume that G has a hole. Let the longest hole in G have length n, and let C_{0} be an n-hole.

(1) There is a metacircular arrangement (ϕ, D) of G with basis C_{0}.

For by 3.3, it suffices to show that every n-hole is dominating, and has no hub, coronet, crown, hat-diagonal, star-diagonal, star-triangle or centre. Let C be an n-hole, with vertices c_{1}- ⋯ -c_{n}-c_{1} say. By hypothesis, C is dominating and has no centre. If it has a hub v, then there are two holes with vertex set in V (C) ∪ {v} different from C, and both are nondominating, a contradiction. Similarly C has no coronet.

Suppose that there is a crown for C; then n ≥ 5 and there are nonadjacent stars s_{1}, s_{2}, adjacent say to c_{1}, …, c_{4} and to c_{2}, …, c_{5} respectively. If n ≥ 6, the hole s_{1}-c_{2}-s_{2}-c_{4}-s_{1} is not dominating, since c_{6} has no neighbour in it. If n = 5, then the subgraph induced on {c_{1}, c_{2}, c_{4}, c_{5}, s_{1}, s_{2}} is a (1, 1, 1)-prism, a contradiction. Thus there is no crown for C.

Suppose that there is a hat-diagonal for C; that is, there are adjacent hats h_{1}, h_{2} ∈ V (G) \ V (C), where h_{1} is adjacent to c_{1}, c_{2} say, and h_{2} is adjacent to c_{i}, c_{i+1}, for some i with 3 ≤ i < n. If i ≥ 4 then the hole h_{1}-h_{2}-c_{i+1}-c_{i+2}- ⋯ -c_{1}-h_{1} is not dominating, since c_{3} has no neighbour in it, a contradiction. Thus i = 3 and similarly i + 1 = n, and so n = 4. But then the subgraph induced on V (C) ∪ {h_{1}, h_{2}} is a (1, 1, 1)-prism, a contradiction. Thus there is no hat-diagonal for C.

Suppose that there is a star-diagonal for C; that is, n = 5 or 6, and there are adjacent stars s_{1}, s_{2} adjacent respectively to c_{n−1}, c_{n}, c_{1}, c_{2} and c_{2}, c_{3}, c_{4}, c_{5} say. Then s_{2} is a centre for the (n − 1)-hole s_{1}-c_{2}-c_{3}- ⋯ -c_{n−1}-s_{1}, a contradiction. Finally, suppose that there is a star-triangle for C; that is, n = 6 and there are three pairwise adjacent stars s_{1}, s_{2}, s_{3} adjacent respectively to c_{1}, …, c_{4}, to c_{3}, …, c_{6} and to c_{5}, c_{6}, c_{1}, c_{2}. Then s_{2} is a centre for the 4-hole s_{1}-c_{4}-c_{5}-s_{3}-s_{1}, a contradiction. Thus the hypotheses of 3.3 are satisfied, and consequently this proves (1).

Let (ϕ, D) be as in (1). Suppose that |ϕ^{−1}(σ_{1})| > 1 for some σ_{1} ∈ Σ. From the fifth axiom for a metacircular arrangement, there exists σ_{2} ∈ Σ with σ_{2} ≠ σ_{1}, such that X_{1} is neither complete nor anticomplete to X_{2}, and every vertex in X_{1} has both a neighbour and a nonneighbour in X_{2}, and vice versa, where X_{i} = ϕ^{−1}(σ_{i}) (i = 1, 2). Choose u_{1} ∈ X_{1} with as many neighbours in X_{2} as possible. Choose v_{2} ∈ X_{2} nonadjacent to u_{1}. Let v_{1} ∈ X_{1} be a neighbour of v_{2}. Since v_{1} does not have more neighbours in X_{2} than u_{1}, and v_{1} is adjacent to v_{2} and u_{1} is not, it follows that there is a neighbour u_{2} ∈ X_{2} of u_{1} that is nonadjacent to v_{1}. Since X_{1}, X_{2} are cliques by the first axiom, it follows that u_{1}-u_{2}-v_{2}-v_{1}-u_{1} is a hole, C say. We may assume that in D, all edges between X_{1} and X_{2} have tail in X_{1}. By hypothesis, C has no centre, and so there does not exist σ_{3} ∈ Σ different from σ_{1}, σ_{2} with ϕ^{−1}(σ_{3}) nonempty such that σ_{1}, σ_{3}, σ_{2} are in clockwise order. Since σ_{2} is the only point σ ∈ Σ such that ϕ^{−1}(σ_{1}) is neither complete nor anticomplete to ϕ^{−1}(σ), it follows that every v ∈ V (G) \ (X_{1} ∪ X_{2}) is either complete or anticomplete to X_{1}, and similarly is either complete or anticomplete to X_{2}. But no such v is complete to both X_{1}, X_{2}, since C has no centre, and no v is anticomplete to both X_{1}, X_{2} since C is dominating. For i = 1, 2, let A_{i} be the set of all v ∈ V (G) \ (X_{1} ∪ X_{2}) that are complete to X_{i}; then A_{1}, A_{2}, X_{1}, X_{2} are pairwise disjoint and have union V (G), and A_{1} is complete to X_{1} and anticomplete to X_{2}, and A_{2} is complete to X_{2} and anticomplete to X_{1}. Since G contains no (1, 1, 1)-prism, it follows that A_{1} is anticomplete to A_{2}. Since G is claw-free, and A_{1} is complete to {u_{1}} and anticomplete to {u_{2}}, it follows that A_{1} is a clique, and similarly so is A_{2}. Hence for i = 1, 2, and for every vertex v ∈ A_{i}, all neighbours of v are pairwise adjacent, and therefore v belongs to no hole. We recall that C_{0} is a basis for (ϕ, D). It follows that V (C_{0}) ⊆ X_{1} ∪ X_{2}, which is impossible since ϕ(v) (v ∈ V (C_{0})) are all different. This proves that there is no such σ_{1}.

We have therefore proved that |ϕ^{−1}(σ_{1})| ≤ 1 for all σ_{1} ∈ Σ. Consequently G is a long circular interval graph. This proves 4.2.

5 Internal clique cutsets

Now we come to the second main result of the paper. We recall that the goal of this series of papers is to give a construction for all claw-free graphs. A clique cutset in a trigraph G is a strong clique C such that G \ C admits a 0-join, that is, V (G) \ C can be partitioned into two nonempty sets V_{1}, V_{2} such that V_{1} is strongly anticomplete to V_{2}. In this situation, G may be regarded as being constructed from the trigraphs G|(V_{i} ∪ C) (i = 1, 2) in the natural way, but this construction is not useful for our purposes, since it does not preserve the property of being claw-free (that is, G may not be claw-free even if both the graphs G|(V_{i} ∪ C) (i = 1, 2) are claw-free).

This difficulty can be partly obviated. Let us say the clique cutset C is internal if the sets V_{1}, V_{2} can be chosen with |V_{1}|, |V_{2}| > 1. The main result of this section asserts that if G is claw-free and admits an internal clique cutset, then either G admits a decomposition that is useful for us, or it belongs to a special class of trigraphs that we can characterize completely.

For a trigraph G and a vertex v ∈ V (G) we denote by N(x) the set of neighbours of x in G, and N^{∗}(v) denotes the set of strong neighbours of v. We need the following lemma.

5.1 Let G be a claw-free trigraph and let C be a minimal clique cutset in G. Let V_{1}, V_{2} be a partition of V (G) \ C such that V_{1}, V_{2} ≠ ∅ and V_{1} is anticomplete to V_{2}. Then

• for all u ∈ C, both N(u) ∩ V_{1} and N(u) ∩ V_{2} are strong cliques, and

• for all u, v ∈ C, either N(u) ∩ V_{1} ⊆ N^{∗}(v) ∩ V_{1} or N(u) ∩ V_{2} ⊆ N^{∗}(v) ∩ V_{2}.

Proof. Suppose that for some vertex u ∈ C there exist two antiadjacent vertices x, y in N(u) ∩ V_{1}. By the minimality of C, there exists a vertex z ∈ N(u) ∩ V_{2}. But now {u, x, y, z} is a claw in G, a contradiction. This proves the first assertion of the theorem.

For the second, assume that there exist v_{1} ∈ (N(u) \ N^{∗}(v)) ∩ V_{1} and v_{2} ∈ (N(u) \ N^{∗}(v)) ∩ V_{2}. Since C is a clique, u is adjacent to v. But then {u, v, v_{1}, v_{2}} is a claw, a contradiction. This proves the second assertion of the theorem and completes the proof of 5.1.

The following is the main result of this section.

5.2 Let G be a claw-free trigraph with an internal clique cutset, such that G does not admit twins, a 0-join, or a 1-join. Then every hole in G has length four; if there is a 4-hole then G admits a coherent proper W-join, and otherwise G is a linear interval trigraph.

Proof. Let G be a claw-free trigraph admitting a internal clique cutset, such that G does not admit twins, a 0-join, or a 1-join. In particular, G is not an antinet. If G has no hole, the theorem therefore follows from 4.1. Hence we may assume that there is a hole H in G. Choose H with length at least five if possible.

Let us say a clique-separation in G is a triple (C, V_{1}, V_{2}), such that

• C is a strong clique of G, and (V_{1}, V_{2}) is a partition of V (G) \ C,

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

• V (H) ∩ V_{2} = ∅.

(1) There is a clique-separation (C, V_{1}, V_{2}) in G with |V_{2}| ≥ 2 and with |V_{2}| maximum; and it can be chosen such that C ≠ ∅, and every vertex in C has a neighbour in V_{1} and a neighbour in V_{2}.

For since G admits an internal clique cutset, there is a triple (C, V_{1}, V_{2}) satisfying the first and second conditions in the definition of a clique-separation, with |V_{1}|, |V_{2}| ≥ 2; and since C is a strong clique, it follows that V (H) has empty intersection with one of V_{1}, V_{2}. Hence (possibly after exchanging V_{1}, V_{2}), it follows that G contains a clique-separation (C, V_{1}, V_{2}) with |V_{2}| ≥ 2. Choose a clique-separation (C, V_{1}, V_{2}) with |V_{2}| maximum (and therefore with |V_{2}| ≥ 2), and subject to that, with C minimal. Since G does not admit a 0-join, it follows that C ≠ ∅. Let c ∈ C. If c has no neighbour in V_{2}, then (C \ {c}, V_{1} ∪ {c}, V_{2}) is also a clique-separation with |V_{2}| maximum, contradicting the minimality of C; and if c has no neighbour in V_{1}, then c ∉ V (H) (since every vertex in V (H) ∩ C has a neighbour in V (H) \ C ⊆ V_{1}, because C is a strong clique), and therefore (C \ {c}, V_{1}, V_{2} ∪ {c}) is a clique-separation contradicting the maximality of |V_{2}|. This proves (1).

For a vertex c ∈ C and for i = 1, 2, let N_{i}(c) be the set of neighbours of c in V_{i}, and let N_{i}^{∗}(c) be the set of strong neighbours of c in V_{i}. Let J be the digraph with V (J) = C and edge set all pairs (u, v) with u, v ∈ C (possibly equal), such that N_{1}(v) ⊈ N_{1}^{∗}(u). Since C is nonempty, there is a strong component of J that is a “sink component”; that is, there exists X ⊆ C such that

• X is nonempty and J|X is strongly connected

• there is no edge (u, v) ∈ E(J) with u ∈ X and v ∉ X.

(2) For all distinct u, v ∈ X, N_{2}(u) = N_{2}^{∗}(u) = N_{2}(v) = N_{2}^{∗}(v).

For since X is strongly connected, there is a directed path of J from u to v, say u = v_{1}- ⋯ -v_{k} = v. For 1 ≤ i < k, since (v_{i}, v_{i+1}) ∈ E(J), it follows that N_{1}(v_{i+1}) ⊈ N_{1}^{∗}(v_{i}), and therefore N_{2}(v_{i+1}) ⊆ N_{2}^{∗}(v_{i}) by the second statement of 5.1. Consequently N_{2}(v) ⊆ N_{2}^{∗}(u). Similarly N_{2}(u) ⊆ N_{2}^{∗}(v). This proves (2).

Let Z = ⋂_{x∈X} N_{1}^{∗}(x).

(3) X ≠ C.

For suppose that X = C. Choose c ∈ C, and let Y = N_{2}(c). By 5.1, Y is a strong clique. There are two cases, depending whether N_{2}(c′) = N_{2}^{∗}(c′) = Y for all c′ ∈ C or not. Suppose first that N_{2}(c′) = N_{2}^{∗}(c′) = Y for all c′ ∈ C. Then C ∪ Y is a strong clique. If Y = V_{2} then since |V_{2}| > 1 it follows that G admits twins, a contradiction; and if Y ≠ V_{2} then (V_{1} ∪ C, V_{2}) is a 1-join, again a contradiction. Thus we may assume that there exists c′ ∈ C with one of N_{2}(c′), N_{2}^{∗}(c′) different from Y. By (2), |C| = 1, and so c′ = c and N_{2}(c) ≠ N_{2}^{∗}(c). Hence N_{1}(c) = N_{1}^{∗}(c) = Z (since c is semiadjacent to a member of V_{2} and F (G) is a matching); and by 5.1, Z is a strong clique, and therefore so is Z ∪ C. But Z ≠ V_{1}, because G|V_{1} contains a hole and therefore V_{1} is not a strong clique; and so (V_{1}, V_{2} ∪ C) is a 1-join, a contradiction. This proves (3).

(4) X ∪ Z is a strong clique, and N_{1}(c) ⊆ Z for every vertex c ∈ C \ X, and H is a 4-hole, and V (H) consists of two vertices of C \ X and two vertices of Z.

For the first statement of 5.1 implies that Z is a strong clique, and therefore X ∪ Z is a strong clique. Let c ∈ C \ X, and x ∈ X. Since (x, c) ∉ E(J), it follows that N_{1}(c) ⊆ N_{1}^{∗}(x). Since this holds for all x ∈ X, we deduce that N_{1}(c) ⊆ Z. From (3), (X ∪ Z, V_{1} \ Z, V_{2} ∪ (C \ X)) is not a clique-separation of G, and so V (H)∩(C \X) ≠ ∅. Let H have vertices h_{1}- ⋯ -h_{n}-h_{1} in order, where h_{1} ∈ C \ X. Then h_{2}, h_{n} ∈ C ∪ N_{1}(h_{1}) ⊆ C ∪ Z, and since C, Z are both strong cliques and h_{2}, h_{n} are antiadjacent, we may assume that h_{2} ∈ C and h_{n} ∈ Z. Since h_{2}, h_{n} are antiadjacent, and X ∪ Z is a strong clique, it follows that h_{2} ∉ X, and so h_{2} ∈ C \ X. Thus by the same argument h_{3} ∈ Z. Since h_{3}, h_{n} ∈ Z and Z is a strong clique, it follows that n = 4, and so H is a 4-hole. This proves (4).

Let us say a step is a 4-hole consisting of two vertices of C \ X and two vertices of Z. We have seen that H is a step. We say a pair (A, B) is a step-connected strip if A ⊆ Z and B ⊆ C \ X, and for every partition (P, Q) of A or of B with P, Q nonempty, there is a step S with V (S) ⊆ A ∪ B and with P ∩ V (S), Q ∩ V (S) ≠ ∅. Certainly the pair (V (H) ∩ Z, V (H) ∩ (C \ X)) is a step-connected strip; so we may choose a step-connected strip (A, B) with V (H) ⊆ A ∩ B and with A ∪ B maximal.

(5) Every vertex in V (G) \ (A ∪ B) is either strongly complete or strongly anticomplete to A, and either strongly complete or strongly anticomplete to B. Moreover, the set of vertices V (G) \ (A ∪ B) that are complete to A ∪ B is a strong clique.

For let v ∈ V (G) \ (A ∪ B), and let A_{1}, B_{1} be the set of members of A, B respectively that are adjacent to v. Let A_{2}, B_{2} be the set of members of A, B respectively that are antiadjacent to v. Suppose first that A_{1}, A_{2} are both nonempty. Then v ∉ V_{2}, since V_{2} is strongly anticomplete to A, and so v ∈ C ∪ V_{1}. Since |A| ≥ 2, there is a partition (P, Q) of A with P, Q nonempty and with P ⊆ A_{1} and Q ⊆ A_{2}. Hence, since (A, B) is step-connected, there is a step a_{1}-a_{2}-b_{2}-b_{1}-a_{1} with a_{1} ∈ A_{1}, a_{2} ∈ A_{2}, and b_{1}, b_{2} ∈ B. Since {a_{1}, b_{1}, a_{2}, v} is not a claw, v is strongly adjacent to b_{1}. Since X ∪ Z is a strong clique containing a_{2}, and v is antiadjacent to a_{2}, it follows that v ∉ X ∪ Z; and therefore v ∉ N_{1}(b_{1}) by (4). Consequently v ∈ C \X, and therefore v is adjacent to b_{2}. But then a_{1}-v-b_{2}-a_{2}-a_{1} is a step, and so (A, B ∪ {v}) is a step-connected strip, contrary to the maximality of A ∪ B. Hence not both A_{1}, A_{2} are nonempty. This proves the first assertion of (5).

Now assume that B_{1}, B_{2} are both nonempty, and choose a step a_{1}-a_{2}-b_{2}-b_{1}-a_{1} with a_{1}, a_{2} ∈ A, b_{1} ∈ B_{1} and b_{2} ∈ B_{2}. Since {b_{1}, a_{1}, b_{2}, v} is not a claw in G, it follows that v is strongly adjacent to a_{1}. Since not both A_{1}, A_{2} are nonempty, it follows that a_{2} ∈ A_{1}. Also, v is not strongly anticomplete to A, and so v ∉ V_{2}; v is antiadjacent to b_{2}, and so v ∉ C; and therefore v ∈ V_{1}. Consequently v ∈ N_{1}(b_{1}) ⊆ Z. Hence v-a_{2}-b_{2}-b_{1}-v is a step, and so (A ∪ {v}, B) is a step-connected strip, contrary to the maximality of A ∪ B. This proves the second assertion of (5).

Now suppose that a, b ∈ V (G) \ (A ∪ B) are both complete to A ∪ B, and are antiadjacent. In particular, a, b are not strongly anticomplete to A, and so a, b ∉ V_{2}; and they are both adjacent to a vertex of C \ X, and therefore both belong to C ∪ Z. Since C, Z are strong cliques, we may assume that a ∈ Z and b ∈ C. Since X ∪ Z is a strong clique, it follows that b ∈ C \ X. Choose a′ ∈ V (H) ∩ Z and b′ ∈ V (H) ∩ C, antiadjacent. Then a-a′-b-b′-a is a step, and so (A ∪ {a}, B ∪ {b}) is a step-connected strip, contrary to the maximality of A ∪ B. Thus there are no such a, b. This proves (5).

From (4), H has length four, and so no hole of G has length more than four; and from (5), G admits a coherent proper W-join. This proves 5.2.

References

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