Van Bang Le

H N De Ridder

Probe split graphs

Keywords: probe graphs, probe split, probe interval, graph class

An undirected graph G = (V, E) is a probe split graph if its vertex set can be partitioned into two sets, N (nonprobes) and P (probes) where N is independent and there exists

time recognition algorithm for probe split graphs. In this article we give O(V 2 + V E) time recognition algorithms and characterisations by forbidden induced subgraphs both for the case when the partition into probes and non-probes is given, and when it is not given.

In 1994, in the context of genome research, Zhang [START_REF] Zhang | Probe interval graphs and its application to physical mapping of DNA[END_REF] introduced probe interval graphs. A graph is a probe interval graph if its vertex set can be partitioned into two sets, probes P and non-probes N , such that N is independent and new edges can be added between non-probes in such a way that the resulting graph is an interval graph. This definition can of course readily be generalized to some graph class C: A graph is probe C if its vertex set can be partitioned into two sets, probes P and non-probes N , such that N is independent and new edges can be added between non-probes in such a way that the resulting graph is in C.

In this manner probe interval [START_REF] Zhang | Probe interval graphs and its application to physical mapping of DNA[END_REF][START_REF] Johnson | A polynomial time recognition algorithm for probe interval graphs[END_REF][START_REF] Mcmorris | On probe interval graphs[END_REF][START_REF] Mcconnell | Construction of probe interval models[END_REF], probe chordal [START_REF] Golumbic | Chordal probe graphs[END_REF][START_REF] Chang | On the recognition of probe graphs of some self-complementary classes of perfect graphs[END_REF], including the intersection of probe chordal with weakly chordal graphs [START_REF] Golumbic | Chordal probe graphs[END_REF], the intersection of trees with probe interval graphs [START_REF] Sheng | Cycle free probe interval graphs[END_REF], the intersection of 2-trees with probe interval graphs [START_REF] Przulj | 2-tree probe interval graphs have a large obstruction set[END_REF], and probe interval bigraphs [START_REF] Chang | Probe interval bigraphs[END_REF] have been defined and investigated. Moreover, already in 1989 -before Zhang's article -Hertz [START_REF] Hertz | Slim graphs[END_REF] defined what he called slim graphs, which are in fact probe Meyniel graphs, and proved that these are perfect. Hoang and Maffray [START_REF] Hoàng | On slim graphs, even pairs, and star-cutsets[END_REF] used Hertz' construction to define probe Gallai graphs. In the recent article [START_REF] Chang | On the recognition of probe graphs of some self-complementary classes of perfect graphs[END_REF] several probe classes are discussed, among them probe split graphs.

Given C, the new graph class of all probe C graphs clearly contains C as a subclass. And when C is a subclass of D, then so is probe C a subclass of probe D. The general questions for new graph classes, 1. the existence of an efficient recognition algorithm, and 2. a characterisation of the structure, possibly by forbidden induced subgraphs, exist in the case of probe C graphs in two variants: one where the partition into probes and non-probes is given and a more general one where it is not given, resulting in four problems.

For the class of probe interval graphs, the first recognition algorithm for the partitioned case was given in [START_REF] Johnson | A polynomial time recognition algorithm for probe interval graphs[END_REF], and one with O(V + E log V ) running time in [START_REF] Mcconnell | Construction of probe interval models[END_REF], while recently the unpartitioned case has been solved [START_REF] Chang | The PIGs full monty -A floor show of minimal separators[END_REF]. Probe chordal graphs (unpartitioned) can be recognized in O(V 2 E) time [START_REF] Chang | On the recognition of probe graphs of some self-complementary classes of perfect graphs[END_REF]. A characterisation by forbidden induced subgraphs is open for both classes. A characterisation by forbidden induced subgraphs is known for the intersection of trees with probe interval graphs [START_REF] Sheng | Cycle free probe interval graphs[END_REF], both partitioned and unpartitioned, but for 2-trees it already seems to be a difficult problem [START_REF] Przulj | 2-tree probe interval graphs have a large obstruction set[END_REF]. The forbidden induced subgraph characterisation for the intersection of trees with probe interval graphs leads to a polynomial recognition algorithm, both partitioned and unpartitioned. Probe interval bigraphs can be recognized in polynomial time [START_REF] Chang | Probe interval bigraphs[END_REF], a characterisation by forbidden subgraphs is unknown. Concerning probe split graphs, in [START_REF] Chang | On the recognition of probe graphs of some self-complementary classes of perfect graphs[END_REF] a polynomial recognition algorithm is sketched that can be implemented to run in time O(V 4 (V + E)), but the characterisation problem is not tackled.

From these results it is clear that neither recognizing nor characterising probe C graphs is a straightforward matter; in fact there is no positive characterisation result on any probe C class at all -the only positive result is on a subclass of probe interval graphs, the intersection of trees with probe interval graphs. In this article we will solve both the recognition and the characterisation problem for unpartitioned and partitioned probe split graphs.

All graphs considered are finite, undirected and simple. Given a graph H and a positive integer n, nH denotes the graph consisting of n disjoint copies of H. C n , P n and K n denote the chordless cycle, chordless path, and complete graph, respectively, on n vertices. A chordless cycle on at least five vertices is called hole. Its complement is a anti-hole. An odd hole is a hole of odd length.

For two disjoint sets of vertices X and Y , X ❖ 1 Y (X ❖ 0 Y ) means that every vertex in X is adjacent (nonadjacent) to every vertex in Y . Occasionally, when such use is clear from context, we may use ❖ 1 , ❖ 0 as graph-valued operators: For graphs X and Y , X ❖ 0 Y is the disjoint union of X and Y and X ❖ 1 Y results from X ❖ 0 Y by adding all possible edges with one endpoint in X and the other in Y . We often identify a subset of vertices with the subgraph induced by that subset, and vice versa. A set of vertices is called independent or stable if the vertices are pairwise non-adjacent and it is called a clique if they are pairwise adjacent. Adjacency of two vertices x, y in a graph G = (V, E) is written xy ∈ E or x ∼ y. The (open) neighbourhood N (v) of a vertex v is the set of its neighbours, the closed neighbourhood N [v] = N (v) ∪ {v} and the non-neighbourhood

N (v) = V \ N [v]. Given a set of vertices X ⊆ V , the subgraph induced by X is written G[X]. The complement of G is written G.
Recall that a graph is a split graph [START_REF] Foldes | Split graphs[END_REF][START_REF] Hammer | The splittance of a graph[END_REF] iff it can be partitioned into a clique and an independent set, and that the split graphs are precisely the (2K 2 , C 4 , C 5 )-free graphs.

Definition 1 A graph G = (V, E) is a probe split graph if its vertex set V can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and there exists

E ′ ⊆ N × N such that G ′ = (V, E ∪ E ′ ) is a split graph.
As mentioned before, all split graphs are probe split. Bipartite graphs G = (X ∪ Y, E) are probe split as well: Take N = X, P = Y and E ′ = N × N .

Theorem 2 G = (V, E) is a probe split graph iff its vertex set can be partitioned into three, possibly empty, sets C, S, I, such that C is a clique, S, I are independent sets and C ❖ 1 S.

Proof: (⇒) Let G = (V, E) be a probe split graph with probes P and non-probes

N (V = P ∪ N ). Let G ′ = (V, E ∪ E ′ ), where E ′ ⊆ N × N ,
′ = N × N , then obviously G ′ = (V, E ∪ E ′ ) is a split graph. Thus, G is probe split. ✷
From Th. 2 we see that probe split graphs are (1,2)-colourable and P 4 -brittle (every P 4 has an endpoint in I) and therefore P 4 -bipartite, perfectly orderable and perfect. (Definitions and references for all these classes can be found in ISGCI [START_REF]Information System on Graph Classes and their Inclusions (ISGCI)[END_REF].) Definition 3 A partition (C, S, I) of the vertex set of a graph G such that C is a clique, S and I are independent sets and C ❖ 1 S is called a valid probe split partition of G.

By Th. 2 a graph is probe split iff it has a valid probe split partition. This fact will be used often and without further reference.

Unpartitioned probe split graphs -An overview

As every induced subgraph of a probe split graph is again a probe split graph, probe split graphs can characterized by forbidden induced subgraphs. In this section we will outline the proof that a graph is a probe split graph iff it has no induced subgraph from Fig. 1 on page 210. This will also give rise to a polynomial recognition algorithm for unpartitioned probe split graphs. The long and technical proof follows in the next section.

Theorem 4 A graph is a probe split graph iff it has no induced subgraph isomorphic to a graph in Fig. 1.

Proof: (⇒) By Lem. 5. (⇐) The proof is given in this and the next section. ✷

Although the necessity of forbidding the graphs in Fig. 1 can easily be checked by brute force (i) , the discussion in the next lemma will provide the reader with more insight in the structure of probe split graphs.

Lemma 5

The graphs in Fig. 1 are not probe split.

Proof:

The key lies in the probe split partition from Th. 2. From this theorem we immediately get the following observations:

1. Every clique has at most one I-vertex, at most one S-vertex, the rest are C-vertices. In particular, every triangle contains at least one C-vertex.

2. Every C 4 consists either of alternating S and I vertices, or of two non-adjacent S-vertices, with the other two vertices being one C and one I-vertex.

3. Combining these two, every house has an I-vertex as the roof, with one neighbour a C-vertex. From this the other vertices follow.

4. Every path on at least six vertices consists of alternating S and I vertices. If a path has even length, then precisely one of the end-vertices is an S-vertex.

2k+1 1 A 1 (k ≥ 2) 1 2k
A 2 (k ≥ 3)

1 2k A 3 (k ≥ 3) A 4 (K 2 ∪ K 3 ) A 5 (longhorn) A 6 (eiffel- tower) A 7 A 8 (C 4 ∪ P 2 ) A 9 (co-fish) A 10 A 11 (antenna)
A 12 (codomino)

A 13 (C 6 ) A 14 A 15 A 16 A 17 A 18 A 19 A 20 A 21 A 22 (3K 2 ) A 23 A 24 (2P 3 ) A 25 A 26 (P 6 ) A 27 A 28 A 29 A 30
Fig. 1: Forbidden subgraphs for probe split graphs (continued on next page).

5. Every P 5 either consists of alternating S and I-vertices, or the middle vertex is a C-vertex, its neighbours Sand the outer vertices I-vertices.

6. If the non-neighbourhood of a vertex contains an edge, then that vertex cannot be a C-vertex.

Obs. 1 gives A 4 (K 2 ∪ K 3 ) as forbidden subgraph, and together with Obs. 4 A 5 (longhorn). If we take two triangles and unite one vertex of each triangle, we get a so-called butterfly. The vertex of degree four must be a C-vertex, while each wing consists of an S and an I-vertex. forbids odd anti-holes of lenght at least 7, so probe split graphs are (odd hole, odd anti-hole)-free. Obs. 5 gives A 6 (eiffeltower). Now consider the graph formed by A 29 with the vertex of degree one deleted. Since every vertex of degree two has two different non-neighbours in the K 4 , and the K 4 has at most one S and at most one I-vertex, it follows that the vertices of degree two must be I-vertices. This implies that the K 4 does not contain an I-vertex, and in particular that at least one of the lower two vertices of the K 4 must be a C-vertex. Hence every neighbour of the highest vertex of degree two must be adjacent to this C-vertex. This gives A 29 , A 30 , A 31 .

From Obs. 2 we have that a vertex v that is universal to a C 4 is a C-vertex. Vertices that are nonadjacent to v then must be I-vertices, and their neighbours in the C 4 are in S or C. This leads to A 20 , A 21 , A 32 to A 34 , A 36 to A 39 and A 41 to A 45 .

Finally to graphs A 46 to A 52 : A vertex that is not part of the P 3 ❖ 1 P 3 must be an I-vertex (Obs. 6 -it is easy to see that they cannot be S-vertices), and thus the P 3 s do not contain any I-vertices. But every P 3 contains at least one non-C-vertex, i.c. an S-vertex. These S-vertices are adjacent. ✷

The sufficiency of Th. 4 is proved inductively. Let G have no induced subgraphs isomorphic to a graph listed in Fig. 1. Set

B = {v ∈ V (G) | N (v) is not a stable set}, C = {v ∈ V (G) | N (v) does not induce a split graph}.
Proposition 6 Assuming G = (V, E) does not contain any graph listed in Fig. 1 as an induced subgraph, then a)

B ∩ C = ∅; b) C is a clique; c) G[B] is bipartite.
Proposition 7 Assuming G = (V, E) does not contain any graph listed in Fig. 1 as an induced subgraph, then for every nontrivial (i.e. with at least two vertices) connected component

B ′ = (X ∪ Y, E ′ ) of G[B], X ❖ 1 C or Y ❖ 1 C.
The basis of the induction is the case that V = B ∪ C. In this case, the Prop. 7 states how to define a valid probe split partition (C, S, B \ S) of G: For every non-trivial component Fig. 1: Forbidden subgraphs for probe split graphs (continuation of previous page).

B ′ = (X ∪ Y, E ′ ) of B, let S(B ′ ) ∈ {X, Y } with S(B ′ ) ❖ 1 C
The induction step occurs when V = B ∪ C. According to Prop. 8, we can remove a vertex v ∈ V \ (B ∪ C) and inductively build a probe split partition on a valid partition of Gv: Proposition 8 Assuming G = (V, E) does not contain any graph listed in Fig. 1 as an induced subgraph, then for every vertex v ∈ V \ (B ∪ C): If Gv is a probe split graph, then so is G. Moreover, a valid partition of G can be obtained from a valid partition of Gv in linear time.

Using Prop. 6, 7 and 8 we can give Alg. 1 to recognize probe split graphs.

(V 2 + V E). ✷ Algorithm 1 Give a valid partition of G = (V, E) iff G is a probe split graph. Compute the subsets B and C if B ∩ C = ∅ or G[B] is not bipartite or G[C] is not a clique or there is a non-trivial connected component B ′ = (X ∪ Y, E ′ ) of G[B] such that neither X ❖ 1 C nor Y ❖ 1 C then FAIL end if if V = B ∪ C then For each non-trivial connected component B ′ = (X ∪ Y, E ′ ) of G[B], let S(B ′ ) ∈ {X, Y } with S(B ′ ) ❖ 1 C (in case both X ❖ 1 C and Y ❖ 1 C, choose S(B ′ ) ∈ {X, Y } arbitrarily) S := B ′ S(B ′ ); I := B \ S SUCCESS: return (C, S, I) end if if V = B ∪ C then Choose an arbitrary vertex v ∈ V \ (B ∪ C) Recursively compute a valid partition (C ′ , S ′ , I ′ ) for G -v Compute a valid partition (C, S, I) for G from (C ′ , S ′ , I ′ ) SUCCESS: return (C, S, I) end if
2 Unpartitioned probe split graphs -The proof of Prop. 6, 7 and 8

In this section we prove Prop. 6, Prop. 7 and Prop. 8. We assume that G = (V, E) has no induced subgraph from Fig. 1 and that B, C ⊆ V are as defined in the previous section.

The proof of Proposition 6

Lemma 10 (Prop. 6.a) B ∩ C = ∅.

Proof: Assume to the contrary that there exists a vertex v ∈ B ∩ C. As v ∈ B, there exist adjacent vertices

x, y ∈ N (v). As v ∈ C and G is C 5 -free, there exist vertices v 1 , v 2 , v 4 , v 4 ∈ N (v) such that {v 1 , v 2 , v 3 , v 4 } induces a 2K 2 with edges v 1 v 2 and v 3 v 4 , or the C 4 = (v 1 , v 2 , v 3 , v 4 , v 1 ).
We consider the first case. In this case, each of x, y is adjacent to at most two of the vertices

v 1 , v 2 , v 3 , v 4 otherwise x or y together with v 1 , v 2 , v 3 , v 4 and v would induce a A 14 or A 8 (C 4 ∪ P 2 ). Moreover, x (respectively, y) cannot be adjacent to both v 1 , v 2 , or to both v 3 , v 4 . For, if x is adjacent to both v 1 , v 2 then x, y, v 3 , v 4 and v would induce a A 4 (K 2 ∪ K 3 ) (if y ∼ v 3 , v 4 ), or y, x, v 1 , v and v 3 or v 4 would induce a C 5 (if y ∼ v 3 or y ∼ v 4 ). So, let without loss of generality, x be nonadjacent to v 1 and v 3 . Now, if y is nonadjacent to all v i , i = 1, 2, 3, 4, then x, y, v, v 1 , v 2 , v 3 , v 4 induce a A 16 (if x ∼ v 2 , v 4 ), or {x, y, v, v 1 , v 2 } or {x, y, v, v 3 , v 4 } induce a A 4 (K 2 ∪ K 3 ) (otherwise).
If y is adjacent to exactly one of the v i , then we may assume without loss of generality that y is nonadjacent to v 1 , v 2 . Then x must be adjacent to

v 2 otherwise x, y, v, v 1 , v 2 would induce a A 4 (K 2 ∪K 3 ). Hence y and v 3 are nonadjacent otherwise x, y, v, v 2 , v 3 would induce a C 5 . It follows that y is adjacent to v 4 , and x, y, v, v 2 , v 4 induce a C 5 (if x ∼ v 4 ), or x, y, v, v 1 , v 2 , v 4 induce a A 12 (co-domino).
Finally, let y be adjacent to (exactly) two of the v i . If y is adjacent to v 1 and

v 3 then x, y, v 1 , v 2 , v 3 , v 4 and v induce a A 16 (if x ∼ v 2 , v 4 ), or x, y, v, v 1 , v 4 or x, y, v, v 2 , v 3 induce a C 5 (if x ∼ v 4 or x ∼ v 2 ). If y is adjacent to v 1 and v 4 then x, y, v, v 1 , v 2 , v 3 , v 4 induce a A 16 (if x ∼ v 2 , v 4 ), or x, y, v, v 2 , v 4 induce a C 5 (if x ∼ v 2 , x ∼ v 4 ), or x, y, v, v 1 , v 2 , v 3 , v 4 induce a A 12 (co-domino) (if x ∼ v 2 , x ∼ v 4 ) or x, y, v, v 1 , v 2 , v 4 induce a A 13 (C 6 ). The first case is settled.
We consider the case of the

C 4 = (v 1 , v 2 , v 3 , v 4 , v 1
). In this case, each of x, y is adjacent to at least two of the vertices v 1 , v 2 , v 3 , v 4 otherwise there would be a A 4 (K 2 ∪ K 3 ) or a C 5 , but to at most three of the v i otherwise there would be a A 22 (3K 2 ).

Let

x be adjacent to v 1 , v 2 , v 3 . If y is also adjacent to v 1 , v 2 , v 3 then x, y, v, v 1 , v 3 , v 4 induce a A 8 (C 4 ∪ P 2 ). If y is adjacent to v 1 , v 2 , v 4 or to v 2 , v 3 , v 4 then x, y, v, v 1 , v 3 , v 4 induce a A 26 (P 6 ). If y is adjacent to v 1 , v 3 , v 4 then x, y, v, v 2 , v 4 induce a C 5 . If y is adjacent to (exactly) v 1 , v 2 , or to v 2 , v 3 then x, y, v, v 1 , v 3 , v 4 induce a A 14 . If y is adjacent to (exactly) v 2 , v 4 then x, y, v, v 1 , v 2 , v 4 induce a A 26 (P 6 ). If y is adjacent to v 1 , v 4 (or to v 3 , v 4 ) then x, y, v, v 2 , v 4 induce a C 5 .
Thus, x, and by symmetry, y must be adjacent to exactly two of the v i .

We first consider the case that at least one of x, y is adjacent to (exactly) two non-neighbours in {v 1 , . . . , v 4 }. Without loss of generality, assume

x is adjacent to v 1 , v 3 . If y is adjacent to v 2 , v 4 then there is a A 21 and if y is adjacent to v 1 , v 3 then x, y, v, v 1 , v 3 , v 4 induce a A 8 (C 4 ∪ P 2 ). If y is adjacent to v 1 , v 2 or to v 2 , v 3 , then x, y, v, v 1 , v 3 , v 4 induce a A 14 and if y is adjacent to v 3 , v 4 or to v 4 , v 1 , then x, y, v, v 1 , v 2 , v 3 induce a A 14 .
Finally, consider the case that each of x, y is adjacent to two neighbours in {v 1 , . . . , v 4 }. Without loss of generality, let x be adjacent to

v 1 , v 2 . If y is adjacent to v 1 , v 4 or to v 2 , v 3 , then x, y, v 2 , v 3 , v 4 or x, y, v 1 , v 3 , v 4 , respectively, induce a C 5 , and if y is adjacent to v 3 , v 4 , then x, y, v 1 , v 2 , v 3 , v 4 induce a A 13 (C 6 ). ✷ Lemma 11 (Prop. 6.b) C is a clique.
Proof: Assume to the contrary that there exist two nonadjacent vertices c 1 = c 2 in C. By Prop. 6.a, N (c 1 ) and N (c 2 ) are independent. This implies that every vertex that is (not) adjacent to c 1 is also (not) adjacent to c 2 and vice versa. Thus, N (c 1 ) = N (c 2 ). Now, as

c 1 ∈ C and because G is C 5 -free, G[N (c 1 )] contains an induced 2K 2 or C 4 . But then G[N (c 1 ) ∪ {c 2 }] contains a A 8 (C 4 ∪ P 2 ) or a A 22 (3K 2 ). ✷ Lemma 12 (Prop. 6.c) G[B] is bipartite.
Proof: Assume to the contrary that B does not induce a bipartite graph. As G is odd hole-free, B contains a triangle v 1 v 2 v 3 . As v i ∈ B, there exist adjacent vertices x i , y i in N (v i ), i = 1, 2, 3. In the following claims, i, j, k are arbitrarily chosen with {i, j, k} = {1, 2, 3}.

CLAIM 1 N (v i ) ∩ {x j , y j , x k , y k } = ∅. PROOF: Assume to the contrary that N (v i ) ∩ {x j , y j , x k , y k } = ∅. As G has no induced A 4 (K 2 ∪ K 3 ), v j ∼ x k or v j ∼ y k , but not both otherwise v i , v k , x k , y k would induce a 2K 2 in N (v j
) and v j would belong to C, contradicting Prop. 6.a. Likewise, v k is adjacent to exactly one of x j , y j .

Let, without loss of generality,

v j ∼ x k and v k ∼ x j . Then x j ∈ {x k , y k } and x k ∈ {x j , y j }. Moreover, y j = y k otherwise v j , v k , x j , y j , x k would induce a C 5 (if x j ∼ x k ) or v i , v j , v k , x j , y j , x k would induce a A 12 (co-domino) (if x j ∼ x k ). Hence y j ∼ y k otherwise y j , y k , v i , v j , v k would induce a A 4 (K 2 ∪ K 3 )
, and y j ∼ x k , y k ∼ x j otherwise there would be a C 5 or a

A 12 (co-domino). Now, v i , v j , v k , x j , y j , x k , y k induce a A 15 (if x j ∼ x k ) or a A 5 (longhorn) (otherwise). ✷ CLAIM 2 x i , y i , v j , v k do not induce a C 4 .
PROOF: Assume to the contrary that

x i , y i , v j , v k do induce a C 4 , say v j ∼ x i , v k ∼ y i and v j ∼ y i , v k ∼ x i .
We first prove some observations.

N (v i ) \ N (v j ) ⊆ N (v k ) \ N (y i ). (1)
Proof of (1

): Let v ∈ N (v i ) \ N (v j ). First assume v ∼ v k .
Then v ∼ y i or v ∼ x i (otherwise there would be a A 11 (antenna)), but not both (otherwise there would be a

A 13 (C 6 )). Now, v i , x i , y i , v and v j (if v ∼ y i ) or v k (if v ∼ x i ) induce a C 5 . Thus, v ∼ v k . Next, assume v ∼ y i . Then v ∼ x i , too (otherwise there would be a C 5 ). Hence v i , v j , v k , x i , y i , v induce a A 26 (P 6 ). Thus, v ∼ y i , and (1) follows.
By symmetry, we have:

N (v i ) \ N (v k ) ⊆ N (v j ) \ N (x i ). (2)
We next show:

N (v i ) \ N (v j ) = ∅ ⇒ N (v k ) ⊆ N (v i ). (3)
Proof of (3

): Let v ∈ N (v i ) \ N (v j ). By (1), v ∼ v k , v ∼ y i . Consider a vertex u ∈ N (v k ), and assume u ∼ v i . Then, by (2), u ∼ v j , u ∼ x i . Moreover, v ∼ u otherwise v i would belong to C, contradicting Prop. 6.a. Now, if u ∼ y i and v ∼ x i then v i , v j , v k , x i , y i , u, v induce a A 17 . If u ∼ y i and v ∼ x i then v i , x i , y i , u, v induce a C 5 . If u ∼ y i and v ∼ x i (or u ∼ y i and v ∼ x i ) then v i , x i , y i , u, v and v j (respectively, v k ) induce a A 11 (antenna). Thus, u ∼ v i , and (3) follows.
By symmetry, we have:

N (v i ) \ N (v k ) = ∅ ⇒ N (v j ) ⊆ N (v i ). (4)
Now, by Claim 1 and symmetry, v i is adjacent to a vertex v ∈ {x j , y j }. By (1), v ∼ v k , v ∼ y i . In particular, v ∈ {x k , y k }. By (3), x k and y k are nonadjacent to v i , hence v j ∼ x k or v j ∼ y k otherwise there would be a A 4 (K 2 ∪ K 3 ), but not both otherwise v j would belong to C, contradicting Prop. 6.a.

Let, without loss of generality,

v j ∼ x k . Then v ∼ x k otherwise v i , v k , v, x k , y k would induce a A 4 (K 2 ∪ K 3 ) (if v ∼ y k ) or v i , v, v j , x k , y k would induce a C 5 (if v ∼ y k ). Now, v i , v j , v k , v, x k , y k induce a A 9 (co-fish) (if v ∼ y k ) or a A 14 (if v ∼ y k ). This final contradiction proves Claim 2. ✷ CLAIM 3 If x j , y j ∈ N (v i ) then N (v k )∩{x j , y j } = ∅, |N (v k )∩{x i , y i }| = 1, and N (v j )∩{x i , y i } = ∅. PROOF: Note first that x i , y i , x j , y j are pairwise distinct, since x j , y j ∈ N (v i ). From v i ∈ B and Prop. 6.a it follows that N (v k ) ∩ {x j , y j } = ∅. Let v k ∼ x j , say. Suppose that |N (v k ) ∩ {x i , y i }| = 1. If x i ∼ v k and y i ∼ v k then G[N (v k )] contains an induced C 5 , C 4 , or 2K 2 , hence v k ∈ C, contradicting Prop. 6.a. Thus, N (v k ) ∩ {x i , y i } = ∅. Then v j ∼ x i or v j ∼ y i (otherwise v i , v j , v k , x i , y i would induce a A 4 (K 2 ∪ K 3 )
), but not both (otherwise v j would belong to C, contradicting Prop. 6.a). Let v j ∼ x i , say. Also, x j ∼ x i or x j ∼ y i (otherwise

x j , v i , v k , x i , y i would induce a A 4 (K 2 ∪ K 3 )), but not both (otherwise v i , v j , v k , x i , y i , x j would induce a A 14 ). Now, if x j ∼ x i then v i , v j , v k , x i , y i , x j induce a A 9 (co-fish), and if x j ∼ y i then v i , v j , x i , y i , x j induce a C 5 . It follows that |N (v k ) ∩ {x i , y i }| = 1.
Let, without loss of generality, x i ∼ v k . Next we suppose that N (v j ) ∩ {x i , y i } = ∅. If x i ∼ v j then x i ∼ x j (otherwise v k would belong to C, contradicting Prop. 6.a), and

y i ∼ x j (otherwise v i , v j , v k , x i , y i , x j would induce a A 26 (P 6 ) (if y i ∼ v j ) or x i , y i , x j , v i , v j induce a C 5 (if y i ∼ v j ))
. Now, if y j ∼ x i and y j ∼ y i then v i , x i , y i , x j , y j induce a A 4 (K 2 ∪ K 3 ). If y j ∼ x i and y j ∼ y i then v i , v k , x i , y i , x j , y j induce a A 14 . If y j ∼ x i and y j ∼ y i then v i , v k , x i , y i , x j , y j induce a A 9 (co-fish), and finally, if y j ∼ x i and y j ∼ y i then x i , y i , x j , y j , v k induce a C 5 . Thus, x i ∼ v j . By Claim 2, therefore, y i ∼ v j , and it follows that

N (v j ) ∩ {x i , y i } = ∅. ✷ CLAIM 4 |N (v i ) ∩ {x j , y j }| ≤ 1 PROOF: Assume to the contrary that x j ∼ v i and y j ∼ v i . By Claim 3, N (v j ) ∩ {x i , y i } = ∅ and we may assume that v k ∼ x j , v k ∼ x i , and v k ∼ y i . By Claim 1, N (v j ) ∩ {x k , y k } = ∅. If x k , y k ∈ N (v j ) then, by Claim 3, N (v k ) ∩ {x j , y j } = ∅, a contradiction. Thus, |N (v j ) ∩ {x k , y k }| = 1, say v j ∼ x k and v j ∼ y k . Moreover, |N (v i ) ∩ {x k , y k }| ≤ 1, otherwise, by Claim 3 again, N (v k ) ∩ {x i , y i } = ∅, a contradiction. Suppose |N (v i ) ∩ {x k , y k }| = 1. Then by Claim 2, v i ∼ x k . In particular, x k ∈ {x i , y i }, and
x k ∼ x i or x k ∼ y i otherwise v i , v j , x k , x i , y i would induce a A 4 (K 2 ∪ K 3 ), but not both otherwise v i , v j , v k , x k , x i , y i would induce a A 14 . Now, x k , y i , x i , v k , v i induce a C 5 (if x k ∼ x i ) or v i , v j , v k , x k , x i , y i induce a A 9 (co-fish) (if x k ∼ x i ). Thus, N (v i ) ∩ {x k , y k } = ∅. Then x j ∈ {x k , y k },
and the same arguments above applied for v i , v j , v k , x j , x k , y k show again that there exists a A 4 (K 2 ∪ K 3 ), or a A 14 , or a C 5 , or a A 9 (cofish). Claim 4 is proved. ✷ Now, as G has no induced A 4 (K 2 ∪ K 3 ), and because of Claims 2 and 4, we have the following two cases with a suitable choice of i, j, k.

Case 1 N (v j ) ∩ {x i , y i } = N (v k ) ∩ {x i , y i } and N (v k ) ∩ {x j , y j } = N (v i ) ∩ {x j , y j }.
Then we may assume that

N (v j ) ∩ {x i , y i } = N (v k ) ∩ {x i , y i } = {x i } and N (v k ) ∩ {x j , y j } = N (v i ) ∩ {x j , y j } = {x j }. It follows that x i ∈ {x j , y j }, x j ∈ {x i , y i }.
As v k ∈ B and because of Prop. 6.a, x i ∼ x j . Moreover, x i ∼ y j (otherwise x i , y j , x j , v i , v j would induce a C 5 ), x j ∼ y i (otherwise x j , y i , x i , v j , v i would induce a C 5 ). In particular,

y i = y j . Now, if y i ∼ y j then y i , y j , x j , v k , x i induce a C 5 . If y i ∼ y j then v i , v j , v k , x i , y i , x j , y j induce a A 2 . Case 1 is settled. Case 2 N (v j ) ∩ {x i , y i } = ∅ and N (v k ) ∩ {x j , y j } = ∅. Then |N (v k ) ∩ {x i , y i }| = 1, say v k ∼ x i , and |N (v i ) ∩ {x j , y j }| = 1, say v i ∼ x j . It follows that x i ∈ {x j , y j }, x j ∈ {x i , y i }. Suppose x i ∼ y j . Then x i , y j , x j , v i , v k induce a C 5 (if x i ∼ x j ) or x i , x j , y j , v i , v j , v k induce a A 12 (co-domino) (if x i ∼ x j )
. Thus, x i ∼ y j . Likewise, x j ∼ y i . In particular, y i = y j , and

y i ∼ y j otherwise y i , y j , v i , v j , v k would induce a A 4 (K 2 ∪ K 3 ). Now, v i , v j , v k , x i , y i , x j , y j induce a A 5 (longhorn) (if x i ∼ x j )
or a A 15 (otherwise). Case 2 is settled, completing the proof of Prop. 6.c.

✷

The proof of Proposition 7

Before we prove Prop. 7, we need some auxiliary results. The next three lemmas deal with the situation when for every c ∈ C: c ❖ 1 X or c ❖ 1 Y .

(

) 5
Let Proof: For contradiction, assume there are adjacent vertices x ∈ X \ {u}, y ∈ Y \ {v} such that c 1 ∼ y and c 2 ∼ x. Then x ∼ v or y ∼ u, but not both (otherwise c 1 , c 2 , u, v, x, y would induce a A 23 or a A 24 (2P 3 )). By symmetry, we may assume

c 1 = c 2 ∈ C such that c 1 ❖ 1 X, c 2 ❖ 1 Y, c 1 ❖ 1 Y, c 2 ❖ 1 X. Lemma 13 Assume C ❖ 1 X and C ❖ 1 Y . Let u ∈ X and v ∈ Y such that c 2 ∼ u and c 1 ∼ v.
x ∼ v and y ∼ u, CLAIM 1 x ❖ 1 C PROOF: Assume x ∼ c for some c ∈ C \ {c 1 , c 2 }. By (5), c ❖ 1 Y . Then u, v, c, c 1 , y, x induce a A 26 (P 6 ) (if c ∼ u), or u, v, c, c 1 , c 2 , x, y induce a A 18 (if c ∼ u). ✷
As x ∈ B, there exist adjacent vertices x ′ , y ′ ∈ N (x). As x ❖ 1 C, we may assume that x ′ ∈ X \ {x}, y ′ ∈ Y \ {v, y}. Suppose y ′ ∼ u. Then x, y, c 1 , c 2 , u, y ′ induce a A 23 (if y ′ ∼ c 1 ), or u, v, c 1 , c 2 , x, y ′ induce a A 14 (if y ′ ∼ c 1 ). Thus, y ′ ∼ u.

In particular,

x ′ = u. Suppose x ′ ∼ y. Then x ′ ∼ c 2 , otherwise x, x ′ , y, c 1 , c 2 , v would induce a A 24 (2P 3 ) (if x ′ ∼ v), or x, x ′ , y, c 1 , c 2 , u, v would induce a A 25 (if x ′ ∼ v). Now, x ′ , y, c 1 , c 2 , u, v induce a A 23 (if x ′ ∼ v), or x, x ′ , y, c 1 , c 2 , u, v induce a A 18 (if x ′ ∼ v). Thus, x ′ ∼ y. Therefore, x ′ ∼ c 2 or y ′ ∼ c 1 (otherwise x, y, c 1 , c 2 , x ′ , y ′ would induce a A 23 ). Now, if x ′ ∼ c 2 and y ′ ∼ c 1 then x ′ , y ′ , c 1 , c 2 , u, v induce a A 23 (if x ′ ∼ v), or x, y, x ′ , y ′ , c 1 , c 2 , u, v induce a A 44 (if x ′ ∼ v). If x ′ ∼ c 2 and y ′ ∼ c 1 then x, x ′ , y, y ′ , c 1 , c 2 , u, v induce a A 40 (if x ′ ∼ v), or a A 45 (if x ′ ∼ v). If x ′ ∼ c 2 and y ′ ∼ c 1 then x, x ′ , y ′ , c 1 , c 2 , v induce a A 26 (P 6 ) (if x ′ ∼ v), or x, x ′ , y ′ , c 1 , c 2 , u, v induce a A 27 (if x ′ ∼ v). ✷ Lemma 14 Assume C ❖ 1 X and C ❖ 1 Y . Let v 1 v 2 v 3 v 4 , be an induced path in B connecting v 1 ∈ X and v 4 ∈ Y . If c 1 ∼ v 4 and c 2 ∼ v 1 then c 1 ∼ v 2 or c 2 ∼ v 3 .
Proof: For a contradiction, assume that c 1 ∼ v 2 and c 2 ∼ v 3 . We will show that v 2 ❖ 1 C and v 3 ❖ 1 C.

As a first step we prove:

CLAIM 1 v 2 ❖ 1 C or v 3 ❖ 1 C PROOF: Suppose v 2 ∼ c ′ 1 and v 3 ∼ c ′ 2 for some c ′ 1 , c ′ 2 ∈ C \ {c 1 , c 2 }. By (5), c ′ 1 ❖ 1 X and c ′ 2 ❖ 1 Y . In particular, c ′ 1 = c ′ 2 . Moreover, c ′ 1 ∼ v 4 or c ′ 2 ∼ v 1 (otherwise c 1 , c 2 , c ′ 1 , c ′ 2 , v 1 , v 2 , v 3 , v 4 would induce a A 46 ), but not both (otherwise c ′ 1 , c ′ 2 , v 1 , v 2 , v 3 , v 4 would induce a A 26 (P 6 )). Now v 1 , v 2 , v 3 , v 4 , c ′ 1 , c ′ 2 , and c 1 (if c ′ 1 ∼ v 4 ) or c 2 (if c ′ 2 ∼ v 1 ) would induce a A 18 . ✷
Let, without loss of generality,

v 2 ❖ 1 C. As v 2 ∈ B, there exist adjacent vertices x, y ∈ N (v 2 ). As v 2 ❖ 1 C, we may assume that x ∈ X \ {v 1 , v 3 }, y ∈ Y \ {v 2 }. Moreover, x ∼ v 4 , (6)
otherwise v 1 , v 2 , v 3 , v 4 , c 1 , c 2 and x would induce a A 25 (if c 2 ∼ x) or a A 28 (if c 2 ∼ x). In particular, y = v 4 . Suppose y ∼ v 3 . Then y ∼ v 1 otherwise v 1 , v 2 , v 3 , v 4 , c 1 , c 2 and y would induce a A 25 (if c 1 ∼ y) or a A 28 (if c 1 ∼ y). Moreover, c 1 ∼ y or c 2 ∼ x otherwise c 1 , c 2 , x, y, v 2 , v 3 would induce a A 23 . But now c 1 , c 2 , x, y, v 1 , v 2 , v 3 , v 4 induce a A 31 (if c 1 ∼ y and c 2 ∼ x) or a A 30 (if c 1 ∼ y or c 2 ∼ x). Thus, y ∼ v 3 . (7)
Hence also

y ∼ c 1 , (8)
otherwise

v 1 , v 2 , v 3 , c 1 , c 2 , y would induce a A 24 (2P 3 ) (if y ∼ v 1 ), or v 1 , v 2 , v 3 , c 1 , c 2 , x, y would induce a A 25 (if y ∼ v 1 , x ∼ c 2 ) or a A 28 (if y ∼ v 1 , x ∼ c 2 ).
We next show:

CLAIM 2 v 3 ❖ 1 C PROOF: Suppose v 3 ∼ c ′ 2 for some c ′ 2 ∈ C \ {c 1 , c 2 }. By (5), c ′ 2 ❖ 1 Y . By Lem. 13, c ′ 2 ∼ v 1 (c 2 := c ′ 2 , u := v 3 , v := v 4 , x := v 1 , y := v 2 ) and c ′ 2 ∼ x (c 2 := c ′ 2 , u := v 3 , v := v 4 , x := x, y := y). Moreover, y ∼ v 1 otherwise v 1 , v 2 , v 3 , v 4 , c 1 , c 2 , c ′ 2 and y would induce a A 46 . Now v 1 , v 2 , v 3 , v 4 , c 1 , c 2 , c ′ 2 , x and y induce a A 47 (if c 2 ∼ x) or a A 48 (if c 2 ∼ x). Claim 2follows. ✷
As v 3 ∈ B, there exist adjacent vertices x ′ , y ′ ∈ N (v 3 ). As v 3 ❖ 1 C, we may assume that y ′ ∈ Y \ {y, v 2 , v 4 } and x ′ ∈ X \ {v 3 }. Now, by symmetry, we obtain from ( 6), [START_REF] Hertz | Slim graphs[END_REF], and (8):

y ′ ∼ v 1 , x ′ ∼ v 2 , and x ′ ∼ c 2 .
In particular,

x ′ ∈ X \ {x, v 1 , v 3 }. Moreover, x ∼ y ′ , otherwise c 1 , c 2 , v 2 , v 3 , x, y ′ would induce a A 23 (if x ∼ c 2 and y ′ ∼ c 1 ), or c 1 , c 2 , v 1 , v 2 , v 3 , v 4 , x, y ′ would induce a A 31 (if x ∼ c 2 and y ′ ∼ c 1 ), or a A 30 (otherwise). Suppose y ∼ x ′ . Then y ∼ v 1 (otherwise v 1 , v 2 , v 3 , v 4 , c 1 , c 2 , y, x ′ would induce a A 46 (if x ′ ∼ v 4 ), or v 1 , v 2 , v 3 , v 4 , c 1 , c 2 , y, x ′ , y ′ would induce a A 47 (if x ′ ∼ v 4 , y ′ ∼ c 1 ) or a A 48 (if x ′ ∼ v 4 , y ′ ∼ c 1 )), and, by symmetry, x ′ ∼ v 4 . Now v 1 , v 2 , v 3 , v 4 , c 1 , c 2 , x, y, x ′ , y ′ induce a A 49 or a A 50 (if x ∼ c 2 or y ′ ∼ c 1 ) or a A 51 (if x ∼ c 2 and y ′ ∼ c 1 ). Thus, y ∼ x ′ . Furthermore, y ∼ v 1 , otherwise v 1 , v 3 , v 4 , c 1 , c 2 , y, x ′ would induce a A 28 (if x ′ ∼ v 4 ), or v 1 , v 3 , v 4 , c 1 , c 2 , y, x ′ , y ′ would induce a A 30 (if x ′ ∼ v 4 , y ′ ∼ c 1 ) or a A 31 (if x ′ ∼ v 4 , y ′ ∼ c 1 )
. By symmetry,

x ′ ∼ v 4 . Suppose x ∼ c 2 . Then v 3 , v 4 , c 1 , c 2 , x, y, x ′ , y ′ induce a A 30 (if y ′ ∼ c 1 ) or a A 31 (if y ′ ∼ c 1 ). Thus, x ∼ c 2 ,
and by symmetry,

y ′ ∼ c 1 . Now v 1 , v 2 , v 3 , v 4 , c 1 , c 2 , x, y, x ′ , y ′ induce a A 52 . ✷ Lemma 15 Let v 1 v 2 • • • v 2k-1 v 2k , k ≥ 2, be an induced path in B connecting v 1 ∈ X and v 2k ∈ Y . If c 1 ∼ v 2k and c 2 ∼ v 1 then c 1 ❖ 0 {v 2i | i = 1, . . . , k} or c 2 ❖ 0 {v 2j-1 | j = 1, . . . , k}.
Proof: The proof is by induction on k. In case k = 2, Lem. 15 follows from Lem. 14.

Let k > 2. First, suppose c 1 ∼ v 2k-2 . Then, by induction (applied to v 1 v 2 • • • v 2k-2 ), c 1 ❖ 0 {v 2i | i = 1, . . . , k -1}, (9)
or

c 2 ❖ 0 {v 2j-1 | j = 1, . . . , k -1}. ( 10
)
As c 1 ∼ v 2k , we are done in case [START_REF]Information System on Graph Classes and their Inclusions (ISGCI)[END_REF]. Also, if c 2 ∼ v 2k-1 then we are done in case [START_REF] Johnson | A polynomial time recognition algorithm for probe interval graphs[END_REF]. So, let us assume that (9) does not hold, hence [START_REF] Johnson | A polynomial time recognition algorithm for probe interval graphs[END_REF] does hold, and

c 2 ∼ v 2k-1 . Let c 1 ∼ v 2i for some i ∈ {1, . . . , k -2}. Now, if i = k -2 then v 2k-4 , v 2k-3 , v 2k-2 , v 2k-1 , c 1 , c 2 induce a A 26 (P 6 ). If i < k -2, v 2i-1 , v 2i , v 2k-3 , v 2k-2 , v 2k-1 , c 1 , c 2 induce a A 27 . Thus, the case c 1 ∼ v 2k-2 is settled. Now suppose c 1 ∼ v 2k-2
, and by symmetry,

c 2 ∼ v 3 . Then c 1 ∼ v 2 because otherwise v 1 , v 2 , v 2k-2 , v 2k-1 , c 1 , c 2 would induce a A 23 (if c 2 ∼ v 2k-1 ), or v 1 , v 2 , v 3 , v 2k-2 , v 2k-1 , c 1 , c 2 would induce a A 27 (if c 2 ∼ v 2k-1 ). Now, if c 1 ∼ v 4 then v 1 , v 2 , v 3 , v 4 , v 5 , c 1 , c 2 induce a A 25 (if c 2 ∼ v 5 ) or a A 28 (if c 2 ∼ v 5 ). If c 1 ∼ v 2i for some 3 ≤ i ≤ k -1, then by induction (applied to v 1 v 2 • • • v 2i ), c 1 ∼ v 2 or c 2 ∼ v 3 , a contradiction. Hence, c 1 ❖ 1 {v 2i | i = 1, . . . , k -1}.
By symmetry we have

c 2 ❖ 1 {v 2j-1 | j = 2, . . . , k}.
But then c 1 , c 2 and v 1 , . . . , v 2k , induce a A 3 . ✷ Lemma 16 (Prop. 7) For every non-trivial connected component

B ′ = (X ∪ Y, E ′ ) of G[B], X ❖ 1 C or Y ❖ 1 C. Proof: CLAIM 1 For every induced path v 1 v 2 • • • v 2k-1 v 2k , k ≥ 3, in B and for every vertex v ∈ C: v ∼ v 1 or v ∼ v 2k PROOF:
The proof is by induction on k. First, let k = 3. If v ∼ v 1 and v ∼ v 6 then, as v ∈ C and because of Prop. 6.a, v ∼ v 2 , v ∼ v 5 . Discussing the adjacencies between v and v 3 , v 4 we conclude that there is an induced C 5 , or a A 11 (antenna), or a A 2 . Thus, v ∼ v 1 or v ∼ v 6 , and Claim 1 is proved for k = 3.

Next, let k ≥ 4, and assume that v

∼ v 1 and v ∼ v 2k . By Prop. 6.a, v ∼ v 2 , v ∼ v 2k-1 . Let i, 3 ≤ i ≤ 2k -2,
(if i ≥ 6) or v, v 1 , v 2 , v 3 , v 4 , v 5 would induce a A 11 (antenna) (if i = 4).
Now, if i ≤ 2k -5 then, by applying the induction hypothesis for the path

v i , v i+1 • • • v 2k , v ∼ v i or v ∼ v 2k , a contradiction. Thus, i ≥ 2k -3, hence i = 2k -3. Then v, v 2k-4 , v 2k-3 , v 2k-2 , v 2k-1 , v 2k induce a A 11 (antenna). ✷ Let B ′ = (X ∪ Y, E(B ′
)) be a nontrivial connected component of B, and assume to the contrary that X ❖ 1 C and Y ❖ 1 C. We distinguish two cases. As c ∈ C and by Prop. 6.a, c ∼ v 2 , c ∼ v 3 . We will show that v 2 ❖ 1 C and v 3 ❖ 1 C. As a first step, we prove

v 2 ❖ 1 C or v 3 ❖ 1 C:CLAIM 2 v 2 ❖ 1 C or v 3 ❖ 1 C. PROOF: Suppose v 2 ∼ c ′ and v 3 ∼ c ′′ for some c ′ , c ′′ ∈ C \ {c}. Then c ′ is adjacent to v 1 , v 3 and c ′′ is adjacent to v 2 , v 4 because of Prop. 6.a. In particular, c ′ = c ′′ . Moreover, c ′ ∼ v 4 or c ′′ ∼ v 1 (otherwise c, c ′ , c ′′ , v 1 , v 2 , v 3 , v 4 would induce a A 20 ), but not both (otherwise v 1 , v 2 , v 3 , v 4 , c ′ , c ′′ would induce a A 26 (P 6 )). Now, c, c ′ , c ′′ , v 1 , v 2 , v 3 , v 4 induce a A 10 , regardless whether c ′ ∼ v 4 or c ′′ ∼ v 1 ,

and Claim 2 follows. ✷

By symmetry, we may assume that

v 2 ❖ 1 C. As v 2 ∈ B, there exist adjacent vertices x, y ∈ N (v 2 ). As v 2 ❖ 1 C, we may assume that x ∈ X \ {v 1 , v 3 }, y ∈ Y \ {v 2 }. Suppose that x ∼ v 4 . Then c ∼ x (as c ∈ C), and c, v 1 , v 2 , v 3 , v 4 , x induce a A 11 (antenna). Thus, x ∼ v 4 . (11)
In particular, y = v 4 . Moreover,

y ∼ c, (12)
otherwise c ∼ x (by Prop. 6.a) and therefore y ∼ v 1 (else y, v 1 , v 2 , c, x would induce a C 5 ), imply-

ing that either v 1 , v 2 , v 3 , c, x, y induce a A 11 (antenna) (if y ∼ v 3 ), or v 1 , v 2 , v 3 , v 4 , c, x, y induce a A 6 (eiffeltower). Furthermore, y ∼ v 3 , (13)
otherwise

v 1 , v 2 , v 3 , v 4 , c, y would induce a A 11 (antenna) (if y ∼ v 1 ), or v 1 , v 2 , v 3 , v 4 , c, x, y would induce a A 6 (eiffeltower) (if y ∼ v 1 and x ∼ c), or a A 7 (if y ∼ v 1 and x ∼ c).
We next show:

CLAIM 3 v 3 ❖ 1 C PROOF: Suppose v 3 ∼ c ′ for some c ′ ∈ C \ {c}. Then by Prop. 6.a, c ′ ∼ v 4 and c ′ ∼ y. Moreover, y ∼ v 1 otherwise v 1 , v 2 , v 3 , v 4 , c, c ′ , y would induce a A 20 (if c ′ ∼ v 1 ) or a A 10 (if c ′ ∼ v 1 ). Now, v 1 , v 2 , v 3 , v 4 , c, c ′ ,
x and y induce a forbidden subgraph H as follows:

• c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 36 • c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 38 . • c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 38 • c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 39 . • c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 37 • c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 42 . • c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 41 • c ′ ∼ v 1 , c ′ ∼ x, c ∼ x: H is a A 43 . Claim 3 follows. ✷ As v 3 ∈ B, there exist adjacent vertices x ′ , y ′ ∈ N (v 3 ). As v 3 ❖ 1 C, we may assume that x ′ ∈ X \{v 3 }, y ′ ∈ Y \ {v 2 , v 4 }.
By symmetry, we obtain from ( 11), (

:

y ′ ∼ v 1 , x ′ ∼ c, and x ′ ∼ v 2 .
In particular, x ′ = v 1 , and x, y, x ′ , y ′ are pairwise distinct. Suppose x ∼ y ′ . Then c is adjacent to precisely one of x, y ′ : otherwise either v 1 , v 2 , v 3 , v 4 , c, x, y ′ would induce a A 7 (if c ∼ x, y ′ ), or v 2 , v 3 , c, x, y ′ would induce a A 4 (K 2 ∪ K 3 ) (if c ∼ x, y ′ ). By symmetry we may assume that c ∼ x and c ∼ y ′ . Then v 3 , v 4 , c, x, y, y ′ induce a A 11 (antenna). Thus,

x ∼ y ′ . Suppose y ∼ x ′ . Then x ′ ∼ v 4 or y ∼ v 1 (otherwise v 1 , v 2 , v 3 , v 4 , c, x, y, x ′ , y ′ would induce a A 32 , or a A 33 , or a A 34 ), but not both (otherwise v 1 , v 2 , v 3 , v 4 , c, y, x ′ would induce a A 20 ). By symmetry we may assume that x ′ ∼ v 4 and y ∼ v 1 . Then v 1 , v 2 , v 3 , v 4 , c, y, x ′ , y ′ induce a A 36 (if c ∼ y ′ ), or a A 37 (if c ∼ y ′ ). Thus, y ∼ x ′ . Then c ∼ x or c ∼ y ′ (otherwise v 3 , v 4 , c, x, y, x ′ would induce a A 11 (antenna) (if x ′ ∼ v 4 ), or v 3 , v 4 , c, x, y, x ′ , y ′ would induce a A 6 (eiffeltower) (if x ′ ∼ v 4 )), but not both (otherwise v 1 , v 2 , v 3 , v 4 , c, x, y, x ′ , y ′ would induce a A 35 (if y ∼ v 1 , x ′ ∼ v 4 ), or v 1 , v 2 , v 4 , c, y, x ′ would induce a A 11 (antenna) (if y ∼ v 1 , x ′ ∼ v 4 ), or v 1 , v 3 , v 4 , c, y, x ′ , y ′ would induce a A 7 (if y ∼ v 1 , x ′ ∼ v 4 ); the case y ∼ v 1 ,
x ′ ∼ v 4 is symmetrical to the last one). By symmetry we may assume that c ∼ x and c ∼ y ′ . But then

v 1 , v 2 , c, y, x ′ , y ′ induce a A 11 (antenna) (if y ∼ v 1 ), or v 1 , v 2 , c, x, y, x ′ , y ′ induce a A 7 (if y ∼ v 1 ). Case 1 is settled. Case 2: For every vertex c ∈ C, c ❖ 1 X or c ❖ 1 Y . In this case, since it is assumed that C ❖ 1 X and C ❖ 1 Y , there exist vertices c 1 = c 2 ∈ C such that c 1 ❖ 1 X, c 1 ❖ 1 Y and c 2 ❖ 1 X, c 2 ❖ 1 Y.
Observe that the prerequisites for Lem. 13, 14, 15 hold. We distinguish two subcases.

Case 2.1: For all a ∈ X, b ∈ Y , if c 2 ∼ a and c 1 ∼ b then a ∼ b. Since c 1 , c 2 ∈ C, there exist a neighbour x ∈ X of c 2 and a neighbour y ∈ Y of c 1 . By Lem. 13, x ∼ y. Consider an induced path (x = v 1 , v 2 , • • • , v 2k-1 , v 2k = y) in B connecting x and y, k ≥ 2. By Lem. 13 again, c 1 ∼ v 2 and c 2 ∼ v 2k-1 . As we are in Case 2.1, v 2 ∼ v 2k-1 , hence k = 2. Now v 1 , v 2 , v 3 , v 4 , c 1 , c 2 induce a A 26 (P 6 ).
Case 2.1 is settled.

Case 2.2:

There exist a ∈ X, b ∈ Y such that c 2 ∼ a, c 1 ∼ b, and a ∼ b. Let a ∈ X and b ∈ Y be two such vertices, and consider an induced path

(a = v 1 , v 2 , • • • , v 2k-1 , v 2k = b) in B connecting a and b. As a ∼ b, k ≥ 2.
By Lem. 15, we may assume without loss of generality,

c 1 ❖ 0 {v 2i | 1 ≤ i ≤ k}. As c 1 ∈ C, c 1 has a neighbour y ∈ Y \ {v 2 , v 4 , . . . , v 2k }.
Case 2.2.1:

c 2 ❖ 0 {v 2j-1 | 1 ≤ j ≤ k}. As c 2 ∈ C, c 2 has a neighbour x ∈ X \ {v 1 , v 3 , . . . , v 2k-1 }. By Lem. 13, x ∼ y. CLAIM 4 x ❖ 0 {v 2i | 1 ≤ i ≤ k} or y ❖ 0 {v 2j-1 | 1 ≤ j ≤ k} PROOF: Suppose x ∼ v 2i for some 1 ≤ i ≤ k. Then y ∼ v 2i-1 , and if i < k, y ∼ v 2i+1 , otherwise c 1 , c 2 ,
x, y, v 2i , and v 2i-1 (and if i < k, v 2i+1 ) would induce a A 26 (P 6 ), hence if v ∈ {v 2j-1 | 1 ≤ j ≤ k} were a neighbour of y, then c 1 , c 2 , x, y, v, v 2i , v 2i-1 would induce a A 27 . Thus,

y ❖ 0 {v 2j-1 | 1 ≤ j ≤ k}. By symmetry, if y ❖ 0 {v 2j-1 | 1 ≤ j ≤ k}, then x ❖ 0 {v 2i | 1 ≤ i ≤ k}.
✷ By symmetry we may assume that

x ❖ 0 {v 2i | 1 ≤ i ≤ k}.
As B is connected, x therefore has a neighbour y ′ ∈ Y \ {y, v 2 , v 4 , . . . , v 2k }. By Lem. 13 (applied to

u = v 1 , v = v 2 , x and y ′ ), c 1 ∼ y ′ .
Moreover,

y ❖ 0 {v 2j-1 | 1 ≤ j ≤ k} :
For, if y ∼ v 2j-1 for some 1 ≤ j ≤ k, then y ′ ∼ v 2j-1 otherwise c 1 , c 2 , x, y, v 2j-1 , y ′ would induce a A 26 (P 6 ). Now c 1 , c 2 , x, y, v 2j-1 , y ′ and v 2j induce a A 27 .

As B is connected, y must have a neighbour x ′ ∈ X \ {x, v 1 , v 3 , . . . , v 2k-1 }. By Lem. 13 again,

c 2 ∼ x ′ .

Hence

x ′ ∼ y ′ , otherwise c 1 , c 2 , x, y, x ′ , y ′ would induce a A 26 (P 6 ). Now c 1 , c 2 , x, y, x ′ , y ′ , and v 1 (if

y ′ ∼ v 1 ) or v 2 (if x ′ ∼ v 2 ) induce a A 27 , or c 1 , c 2 , x, y, x ′ , y ′ , v 1 , v 2 induce a A 19 (if y ′ ∼ v 1 and x ′ ∼ v 2 ). Case 2.2.1 is settled. Case 2.2.2: c 2 ∼ v 2j-1 for some 1 ≤ j ≤ k. Fix such an index j. Since c 2 ∼ v 1 , j > 1. By Lem. 13 (applied to u = v 1 , v = v 2 , x = v 2j-1 and y), y ∼ v 2j-1 .
Suppose y ∼ v 2j ′ -1 for some 1 ≤ j ′ ≤ k, j ′ = j. Then, by Lem. 13 again,

c 2 ∼ v 2j ′ -1 . If j ′ = j -1 then c 1 , c 2 , y, v 2j-1 , v 2j-2 , v 2j-3 induce a A 26 (P 6 ). If j ′ = j + 1 (implying j < k) then c 1 , c 2 , y, v 2j-1 , v 2j , v 2j+1 induce a A 26 (P 6 ). If j ′ = j ±1, c 1 , c 2 , y, v 2j-1 , v 2j , v 2j ′ -1 , v 2j ′ induce a A 27 . Thus, y ❖ 0 {v 1 , v 3 , . . . , v 2k-1 }.
As B is connected, y has a neighbour x ∈ X \ {v 1 , v 3 , . . . , v 2k-1 }. By Lem. 13 again, c 2 ∼ x. Now, if x ∼ v 2j-2 then c 1 , c 2 , x, y, v 2j-2 , v 2j-3 induce a A 26 (P 6 ), and if x ∼ v 2j-2 then c 1 , c 2 , x, y, v 2j-1 , v 2j-2 , v 2j-3 induce a A 27 .

Case 2.2.2, hence Case 2, is settled, and the proof of Prop. 7 is complete. ✷

The proof of Proposition 8

Let v ∈ V \ (B ∪ C), that is, N (v) induces a split graph and N (v) is independent. Assume that Gv is probe split and let (C, S, I) be a probe split partition of Gv. Create subpartitions of S and I as:

S 1 = S ∩ N (v), S 2 = S \ S 1 , I 1 = I ∩ N (v), I 2 = I \ I 1 . As N (v) is an independent set, S 2 ❖ 0 I 2 and |C ∩ N (v)| ≤ 1. Moreover, C ❖ 1 S 2 and S 2 ⊆ N (v) implies that if S 2 = ∅, then |C ∩ N (v)| = 0, that is v ❖ 1 C. Lemma 17 If S 1 ❖ 0 I 1 then G is probe split.
Proof: We split the proof into two cases. is a valid probe split partition.

2. v ❖ 1 C. Because N (v) is independent, v is non-adjacent to precisely one vertex c of C. Then, for the same reason, S 2 = ∅ and c ❖ 0 I 2 . Define

I 11 = I 1 ∩ N (c), I 12 = I 1 \ I 11 .
We may assume I 11 to be non-empty, because otherwise (Cc + v, S 1 , I + c) would be a valid probe split partition. We may also assume that

I 21 = {x ∈ I 2 | |N (x) ∩ S 1 | ≥ 2}, A = {x ∈ I 2 | |N (x) ∩ S 1 | = 1 ∧ x ❖ 1 (C -c)}, B = {x ∈ I 2 | |N (x) ∩ S 1 | = 1 ∧ x ❖ 1 (C -c)}, R = I 2 \ (I 21 ∪ A ∪ B).
Note that by this definition R ❖ 0 S 1 and A ❖ 1 (C -c). We first show that [START_REF] Sheng | Cycle free probe interval graphs[END_REF].

I 21 ❖ 1 (C -c). (14)
We now may assume that

B = ∅ because otherwise (C -c, I 21 ∪ A ∪ {c, v}, I 1 ∪ R ∪ S 1
) is a valid probe split partition. We next show that precisely one vertex s B ∈ S 1 exists such that s B is the unique neighbour in S 1 of every vertex in B, that is We claim that (Q, U, J) with

N (B) ∩ S 1 = {s B }. (15
Q = C -c + s B , U = I 21 ∪ A ∪ {c, v}, J = I 1 ∪ R ∪ B ∪ (S 1 -s B )
is a valid probe split partition: Independence of U and J is clear by definition of A, B, R and s B and Q ❖ 1 U follows from ( 14) and ( 16).

✷

We turn to the case when

S 1 ❖ 0 I 1 . Let x ∈ S 1 , y ∈ I 1 with xy ∈ E such that |N (x) ∩ I 1 | + |N (y) ∩ S 1 |
is maximum. Partition I 1y and S 1x as:

I 11 = (I 1 -y) ∩ N (x), I 12 = (I 1 -y) \ I 11 , S 11 = (S 1 -x) ∩ N (y), S 12 = (S 1 -x) \ S 11 .
For some of the following lemmas it is important to recall that G[N (v)] is assumed to be a split graph and therefore (2K We are now ready to prove the first case of the lemma, distinguishing two cases: This settles the second case, and Th. 31 is proved.

  be a split graph with clique K and independent set U . Now, let C = K ∩ P , S = K ∩ N and I = U . In G clearly C is a clique, S and I are independent, and C ❖ 1 S. (⇐) Let G = (V, E) be a graph with a partition (C, S, I) of V into a clique C and independent sets S, I such that C ❖ 1 S. Now, let P = C ∪ I, N = S and E

  If u and v are adjacent, then, for all adjacent vertices x ∈ X \ {u} and y ∈ Y \ {v}, c 1 ∼ y or c 2 ∼ x.

Case 1 :

 1 There exists a vertex c ∈ C non-adjacent to a vertex a ∈ X and non-adjacent to a vertex b ∈ Y . As c ∈ C and because of Prop. 6.a, a ∼ b. Hence, by Claim 1, every shortest path in B ′ connecting a and b must consist of exactly four vertices (including a, b); let v 1 v 2 v 3 v 4 with v 1 = a and v 4 = b be a shortest path in B ′ .

  I 11 ❖ 1 (C -c) because otherwise (C -c + v, I 11 ∪ S 1 , I 2 ∪ I 12 ∪ {c}) would be a valid probe split partition. Let i 11 ∈ I 11 and c 11 ∈ Cc such that i 11 c 11 ∈ E (note that i 11 c ∈ E). Partition I 2 as:

) Assume there are b 1 , b 2 ∈

 12 B with unique neighbour s 1 , s 2 ∈ S 1 , respectively (b 1 = b 2 , s 1 = s 2 ). Then c 11 b 1 and c 11 b 2 are both edges, because otherwise b 1 s 1 b 2 s 2 vci 11 c 11 would induce a A 37 or a A 36 . According to the definition of B, a vertex c 1 ∈ Cc exists that is a non-neighbour of b 1 . c 1 i 11 ∈ E, because otherwise we again have a A 37 or a A 36 (b 1 s 1 b 2 s 2 vci 11 c 1 ). But now b 1 s 1 b 2 s 2 vci 11 c 11 c 1 induces a A 47 (if c 1 b 2 ∈ E) or a A 48 (if c 1 b 2 ∈ E). This proves s 1 = s 2 and thus (15). Finally we show that s B ❖ 1 (I 21 ∪ A). (16) Let x ∈ I 21 ∪ A be a non-neighbour of s B and let s 1 ∈ S 1 be a neighbour of x. Let b ∈ B with non-neighbour c b ∈ Cc. By (14) and the definition of A, x ❖ 1 (C -c). Both i 11 c b and c 11 b are edges because otherwise i 11 cvs 1 s B bxc b , and i 11 cvs 1 s B bxc 11 , respectively, induce a A 36 . But then i 11 cvs 1 s B bxc 11 c b induce a A 48 . (16) follows.

  (a) S 12 = ∅We claim that (Q, U, J) withQ = Cc + y + s i , U = {v, c}, J = (Iy) ∪ (S 11s i + x) ∪ S 12is a valid probe split partition. By Lem. 19, Q is a clique and by assumption U is independent. By (27), x is non-adjacent to Jx and by (28), S 11s i is non-adjacent to I, thus J is independent.(b)S 12 = ∅ If I 12 ∩ N (c) = ∅, then is (Cc + v + y, S 11x, Iy + c) a valid probe split partition. Otherwise (Q, U, J) with Q = Cc + y + s i , U = {v, c}, J = (Iy) ∪ (S 11s i + x)is a valid probe split partition.because if a ∈ A were adjacent to s 1 ∈ S 1 then xyas 1 induce a B 4 ; if b ∈ B were adjacent to s 0 ∈ S 0 , then by Lem. 30 and definition of B, bx ∈ E and thus xybs 0 induce a B 2 ; if s ∈ S N were adjacent to i ∈ I 0 then xysi induce a B 2 . Furthermore,|(S 1 + x) ∩ N (B)| ≤ 1 ∧ |(I 1 + y) ∩ N (S N )| ≤ 1 : (36) If b ∈ B has two neighbours s, s ′ ∈ S 1 + x, then ybss ′ induce a B 4 . And if s, s ′ ∈ S 1 + x (s = s ′ ) have different neighbours b, b ′ ∈ B, respectively, then bsys ′ b ′ induce a B 8 .The proof of the second statement is similar.We now consider three cases.(a) B ❖ 0 S 1 By (36), we letS 1 ∩ N (B) = {s B }, then B ❖ 0 S 1 + x -s B . Let b ∈ B be adjacent to s B .ThenA = ∅, I 1 = ∅, y ❖ 1 C,because otherwise axys B b, with a ∈ A, would induce a B 8 ; xi 1 s B b, with i 1 ∈ I 1 , would induce a B 2 ; and xycs B , with c ∈ C non-adjacent to y, would induce a B 3 or a B 4 .Then G is a split graph with clique C + s B + y and independent set (Ss B ) ∪ (Iy), and thus trivially probe split.(b) B ❖ 0 S 1 ∧ S N ❖ 0 (I 1 + y) By (36), we let (I 1 + y) ∩ N (S N ) = {i S }, then S N ❖ 0 I 1 + y -i S . Then A ❖ 0 S 0 , i S ❖ 1 C,because otherwise si S xas 0 , with a ∈ A adjacent to s 0 ∈ S 0 and s ∈ S N adjacent to i S , would induce a B 9 ; and xcsi S , with s ∈ S N adjacent to and c ∈ C non-adjacent to i S , would induce a B 4 .Then G is a split graph with clique C + i S + x and independent set (Sx) ∪ (Ii S ) and thus trivially probe split.(c) B ❖ 0 S 1 ∧ S N ❖ 0 (I 1 + y)First assume that S 1 = ∅. Let s 1 ∈ S 1 , then A ❖ 0 S 0 , y ❖ 1 C,because otherwise as 0 s 1 y, with a ∈ A and s 0 ∈ S 0 neighbours, would induce a B 2 ; and xycs 1 , with c ∈ C non-adjacent to y, would induce a B 3 or a B 4 .Then G is a split graph with clique C + x + y and independent set (Sx) ∪ (Iy) and thus trivially probe split.Next assume S 1 = ∅. If we add all edges between vertices in A then we get a split graph with clique C + x ∪ A and independent set (Sx) ∪ (I \ A). As A ⊆ N , if follows that Q is probe split with respect to the partition (N, P ).

  This gives A 7 . Obs. 2 gives A 8 (C 4 ∪ P 2 ) to A 10 , A 22 (3K 2 ) and A 24 (2P 3 ). Obs. 3 gives A 11 (antenna) to A 19 , A 25 to A 28 and A 40 . Obs. 4 gives A 2 , A 3 , A 35 , and odd cycles of length at least 7. Additionally a C 5 is forbidden because it cannot consist solely of S and I vertices, but if it contains a C vertex, then its two non-neighbours in the C 5 , which must be I-vertices, are adjacent to each other. This gives odd holes (A 1 ). Note that A 26 (P 6 )

  and define S = B ′ S(B ′ ).

	A 31	A 32	A 33	A 34		A 35	A 36
	A 37	A 38	A 39	A 40	A 41	A 42
	A 43	A 44	A 45	A 46	A 47	A 48	A 49
	A 50	A 51	A 52

  Theorem 9 Algorithm 1 correctly recognizes probe split graphs, and can be implemented with running time O(V 2 + V E).

	Proof: Correctness follows from Lem. 5, Prop. 6, Prop. 7 and Prop. 8. It is obvious that calculating B and
	C and verifying Prop. 6 and Prop. 7 (first if-statement) can be done in the desired timebound. The next two
	if-statement form a recursive algorithm. Note that in the recursion we do not need to calculate B, C, nor
	to verify Prop. 6 and Prop. 7. Let n = |V \ (B ∪ C)|, then the basis of the recursion (second if-statement)
	can be executed in time T (0) = O(V +E), and the third if-statement takes T (n) = T (n-1)+O(V +E)
	by Prop. 8. Solving the recurrence gives O

  be the smallest index such that v ∼ v i ; such an i exists otherwise v, v 1 , . . . , v 2k would induce a A 2 . Note that, by the choice of i, v ∼ v j , j = 2, 3, . . . i -1, and by Prop. 6.a, v ∼ v i+1 . Moreover, i must be odd otherwise v, v 1 , v 2 , . . ., v i would induce a A 2

  1. v ❖ 1 C. We may assume S 1 ❖ 0 I 2 (otherwise (C, S 2 ∪ {v}, I ∪ S 1 ) is a valid probe split partition of G), I 1 ❖ 0 S 2 (otherwise (C ∪ {v}, S 1 , I ∪ S 2 ) is a valid probe split partition), and C = ∅ (otherwise({v}, S 1 ∪ I 1 , S 2 ∪ I 2) is a valid probe split partition). In particular I 1 , I 2 , S 1 , S 2 all are non-empty. Define I 21 = I 2 ∩ N (S 1 ),I 22 = I 2 \ I 21 , I 11 = I 1 ∩ N (S 2 ), I 12 = I 1 \ I 11 .Note thatI21 and I 11 are non-empty. We show that I 21 ❖ 1 C or I 11 ❖ 1 C. Let i 11 ∈ I 11 with a neighbour s 2 ∈ S 2 and a non-neighbour c ∈ C and let i 21 ∈ I 21 with a neighbour s 1 ∈ S 1 and a non-neighbour c ′ ∈ C. If c ′ = c then vci 11 i 21 s 1 s 2 induce a A 11 (antenna), and if c = c ′ then vcc ′ i 11 i 21 s 1 s 2 induce a A 28 . Thus either I 21 ❖ 1 C or I 11 ❖ 1 C. If I 21 ❖ 1 C, then (C, {v} ∪ S 2 ∪ I 21 , I 1 ∪I 22 ∪S 1 ) is a valid probe split partition and if I 11 ❖ 1 C then (C ∪{v}, S 1 ∪I 11 , I 12 ∪S 2 ∪I 2 )

  Let x ∈ I 21 with two neighbours u, u ′ ∈ S 1 and a non-neighbourc x ∈ Cc. If i 11 c x ∈ E then vuu ′ cxi 11 c x induces a A 20 , if xc 11 ∈ E then vuu ′ cxi11 c 11 induces a A 20 , and if both are edges then vuu ′ cxc x i 11 c 11 induces a A 46 . This proves

  First, there cannot be an edge between S 11 and I 11 or between S 12 and I 12 , because together with x, y this edge would induce a C 4 or 2K 2 , respectively, in N (v). Secondly, suppose an edge x ′ y ′ exists, with x ′ ∈ S 11 , y ′ ∈ I 12 . Then I 11 = ∅, because otherwise x, x ′ , y ′ and a vertex fromI 11 would induce a 2K 2 in N (v), which implies that |N (x ′ ) ∩ I 1 | + |N (y) ∩ S 1 | > |N (x) ∩ I 1 | + |N (y) ∩ S 1 |,contradicting the choice of x, y. Similarly, there is no edge between I 11 and S 12 .✷Lemma 19 If S 11 = ∅ then y ❖ 1 (C ∩ N (v)). If y is non-adjacent to some c ∈ (C ∩ N (v)) then x,y, c and a vertex from S 11 induce a C 4 in N (v). ✷ Lemma 20 Either S 2 ❖ 0 I 11 or I 2 ❖ 0 S 11 . Proof: Assume there are edges s 2 i 11 and i 2 s 11 with s 2 ∈ S 2 , i 11 ∈ I 11 , i 2 ∈ I 2 , s 11 ∈ S 11 . If xi 2 ∈ E or ys 2 ∈ E then vs 2 i 2 s 11 i 11 together with x or y, respectively, induce a A 11 (antenna); if neither are edges then vs 2 i 2 s 11 i 11 xy induce a A 2 . ✷ Lemma 21 a) Either S 2 ❖ 0 I 12 or S 2 ❖ 0 (I 11 + y) or I 2 ❖ 0 (S 11 + x). b) Either I 2 ❖ 0 S 12 or I 2 ❖ 0 (S 11 + x) or S 2 ❖ 0 (I 11 + y). We prove the first statement; the second is symmetrical. Assume there are edges s 2 i 12 , s ′ 2 z and i 2 t with s 2 , s ′ 2 ∈ S 2 , i 12 ∈ I 12 , i 2 ∈ I 2 , z ∈ I 11 + y, t ∈ S 11 + x. By Lem. 20, z = y or t = x, implying that z and t are adjacent. If zs 2 ∈ E or i 12 s ′ 2 ∈ E then vzti 2 together with s 2 or s ′ 2 , respectively, induces a A 11 (antenna); if neither are edges then vzti 12 i 2 s 2 s ′ 2 induces a A 6 (eiffeltower). Consider an edge i 2 s 12 with i 2 ∈ I 2 , s 12 ∈ S 12 . We may assume that xi 2 ∈ E, because otherwise the previous case applies. vc ∈ E because otherwise vi 12 s 2 cs 12 would induce a C 5 and hence i 2 c ∈ E because otherwise vi 12 s 2 cs 12 i 2 would induce a A 11 (antenna). Now, if yc ∈ E then either vxycs 2 i 2 s 12 i 12 induces a A 19 (if ys 2 ∈ E) or vxycs 2 i 2 s 12 induces a A 27 . If yc ∈ E then either vxycs 2 i 12 induces a A 23 (if ys 2 ∈ E) or vxycs 2 i 2 s 12 i 12 induces a A 40 (if ys 2 ∈ E). Lemma 23 If S 2 ❖ 0 I 12 and I 2 ❖ 0 (S 11 + x) then G is probe split. Let i 2 ∈ I 2 and s 11 ∈ S 11 be neighbours. First, consider a vertex i 11 ∈ I 11 that is adjacent to c. Then either vxcs 11 i 2 i 11 induce a A 9 (co-fish) (if xi 2 ∈ E) or vxycs 11 i 2 i 11 induce a A 10 (otherwise). Next, assume i 12 ∈ I 12 is adjacent to c. Let i 11 ∈ I 11 , then ci 11 ∈ E. Now either vxyci 11 s 11 i 2 i 12 induce a A 38 (if xi 2 ∈ E) or vxycs 11 i 2 s 12 induce a A 20 (if xi 2 ∈ E). Finally assume s 12 ∈ S 12 exists. Let i 11 ∈ I 11 , then ci 11 ∈ E. Now either vxyci 11 s 11 i 2 s 12 induce a A 38 (if xi 2 ∈ E) or vxycs 11 i 2 s 12 induce a A 20 (if xi 2 ∈ E). This finishes the proof of (26). By (26), (Cc + v + y, S, Iy + c) is a valid probe split partition if I 11 = ∅. Now we assume I 11 = ∅. If S 12 = ∅ then x ❖ 0 I 2 . Let s 12 ∈ S 12 . First, if i 2 ∈ I 2 ∩ N (S 11 ) with neighbour s 11 ∈ S 11 is adjacent to c, then vxycs 12 i 2 s 11 induce either a A 20 (if ci 2 ∈ E) or a A 10 (if ci 2 ∈ E). Next, let i 2 ∈ I 2 be adjacent to s 11 ∈ S 11 and assume i ′ 2 ∈ I 2 is non-adjacent to x. But then vxycs 12 i 2 s 11 i ′ 2 induce either a A 36 (if ci 2 , ci ′ 2 ∈ E) or a A 39 (if ci 2 , ci ′ 2 ∈ E) or a A 38 (otherwise). This finishes the proof of (27). If S 12 ∪ (I 12 ∩ N (c)) = ∅ then ∃!s i ∈ S 11 : S 11 ∩ N (I 2 ) = {s i }. (28) We already know we may assume |S 11 ∩ N (I 2 )| ≥ 1. Let t ∈ S 12 ∪ (I 12 ∩ N (c)) and s, s ′ ∈ S 11 ∩ N (I 2 ). If s, s ′ have a common neighbour i 2 ∈ I 2 then vyctss ′ i 2 induce a A 20 , if they have private neighbours i 2 , i ′ 2 ∈ I 2 , respectively, then vyctss ′ i 2 i ′ 2 induce a A 36 . This finishes the proof of (28).

	Proof: Proof: ✷ (27)

2 , C 4 , C 5 )-free. Lemma 18 (S 11 ∪ S 12 ) ❖ 0 (I 11 ∪ I 12 )

Proof: ✷ Lemma 22 If I 2 ❖ 0 S 1 then (I 12 ∩ N (S 2 )) ❖ 1 C.

Proof: Seeking a contradiction, assume i 12 ∈ I 12 ∩ N (S 2 ) is non-adjacent to c ∈ C. Let s 2 ∈ S 2 be a neighbour of i 12 . We distinguish two cases matching the partition of S 1 .

1. I 2 ❖ 0 (S 11 + x)

Consider an edge i 2 z with i 2 ∈ I 2 , z ∈ S 11 + x. Then z is adjacent to c, v, y and non-adjacent to s 2 , i 12 . Thus v must be adjacent to c because otherwise vi 12 s 2 cz would induce a C 5 . Furthermore, y is non-adjacent to s 2 (otherwise vyzs 2 i 2 i 12 would induce a A 11 (antenna)) and hence non-adjacent to c (otherwise vyzs 2 i 12 c would induce a A 23 ). But now either vczs 2 i 2 i 12 induces a A 11 (antenna) (if i 2 c ∈ E) or vczs 2 i 2 i 12 y induces a A 17 (if i 2 c ∈ E).

2. I

2 ❖ 0 S 12

(i) In fact, we verified by computer that the graphs in Fig.1are minimal non probe split graphs.

Proof: We show that (Q, U, J) with

is a valid probe split partition. By assumption S 2 = ∅, therefore v ❖ 1 C and Q is a clique. By Lem. 18, U is independent and by Lem. 22, U ❖ 1 Q. Finally, by Lem. 21.a, J is independent.

✷

Lemma 24 If I 2 ❖ 0 S 12 and S 2 ❖ 0 (I 11 + y) then G is probe split.

Proof: We show that (Q, U, J) with

is a valid probe split partition. Again is by assumption S 2 = ∅ and thus Q a clique. By Lem. 18, U is independent and by Lem. 21.b, J is independent. First we show that

Let z ∈ (I 11 + y) ∩ N (S 2 ) be non-adjacent to c ∈ C and adjacent to s 2 ∈ S 2 . Let i 2 ∈ I 2 and s 12 ∈ S 12 be neighbours, and note that by Lem. 21.b, i 2 x ∈ E. But now either vczs 2 s 12 i 2 induce a A 11 (antenna), or vczs 2 s 12 i 2 x induce a A 27 . This proves (17).

Next we show that

Let z ∈ (I 11 + y) \ N (S 2 ) be non-adjacent to c ∈ C. Let i 2 ∈ I 2 and s 12 ∈ S 12 be neighbours, and let s 2 ∈ S 2 and t ∈ I 11 + y be neighbours as well. Note that t = z and that by (17) tc ∈ E. But now vcxzts 2 s 12 i 2 induce either a A 29 (if ci 2 ∈ E) or a A 30 (if ci 2 ∈ E). ✷

Lemma 25 If I 2 ❖ 0 S 12 and S 2 ❖ 0 (I 11 + y) then G is probe split.

Proof: We distinguish two cases:

We show that (Q, U, J) with

is a valid probe split partition. By assumption v ❖ 1 C and thus Q is a clique. By Lem. 18, U is independent and by Lem. 22, U ❖ 1 Q. Finally, by assumption J is independent.

v ❖ 1 C

By the discussion after the definition of S 2 , we have that S 2 = ∅ and that v is non-adjacent to precisely one vertex c ∈ C. Furthermore, c ❖ 0 I 2 , because N (v) is assumed to be independent. We start by showing that

Let z ∈ N (c) ∩ (I 11 + y), and i 2 ∈ I 2 with a neighbour s 12 ∈ S 12 . Then xi 2 ∈ E, and thus

) because otherwise cc ′ vxs 12 i 12 i 2 induce a A 20 . Finally, assume that a vertex

is a valid probe split partition. Otherwise (Q, U, J) with By assumption, A = ∅ and S 2 = ∅ and thus v ❖ 1 C. We first show that

, then zxvc 1 c 2 and a neighbour of z in S 2 induce a A 24 (2P 3 ). This proves that every vertex in

) and if they have private neighbours s, s ′ , respectively, then vzz ′ cxss ′ induce a A 25 . This proves that every two vertices in A have the same neighbours in C, thereby implying the validity of (21). We now distinguish two cases:

is a valid probe split partition.

So, assume that Ay = ∅, then, by Lem. 20, I 2 ❖ 0 S 11 . Note that A ❖ 1 C both when y ∈ A and when y ∈ A: If y ∈ A then this follows from y ❖ 1 C and (21); if y ∈ A and a ∈ A is non-adjacent to c ∈ C and adjacent to s ∈ S 2 then avcys together with a vertex from S 11 induce a A 23 . Now we can show that (Q, U, J) with

is a valid probe split partition (note that y may or may not be in A): We have demonstrated that

2 ∈ E and with s 2 ∈ S 2 a neighbour of a). This proves the second statement.

). This finishes the proof of (24).

For the remainder of the proof of the lemma we consider two cases:

(a)

is a valid probe split partition (note that c A might not exist). It is clear that Q is a clique and that J is independent. By (21), ( 22) and ( 23), U is independent and by ( 23) and the case

By ( 23), I 11 = ∅, and by ( 24), (S 2 ∩ N (I 12 )) ❖ 1 y and C ❖ 1 y. Thus (Q, U, J) with

is a valid probe split partition.

✷

Lemma 27 If I 2 ❖ 0 S 12 and S 2 ❖ 0 (I 11 + y), then G is probe split.

Proof:

We may assume v ❖ 1 C because otherwise (C + v, S \ S 2 , I ∪ S 2 ) is a valid probe split partition. So let c ∈ C be the single non-neighbour of v in C. Then S 2 = ∅ and c ❖ 0 I 2 . We may also assume that S 11 = ∅ because otherwise (Cc + x, {c, v}, I ∪ S 12 ) is a valid probe split partition. We start by proving By (25), (Q, U, J) with

is a valid probe split partition if yc ∈ E. So assume yc ∈ E. We may then also assume I 2 ❖ 0 S 11 because otherwise (Cc + x + y, {c, v}, I ∪ S) is a valid probe split partition. We prove that if

We may assume I 2 ❖ 0 (S 11 + x), because otherwise by Lem. 22, (Q, U, J)

). Finally, assume z ∈ I 11 + y is non-adjacent to c ′ ∈ Cc. Then vxzcc ′ i 12 s 2 induce a A 28 . Thus (Cc) ❖ 1 (I 11 + y), finishing the proof of (31).

We claim that (Q, U, J) with

is a valid probe split partition. It is clear that Q is a clique. By (31), U is independent and U ❖ 1 Q and by assumption J is independent. ✷ Lemma 28 (Prop. 8) If Gv is a probe split graph, then so is G. Moreover, a probe split partition of G can be obtained from a probe split partition of Gv in linear time.

Proof: Lem. 24 to 27 cover all possible relations between I 2 and S 12 and between S 2 and I 11 + y and therefore prove that if Gv is probe split, then so is G. The proofs of those lemmas also show how a probe split partition of G can be calculated from a probe split partition of Gv. It is straightforward that this can be done in linear time using suitable data structures. ✷

Partitioned probe split graphs

In this section we investigate graphs G = (N, P, E) with a given partition of its vertex set into probes P and non-probes N , with G[N ] an independent set.

Definition 29 A graph G = (N, P, E), with N an independet set, is a partitioned probe split graph (with respect to the partition

First we prove a characterisation by 10 forbidden induced subgraphs for partitioned probe split graphs, and then we give a polynomial recognition algorithm.

In this section we shall write X N , X P for the intersection of a vertex set X with N, P , respectively in a partitioned probe split graph (N, P, E). Theorem 31 G = (N, P, E) with N an independent set is a partitioned probe split graph iff G has none of the graphs of Fig. 2 as an induced subgraph.

Proof: It is clear that if G is probe split, then G does not contain any of the graphs of Fig. 2 as an induced subgraph. For the other direction it is easy to verify that if G does not contain any of the graphs in Fig. 2, then G does not contain any of the graphs in Fig. 1 either, and thus G is probe split. Let (C, S, I) be a probe split partition of G. We distinguish two cases.

S P ❖ 0 I

Suppose B = ∅. If we add all edges between vertices in N ′ = S N ∪ A ∪ C N then we get a split graph with clique Q = N ′ ∪ C P and independent set V (G) \ Q. As N ′ ⊆ N , it follows that G is probe split with respect to the partition (N, P ).

So assume B = ∅. Then S N ❖ 0 I P :

Let n ∈ S N be adjacent to i ∈ I P and let b ∈ B with neighbour s ∈ S P and non-neighbour c ∈ C P .

Then bscni induce either a B 9 (if ic ∈ E) or a B 10 (if ic ∈ E).

To see this, note first that by Lem. 30 and definition of B, every vertex in B has exactly one neighbour in S P . Suppose now that vertices s, s

Suppose s B is non-adjacent to a ∈ A. Let b ∈ B be non-adjacent to c ∈ C P and let s ∈ S P be a neighbour of a. Then bs B csa induce a B 10 .

Now, if we add all edges between vertices in N ′ = A ∪ C N then we get a split graph with clique Q = N ′ ∪ C P + s B and independent set V (G) \ Q. As N ′ ⊆ N , it follows that G is probe split with respect to the partition (N, P ). This settles the first case. Then S 1 ❖ 0 I 1 (otherwise there would be a B 3 ) and S 0 ❖ 0 I 0 (otherwise there would be a B 1 ). Moreover, S 1 ❖ 0 I 0 : If x 1 ∈ S 1 is adjacent to y 0 ∈ I 0 , then I 1 = ∅ (otherwise there would be a Theorem 32 Given G = (N, P, E) with N an independent set, it can be decided in O(V 2 + V E) time whether G is probe split.

Proof: First check with Alg. 1 that G is probe split and, if so, calculate a valid partition (C, S, I). Next check that Lem. 30 holds and work through Th. 31. This can be done in the desired timebound. ✷


"Trivializing" Generalizations of some Izergin-Korepin-type Determinants Tewodros Amdeberhan 1 and Doron Zeilberger 2 1 Tulane Univ., Dept of Math., New Orleans, LA 70118, USA 2 Rutgers Univ., Dept of Math., Piscataway, NJ 08854, USA received May 8, 2007, revised June 13, 2007;July 31, 2007, accepted July 31, 2007. We generalize (and hence trivialize and routinize) numerous explicit evaluations of determinants and pfaffians due to Kuperberg, as well as a determinant of Tsuchiya. The level of generality of our statements render their proofs easy and routine, by using Dodgson condensation and/or Krattenthaler's factor exhaustion method.

All our matrices will be assumed to be embedded inside an infinite matrix. The first theorem adds parameters to the determinant formulas found in Kuperberg [START_REF] Kuperberg | Symmetry classes of alternating-sign matrices under one roof[END_REF]Theorem 15], as well as older determinants, mentioned there, due to Cauchy, Stembridge, Laksov-Lascoux-Thorup, and Tsuchiya [T]. This way, the formulation is suited to the method of [AZ]. Our proofs are much more succinct and automatable, since their generality enables an easy induction using Dodgson's rule [D, AZ], or by employing Krattenthaler's elegant factor exhaustion method [START_REF] Krattenthaler | Advanced determinant calculus[END_REF]. Relevant background for this paper can found in [Ku], and references thereof.

Theorem 1 det 1 x i + y j + Ax i y j 1,n i,j = i<j (x j -x i )(y j -y i ) n i,j (x i + y j + Ax i y j ) . det 1 x i + y j - 1 1 + x i y j 1,n i,j = i<j (1 -x i x j )(1 -y i y j )(x j -x i )(y j -y i ) n i,j (x i + y j )(1 + x i y j ) • n i=1 (1 -x i )(1 -y i ). det Ay j + Bx i y j + x i 1,n i,j = (A -B) n-1 A n j y j + (-1) n-1 B n i x i i<j (x i -x j )(y i -y j ) n i,j (x i + y j ) . det 1 -x i y j y j -x i 1,n i,j = (-1) ( n 2 ) n j (1 + x j )(1 -y j ) + n i (1 -x i )(1 + y i ) i<j (x i -x j )(y i -y j ) 2 n i,j (y j -x i )
.

det 1 x i + y j 1,n i,j = i<j (x j -x i )(y j -y i ) n i,j (x i + y j )
.

Pf 2 = det x j -x i x j + x i 1,2n i,j = i<j≤2n (x i -x j ) 2 (x i + x j ) 2 . Pf 2 = det x j -x i 1 -x i x j 1,2n i,j = i<j≤2n (x i -x j ) 2 (1 -x i x j ) 2 .
Remark 1 Notice that the latter two statements apply only to even-dimensional matrices. An error from [Ku] in the second formula has been corrected here. Pf stands for Pfaffian of a matrix.

The next theorem generalizes, and presents variations of, several of the determinants that appear in Theorems 16 and 17 [Ku] (typos corrected in [Kr2, Theorems 13 and 14]). Below, Z 1 , Z 2 , Z 3 , Z 4 , Z 5 are defined by (here

γ(a, b) = a -b, τ (a, b) = a + b) Z 1 (p, q; x, y) i,j = γ(q j-i , x j-i ) τ (p j-i , y j-i ) , Z 2 (p, q; x, y) i,j = γ(q 1+j-i , x 1+j-i ) τ (p 1+j-i , y 1+j-i ) , Z 3 (p, q; x, y) i,j = γ(q -1+j-i , x -1+j-i ) τ (p -1+j-i , y -1+j-i ) , Z 4
(q, q; x, x) i,j = γ(q a+j-i , x a+j-i ) τ (q a+j-i , x a+j-i ) , Z 5 (q, q; x, x) i,j = τ (q b+j-i , x b+j-i ) γ(q b+j-i , x b+j-i ) ,

for a ∈ Z, b = ±n, ±(n + 1), . . . . Let δ e,n = 1+(-1) n 2 denote Kronecker's delta function centered at the even integers, and let λ i,j = 1, if i = j and λ i,i = 0.

Theorem 2 Write γ(a, b) = a -b, τ (a, b) = a + b, we have the matrix determinants

det γ(q n+j-i , x n+j-i ) γ(p n+j-i , y n+j-i ) 1,n i,j = (py) ( n 3 ) γ(q, x) n j>i γ(p j-i , y j-i ) 2 γ(qp j-i , xy j-i )γ(xp j-i , qy j-i ) i,j γ(p n+j-i , y n+j-i ) . det τ (q j-i , x j-i ) τ (p j-i , y j-i ) 1,n i,j = 2|j-i>0 γ(p j-i , y j-i ) 2 2∤j-i>0 γ(qp j-i , xy j-i )γ(xp j-i , qy j-i ) (qx) ⌊n 2 /4⌋ j>i τ (p j-i , y j-i ) 2 . det(Z 1 ) 1,n i,j = δ e,n γ(q, x) n (py) n/2 (qx) ⌊n 2 /4⌋
2|j-i>0 γ(p j-i , y j-i ) 2 γ(qp j-i , xy j-i )γ(xp j-i , qy j-i ) j>i τ (p j-i , y j-i ) 2

. det(Z 2 ) 1,n i,j = γ(q, x) n (qx) ⌊(n-1) 2 /4⌋ 2|j-i>0 γ(p j-i , y j-i ) 2 γ(qp j-i , xy j-i )γ(xp j-i , qy j-i ) τ (p n , y n ) 1-δe,n j>i τ (p j-i , y j-i ) 2

. det(Z 3 ) 1,n i,j = (-py) n γ(q, x) n (qx) ⌊(n+1) 2 /4⌋ 2|j-i>0 γ(p j-i , y j-i ) 2 γ(qp j-i , xy j-i )γ(xp j-i , qy j-i ) τ (p n , y n ) 1-δe,n j>i τ (p j-i , y j-i ) 2

.

det(Z 4 ) 1,n i,j = 2 n-1 q na + (-1) n x na (qx) n(n-1)(n+1-3a)/6 j =i γ(q |j-i| , x |j-i| ) i,j τ (q a+j-i , x a+j-i ) . det(Z 5 ) 1,n i,j = (-1) ( n 2 ) 2 n-1 q nb + x nb (qx) n(n-1)(n+1-3b)/6 j =i γ(q |j-i| , x |j-i| ) i,j γ(q b+j-i , x b+j-i ) . Pf 2 = det λ i,j γ(q j-i , x j-i )γ(r j-i , z j-i ) γ(p j-i , y j-i ) 1,2n i,j = (yp) n (qxrz) n 2 1,n j =i γ(p |j-i| , y |j-i| ) 2 1,n i,j γ(p n+j-i , y n+j-i ) 2 × 1,n i,j
γ(qp |j-i| , xy |j-i| )γ(xp |j-i| , qy |j-i| )γ(rp |j-i| , zy |j-i| )γ(zp |j-i| , ry |j-i| ).

Sketch of Proof: Identities Z 4 and Z 5 are directly amenable to Dodgson's Condensation technique [AZ]. For the remaining assertions, use the factor exhaustion method [START_REF] Krattenthaler | Advanced determinant calculus[END_REF] (see also [Ku]): the essential idea is to compare zeros and poles on both sides of the equation at hand. We leave the straightforward details to the reader. ✷

  1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France Sketch of Proof: An automatic application of Dodgson Condensation [D, AZ]. ✷ Corollary 1 (Cauchy, Stembridge, Laksov-Lascoux-Thorup)

Acknowledgments

The authors wish to thank Christian Krattenthaler for helpful suggestions.