Stavros D Nikolopoulos
email: stavros@cs.uoi.gr

Leonidas Palios
email: palios@cs.uoi.gr

Recognizing HH-free, HHD-free, and Welsh-Powell Opposition Graphs

Keywords: HH-free graph, HHD-free graph, Welsh-Powell opposition graph, perfectly orderable graph, recognition

In this paper, we consider the recognition problem on three classes of perfect graphs, namely, the HH-free, the HHDfree, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in O(n min{m α(n, n), m + n log n}) time whether a given graph G on n vertices and m edges contains a house or a hole; this implies an O(n min{m α(n, n), m + n log n})-time and O(n + m)-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement G of the graph G is HH-free can be efficiently resolved in O(nm) time using O(n 2 ) space, which leads to an O(n m)-time and O(n 2 )-space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required O(n 3 ) time and O(n 2 ) space.

Introduction

A linear order ≺ on the vertices of a graph G is perfect if the ordered graph (G, ≺) contains no induced P 4 abcd with a ≺ b and d ≺ c (such a P 4 is called an obstruction). In the early 1980s, Chvátal [START_REF]Perfectly ordered graphs[END_REF] defined the class of graphs that admit a perfect order and called them perfectly orderable graphs. The interest in perfectly orderable graphs comes from the fact that several problems in graph theory, which are NP-complete in general graphs, have polynomial-time solutions in graphs that admit a perfect order [1; 5]; unfortunately, it is NP-complete to decide whether a graph admits a perfect order [START_REF] Middendorf | On the complexity of recognizing perfectly orderable graphs[END_REF]. Since the recognition of perfectly orderable graphs is NP-complete, we are interested in characterizing graphs which form polynomially recognizable subclasses of perfectly orderable graphs. Many such classes of graphs, with very interesting structural and algorithmic properties, have been defined so far and shown to admit polynomial-time recognitions (see [1; 5]); note however that not all subclasses of perfectly orderable graphs admit polynomial-time recognition [START_REF] Hoàng | On the complexity of recognizing a class of perfectly orderable graphs[END_REF].

In this paper, we consider the class of HH-free graphs and two classes of perfectly orderable graphs, namely, the HHD-free, and the Welsh-Powell opposition graphs; note that the complement of an HH-free graph is perfectly orderable (this was conjectured by Chvátal and proved by Hayward [START_REF] Hayward | Meyniel weakly triangulated graphs I: co-perfect orderability[END_REF]). A graph is hole house domino P A P 5

Fig. 1: Some simple graphs.

HH-free if it contains no hole (i.e., a chordless cycle on ≥ 5 vertices) and no house as induced subgraphs (see Figure 1). The HH-free graphs properly generalize the class of triangulated (or chordal) graphs, i.e., graphs with no induced chordless cycles of length greater than or equal to four [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]. A subclass of HH-free graphs, which also properly generalizes the class of triangulated graphs, is the class of HHD-free graphs; a graph is HHD-free if it contains no hole, no house, and no domino as induced subgraphs (see Figure 1). In [START_REF] Hoàng | On brittle graphs[END_REF], Hoàng and Khouzam proved that the HHD-free graphs admit a perfect order, and thus are perfectly orderable.

A graph is called an Opposition graph if it admits a linear order ≺ on its vertices such that there is no P 4 abcd with a ≺ b and c ≺ d. Opposition graphs belong to the class of bip * graphs (see [START_REF] Brandstädt | Graph classes: A survey[END_REF]), and hence are perfect [START_REF] Olariu | All variations on perfectly orderable graphs[END_REF]. The complexity of recognizing opposition graphs is unknown. It is also open whether there is an opposition graph that is not perfectly orderable [START_REF] Brandstädt | Graph classes: A survey[END_REF]. The class of opposition graphs contains several known classes of perfectly orderable graphs. For example, bipolarizable graphs are, by definition, opposition graphs; a graph is bipolarizable if it admits a linear order ≺ on its vertices such that every P 4 abcd has b ≺ a and c ≺ d [START_REF] Olariu | Weak bipolarizable graphs[END_REF]. Another subclass of opposition graphs, which we study in this paper, are the Welsh-Powell opposition graphs. A graph is defined to be a Welsh-Powell Opposition graph (or WPO-graph for short), if it is an opposition graph for every Welsh-Powell ordering; a Welsh-Powell ordering for a graph is an ordering of its vertices in nondecreasing degree [START_REF] Welsh | An upper bound on the chromatic number of a graph and its applications to timetabling problems[END_REF].

Hoàng and Khouzam [START_REF] Hoàng | On brittle graphs[END_REF], while studying the class of brittle graphs (a well-known class of perfectly orderable graphs which contains the HHD-free graphs), showed that HHD-free graphs can be recognized in O(n 4 ) time, where n denotes the number of vertices of the input graph. An improved result was obtained by Hoàng and Sritharan [START_REF] Hoàng | Finding houses and holes in graphs[END_REF] who presented an O(n 3 )-time algorithm for recognizing HH-free graphs and showed that HHD-free graphs can be recognized in O(n 3 ) time as well; one of the key ingredients in their algorithms is the reduction to the recognition of triangulated graphs. Recently, Eschen et al. [START_REF] Eschen | Recognition of some perfectly orderable graph classes[END_REF] described recognition algorithms for several classes of perfectly orderable graphs, among which a recognition algorithm for HHP-free graphs; a graph is HHP-free if it contains no hole, no house, and no "P" as induced subgraphs (see Figure 1). Their algorithm is based on the property that every HHP-free graph is HHDA-free graph (a graph with no induced hole, house, domino, or "A"), and thus a graph G is HHP-free graph if and only if G is a HHDA-free and contains no "P" as an induced subgraph. The characterization of HHDA-free graphs due to Olariu (a graph G is HHDA-free if and only if every induced subgraph of G either is triangulated or contains a non-trivial module [START_REF] Olariu | Weak bipolarizable graphs[END_REF]) and the use of modular decomposition [START_REF] Mcconnell | Linear-time modular decomposition and efficient transitive orientation[END_REF] allowed Eschen et al. to present an O(n m)-time recognition algorithm for HHP-free graphs.

For the class of WPO-graphs, Olariu and Randall [START_REF] Olariu | Welsh-Powell opposition graphs[END_REF] gave the following characterization: a graph G is WPO-graph if and only if G contains no induced C 5 (i.e., a hole on 5 vertices), house, P 5 , or "P" (see Figure 1). It follows that G is a WPO-graph if and only if G is HHP-free and G is HH-free. Eschen et al. [START_REF] Eschen | Recognition of some perfectly orderable graph classes[END_REF] combined their O(n m)-time recognition algorithm for HHP-free graphs with the O(n 3 )-time recognition algorithm for HH-free graphs proposed in [START_REF] Hoàng | Finding houses and holes in graphs[END_REF], and showed that WPO-graphs can be recognized in O(n 3 ) time.

In this paper, we present efficient algorithms for recognizing HH-free, HHD-free, and WPO-graphs. We show that a variant of the classic linear-time algorithm for testing whether an ordering of the vertices of a graph is a perfect elimination ordering can be used to determine whether a vertex of a graph G belongs to a hole or is the top of a house or a building in G. We take advantage of properties characterizing the chordal completion of a graph and show how to efficiently compute for each vertex v the leftmost among v's neighbors in the chordal completion which are to the right of v, without explicitly computing the chordal completion. As a result, we obtain an O(n min{m α(n, n), m + n log n})-time and O(n + m)-space algorithm for determining whether a graph on n vertices and m edges is HH-free; we also describe how the algorithm can be augmented to provide a certificate (an induced house or hole) whenever it decides that the input graph is not HH-free.

Our HH-free graph recognition algorithm, in conjunction with results by Jamison and Olariu [START_REF] Jamison | On the semi-perfect elimination[END_REF] and by Hoàng and Khouzam [START_REF] Hoàng | On brittle graphs[END_REF], enables us to describe an algorithm for recognizing HHD-free graphs which also runs in O(n min{m α(n, n), m + n log n}) time and requires O(n + m) space. Additionally, for a graph G on n vertices and m edges, we show that we can detect whether the complement G of G is HH-free in O(n m) time using O(n 2 ) space. In light of the characterization of WPO-graphs due to Olariu and Randall [START_REF] Olariu | Welsh-Powell opposition graphs[END_REF] which implies that a graph G is a WPO-graph if and only if G is HHP-free and its complement G is HH-free, and the O(n m)-time recognition algorithm for HHP-free graphs of Eschen et al. [START_REF] Eschen | Recognition of some perfectly orderable graph classes[END_REF], our result yields an O(n m)-time and O(n 2 )-space algorithm for recognizing WPO-graphs.

The paper is structured as follows. In Section 2, we review the terminology that we use throughout the paper and we present well known results that are useful for our algorithms. In Section 3, we present the methodology and establish properties that enable us to efficiently determine whether a given graph is HH-free, describe the algorithm, and give its analysis and the certificate computation. The recognition algorithms for HHD-free graphs and WPO-graphs are described and analyzed in Section 4. Section 5 summarizes our results and presents some open problems.

Preliminaries

We consider finite undirected graphs with no loops or multiple edges. Let G be such a graph; then, V (G) and E(G) denote the set of vertices and of edges of G respectively. The subgraph of a graph G induced by a subset S of G's vertices is denoted by G

[S]. A subset B ⊆ V (G) of vertices is a module if 2 ≤ |B| < |V (G)| and each vertex x ∈ V (G) -B is
adjacent to either all vertices or no vertex in B. The neighborhood N (x) of a vertex x ∈ V (G) is the set of all the vertices of G which are adjacent to x. The closed neighborhood of x is defined as N [x] := N (x) ∪ {x}. We use M (x) to denote the set V (G) -N [x] of non-neighbors of x. Furthermore, for a vertex y ∈ M (x), we use n(x, y) to denote the number of vertices in the set N (x) ∩ N (y), i.e., the set of common neighbors of x and y, or equivalently, the degree of the vertex y in the graph induced by the set N (x) ∪ {y}. The degree of a vertex x in a graph G, denoted deg(x), is the number of edges incident on x; thus, deg(

x) = |N (x)|. A path v 0 v 1 • • • v k of a graph G is called simple if none of its vertices occurs more than once; it is called a cycle (simple cycle) if v 0 v k ∈ E(G). A simple path (cycle) is chordless if v i v j /
∈ E(G) for any two non-consecutive vertices v i , v j in the path (cycle). A chordless path (chordless cycle, respectively) on n vertices is commonly denoted by P n (C n , respectively). In particular, a chordless path on 4 vertices is denoted by P 4 . If abcd is a P 4 of a graph, then the vertices b and c are called midpoints and the vertices a Algorithm PEO(G, σ) Let G be a graph and let x, y be a pair of vertices. If G contains a path from vertex x to vertex y, we say that x is connected to y. The graph G is connected if x is connected to y for every pair of vertices x, y ∈ V (G). The connected components (or components) of G are the equivalence classes of the "is connected to" relation on the vertex set V (G). The co-connected components (or co-components) of G are the connected components of the complement G of the graph G.

1. for each vertex u ∈ V (G) do A(u) ← ∅; 2. for i ← 1 to n -1 do 3. u ← σ(i); 4. X ← {x ∈ N (u) | σ -1 (u) < σ -1 (
A graph G has a perfect elimination ordering if its vertices can be linearly ordered (v 1 , v 2 , . . . , v n ) so that each vertex v i is simplicial in the graph G i = G[{v i , v i+1 , . . . , v n }] induced by the vertices v i , v i+1 , . . . , v n , for 1 ≤ i ≤ n; a vertex of a graph is simplicial if its neighborhood induces a complete subgraph. It is well-known that a graph is triangulated if and only if it has a perfect elimination ordering [1; 5; 16]. The notion of a simplicial vertex was generalized by Jamison and Olariu [START_REF] Jamison | On the semi-perfect elimination[END_REF] who defined the notion of a semi-simplicial vertex: a vertex of a graph G is semi-simplicial if it is not a midpoint of any P 4 of G. A graph G has a semi-perfect elimination ordering if its vertices can be linearly ordered (v 1 , v 2 , . . . , v n ) so that each vertex v i is semi-simplicial in the graph G i , for 1 ≤ i ≤ n. A graph is a semi-simplicial graph if and only if it has a semi-perfect elimination ordering (see [START_REF] Eschen | Recognition of some perfectly orderable graph classes[END_REF]). 2, we include the classic algorithm PEO(G, σ) for testing whether the ordering σ is a perfect elimination ordering; if the graph G has n vertices and m edges, the algorithm runs in O(n + m) time and requires O(n + m) space [5; 16]. Note that, in Step 4 of the Algorithm PEO(G, σ), the set X is assigned the neighbors of the vertex u which have larger σ -1 ( )-values; that is, X = N (u) ∩ {σ(i + 1), . . . , σ(n)}; thus, in Step 6, the vertex w is the neighbor of u in G which is first met among the vertices to the right of u along the ordering σ.

Let σ = (v 1 , v 2 , . . . , v n ) be an ordering of the vertices of a graph G; σ(i) is the i-th vertex in σ, i.e., σ(i) = v i , while σ -1 (v i ) denotes the position of vertex v i in σ, i.e., σ -1 (v i ) = i, 1 ≤ i ≤ n. In Figure

Recognizing HH-free graphs

The most important ingredient (and the bottleneck too) of the HHD-free graph recognition algorithm of Hoàng and Sritharan [START_REF] Hoàng | Finding houses and holes in graphs[END_REF] is an algorithm to determine whether a simplicial vertex v of a graph G is high, i.e., it is the top of a house or a building (i) (or belongs to a hole) in G, which involves the following steps:

⊲ They compute an ordering of the set M (v) of non-neighbors of v in G where, for two vertices y, y ′ ∈ M (v), y precedes y ′ whenever n(v, y) ≤ n(v, y ′ ); recall that, for y ∈ M (v), n(v, y) is the number of common neighbors of v and y. As we will be using this ordering in the description of our approach, we call it a DegMN-ordering of M (v).

⊲ They perform chordal completion on G[M (v)] with respect to a DegMN-ordering of M (v).

⊲ The vertex v is high if and only if the graph G ′ v resulting from G after the chordal completion on

G[M (v)] is triangulated.
As we mentioned in the introduction, the algorithm of Hoàng and Sritharan runs in O(n 3 ) time, where n is the number of vertices of the input graph. In order to be able to beat this, we need to avoid the chordal completion step. Indeed, we show how we can take advantage of the Algorithm PEO and of properties of the chordal completion in order to compute all necessary information without actually performing the chordal completion. In particular, we prove that the following results hold:

Lemma 3.1 Let G be a graph, v a vertex of G, and (y 1 , y 2 , . . . , y k ) a DegMN-ordering of the non- neighbors M (v) of v in G. Moreover, let G ′ v be the graph resulting from G after the chordal comple- tion on G[M (v)] with respect to the DegMN-ordering (y 1 , y 2 , . . . , y k ) and let σ = (y 1 , y 2 , . . . , y k , x 1 , x 2 , . . . , x deg(v) , v) where x 1 , x 2 , . . . , x deg(v) is an arbitrary ordering of the neighbors of v in G. If Algo- rithm PEO(G ′ v , σ) returns "false" while processing vertex y i ∈ M (v), then A(y i ) -N (y i ) ⊆ N (v).
Proof: Since the Algorithm PEO returns "false" while processing vertex y i ∈ M (v), then A(y i ) -N (y i ) = ∅. Suppose that there exists a vertex y j ∈ M (v) belonging to A(y i ) -N (y i ). The vertex y j was added to A(y i ) at Step 7 of a prior iteration of the for-loop, say, while processing vertex y ℓ . It follows that σ -1 (y ℓ ) < σ -1 (y i ) < σ -1 (y j ), and y i , y j ∈ N (y ℓ ). Since y j / ∈ N (y i ), we have that

y ℓ is not simplicial in G ′ v [{y ℓ , y ℓ+1 , . . . , y k }]; a contradiction to the definition of G ′ v . ✷ Lemma 3.2 Let G ′ v
and σ be as in the statement of Lemma 3.1. The vertex v belongs to a C 5 or is the top of a house in the graph G ′ v if and only if Algorithm PEO(G ′ v , σ) returns "false" while processing vertex z, where z ∈ M (v).

Proof: (⇐=) The Algorithm PEO(G ′ v , σ) returns "false" while processing vertex z only if at Step 8 there exists a vertex

x ∈ A(z) -N (z). From Lemma 3.1 we have that A(z) -N (z) ⊆ N (v); thus, x ∈ N (v).
The vertex x was added to A(z) at Step 7 of a prior iteration of the for-loop, say, while processing vertex y;

then, σ -1 (y) < σ -1 (z) < σ -1 (x), and yz ∈ E(G ′ v ) and xy ∈ E(G ′ v ). Moreover, since z ∈ M (v) and x / ∈ N (z), we have that y ∈ M (v) and xz / ∈ E(G ′ v ). Since σ -1 (y) < σ -1 (z)
, the definition of the (i) A building is a graph on vertices v 1 , v 2 , . . . , vp, where p ≥ 6, and edges v 1 vp, v 2 vp, and

v i v i+1 for i = 1, 2, . . . , p -1; the vertex v 1 is called the top of the building. DegMN-ordering implies that n(v, y) ≤ n(v, z); because xy ∈ E(G ′ v ) and xz / ∈ E(G ′ v ), there exists a vertex x ′ ∈ N (v) such that x ′ z ∈ E(G ′ v ) and x ′ y / ∈ E(G ′ v ).
But then, the vertices v, x, x ′ , y, z induce either a C 5 or a house: if xx ′ / ∈ E(G ′ v ) then v belongs to a C 5 ; otherwise, v is the top of a house. (=⇒) Among the C 5 s of G ′ v to which v belongs and the houses of G ′ v with v as the top vertex, consider the C 5 or house whose vertices, say, y and z, that belong to M (v) are such that the quantity |σ -1 (y)-σ -1 (z)| is minimized. Let x, x ′ be the remaining two vertices of the C 5 or house, where x,

x ′ ∈ N (v), xy ∈ E(G ′ v ), xz / ∈ E(G ′ v ), x ′ z ∈ E(G ′ v ), and x ′ y / ∈ E(G ′ v )
, and suppose without loss of generality that σ -1 (y) < σ -1 (z) (see Figure 4(a); the dotted edge indicates a potential edge of G).

Next, we show that z is the leftmost among the neighbors of y that are to the right of y (with respect to σ) in G ′ v . Suppose for contradiction that the leftmost among these neighbors is

w = z. Then, σ -1 (y) < σ -1 (w) < σ -1 (z), and since yw ∈ E(G ′ v ) and yz ∈ E(G ′ v ), the definition of the graph G ′ v implies that wz ∈ E(G ′ v ). Additionally, if xw / ∈ E(G ′ v ), then due to the ordering σ, n(v, y) ≤ n(v, w), which (because xy ∈ E(G ′ v )) implies that there exists a vertex p ∈ N (v) such that pw ∈ E(G ′ v ) and py / ∈ E(G ′ v )
; but then, the vertices v, x, y, w, p induce a C 5 or a house to which v belongs and

|σ -1 (y)-σ -1 (w)| < |σ -1 (y)-σ -1 (z)|, in contradiction to the minimality of the C 5 or house induced by v, x, y, z, x ′ . Thus, xw ∈ E(G ′ v ). Then, if x ′ w / ∈ E(G ′ v ), the vertices v, x, w, z, x ′ induce a C 5 or a house to which v belongs and |σ -1 (w)-σ -1 (z)| < |σ -1 (y)-σ -1 (z)|, in contradiction to the minimality of the C 5 or house induced by v, x, y, z, x ′ . If however x ′ w ∈ E(G ′ v ) then, because n(v, w) ≤ n(v, z) (since σ -1 (w) < σ -1 (z)) and because xw ∈ E(G ′ v ) whereas xz / ∈ E(G ′ v ), there exists a vertex q ∈ N (v) such that qz ∈ E(G ′ v ) and qw / ∈ E(G ′ v )
; but then, the vertices v, x ′ , w, z, q induce a C 5 or a house to which v belongs and |σ -1 (w)σ -1 (z)| < |σ -1 (y)σ -1 (z)|, in contradiction again to the minimality of the C 5 or house induced by v, x, y, z, x ′ . Therefore, w = z. Then, while processing vertex y, the Algorithm PEO includes vertex x in X in Step 4 and later in Step 7 adds x in A(z); then, while processing vertex z, the Algorithm PEO detects that A(z) -N (z) = ∅ since x / ∈ N (z), and returns "false." ✷ Lemma 3.1 implies that, while running Algorithm PEO(G ′ v , σ), it suffices to collect in the set X (Step 4) only the common neighbors of u and v; in turn, Lemma 3.2 implies that it suffices to execute the for-loop of Steps 2-8 only for the non-neighbors of v.

Additionally, since neither the graph G nor the ordering σ changes during the execution of the Algorithm PEO, then, for each vertex u of G, we can precompute the corresponding vertex w (see Step 6). In fact, in light of Lemma 3.2, we can precompute an array [u] is equal to the leftmost among the neighbors of u that are to the right of u (with respect to a DegMN-ordering σ v of the non-neighbors

N ext N eighbor G ′ [M (v)],σv [ ], such that for each vertex u ∈ M (v), the entry N ext N eighbor G ′ [M (v)],σv
M (v) of v in G) in the chordal completion G ′ [M (v)] of the subgraph G[M (v)].
Note that a vertex u ∈ M (v) need not have any neighbors among the vertices that follow it in σ v ; in such a case, the entry N ext N eighbor G ′ [M (v)],σv [u] does not get assigned a value, yet, since the for-loop (Steps 2-8) of Algorithm PEO will only be executed for the non-neighbors of v because of Lemma 3.2, we do not need to update any set A( ).

Based on the above, we obtain the Algorithm Not-in-HHB, presented in Figure 3, which takes as input a graph G and a vertex v of G, and returns "true" if and only if the vertex v does not belong to a hole, and it is not the top of a house or a building in G. The correctness of Algorithm Not-in-HHB is established in the following theorem. for each non-neighbor u of v do

A(u) ← ∅; 2. for i ← 1 to k do 3. u ← σ v (i); 4. X ← N (u) ∩ N (v); {note: ∀x ∈ X, u precedes x in the ordering σ v } 5. if X = ∅ and the entry N ext N eighbor G ′ [M (v)],σv [u] has been assigned a value 6. then w ← N ext N eighbor G ′ [M (v)],σv [u]; {note: w ∈ M (v)} 7. concatenate X to A(w); {note: w / ∈ X} 8. if A(u) -N (u) = ∅ then return("false");
9. return("true"); Fig. 3: The algorithm for determining whether a vertex v belongs to a hole or is the top of a house or a building.

Proof: (=⇒) Suppose that the algorithm returns "false" while processing vertex z ∈ M (v) (i.e, when i = σ -1 v (z)). This happens only if at Step 8 of the current iteration of the for-loop there exists a vertex x ∈ A(z) -N (z). Then, from Lemma 3.2, we have that A(z) -N (z) ⊆ N (v), which implies that x ∈ N (v) and xz / ∈ E(G). The vertex x was added to A(z) at Step 7 of a prior iteration, say, while processing vertex y; thus, xy ∈ E(G) and z = N ext N eighbor G ′ [M (v)],σv [y] which implies that σ -1 v (y) < σ -1 v (z) (and thus y ∈ M (v)), and yz ∈ E(G ′ [M (v)]). As in the proof of Lemma 3.2, we can show that there exists a vertex x ′ of G such that x ′ ∈ N (v), x ′ z ∈ E(G), and x ′ y / ∈ E(G) (see Figure 4(a), where the dotted edge indicates a potential edge of G). For the vertices y, z (which are adjacent in G ′ [M (v)]), we distinguish two cases:

yz ∈ E(G). Then, if xx ′ / ∈ E(G)
, the vertex set {v, x, y, z, x ′ } induces a hole (in fact, a C 5 ), otherwise it induces a house with vertex v at the top.

yz / ∈ E(G). Then, because z = N ext N eighbor G ′ [M (v)]
,σv [y] (i.e., the vertices y, z are adjacent in the chordal completion G ′ [M (v)]), Lemma 2 of [START_REF] Hoàng | Finding houses and holes in graphs[END_REF] implies that the graph G has an induced path on at least three vertices connecting y and z all of whose vertices are in M (v) and such that for each vertex w of the path other than y, z, it holds that

N (w) ∩ N (v) ⊆ N (y) ∩ N (v). Let a 1 a 2 • • • a q
be a chordless such path where a 1 = y, a q = z, and q ≥ 3; then, a i ∈ M (v) and N (a i ) ∩ N (v) ⊆ N (y) ∩ N (v), for all 1 < i < q (see Figure 4(b), where the dashed edge indicates an edge in

E(G ′ [M (v)]) -E(G)). Since x ′ / ∈ N (y), this implies that x ′ / ∈ N (a i ) for all i = 1, 2, . . . , q -1. v x x y z N(v) M(v) ' v x x y z N(v) M(v) ' (a) (b)
Fig. 4::

Let p = max{i | x ∈ N (a i )};
p is well defined since x ∈ N (a 1 ), and p < q since x / ∈ N (a q ) -recall that a 1 = y, a q = z, xy ∈ E(G), and xz / ∈ E(G). Then, the vertices a p+1 , . . . , a q-1 are not adjacent to x or x ′ , so that if xx ′ / ∈ E(G), the vertices v, x, a p , . . . , a q-1 , z, x ′ induce a hole in G, whereas if xx ′ ∈ E(G) they induce a house or a building with v at its top.

In both cases, the vertex v belongs to a hole or is the top of a house or a building in the graph G.

(⇐=) Suppose that the vertex v belongs to a hole or is the top of a house or a building in G. If v belongs to a C 5 or is the top of a house, let v, x, y, z, x ′ be the vertices inducing the C 5 or house (x, x ′ ∈ N (v), y, z ∈ M (v), xy ∈ E(G), and x ′ z ∈ E(G)); if v belongs to a hole on more than 5 vertices or is the top of a building, we consider such a hole or building on the fewest vertices, and let them be v, x, y, a 1 , . . . , a p , z, x ′ (x, x ′ ∈ N (v), y, a 1 , . . . , a p , z ∈ M (v), xy ∈ E(G), and x ′ z ∈ E(G)). Moreover, suppose without loss of generality that in either case σ -1 v (y) < σ -1 v (z). In case v belongs to a hole on ≥ 6 vertices or is the top of a building, we can show that all the a i s precede both y and z in the ordering σ v : if any a i appears between y and z, then the definition of the DegMN-ordering σ v implies that there exists vertex x ′′ ∈ N (v) such that x ′′ ∈ N (a i ) -N (y) (recall that xy ∈ E(G) and xa i / ∈ E(G)); then the vertices v, x, y, a 1 , . . . , a i , x ′′ induce a hole or a building on fewer vertices. Then, this property of the a i s and Lemma 3.3 imply that yz ∈ E(G ′ [M (v)]).

From the above, we conclude that, in any case, the vertices y, z are adjacent in G ′ [M (v)]; then, we show that there exists a sequence y=b 1 , b 2 , . . . , b q =z of non-neighbors of v in G such that b

i = N ext N eighbor G ′ [M (v)],σv [b i-1 ] for 2 ≤ i ≤ q (note that b i = N ext N eighbor G ′ [M (v)],σv [b i-1 ] im- plies that σ -1 v (b i-1 ) < σ -1 v (b i ) and b i-1 b i ∈ E(G ′ [M (v)])).
The existence of such a sequence is shown as follows

: if z = N ext N eighbor G ′ [M (v)],σv [y], then the sequence is precisely y, z; otherwise, if b 2 = N ext N eighbor G ′ [M (v)],σv [y], then yb 2 ∈ E(G ′ [M (v)]) which from the fact that yz ∈ E(G ′ [M (v)]) and from the definition of G ′ [M (v)] implies that b 2 z ∈ E(G ′ [M (v)])
; next, we repeat the above argument for b 2 in the place of y, and so on so forth; since there is a finite number of vertices between y and z in σ v , eventually, we will find a vertex b q-1 such that z if Algorithm Not-in-HHB(G, v) returns "false" then return("the graph is not HH-free"); {G contains a house or a hole} 2. return("the graph is HH-free");

= N ext N eighbor G ′ [M (v)],σv [b q-1 ]. Let r = max{i | x ∈ N (b i )};
Fig. 5: The algorithm for determining whether a graph G is HH-free.

x / ∈ N (b r+1 ), if not earlier. ✷

In light of Theorem 3.1 and by observing that a building contains a hole, we obtain the very simple HH-free graph recognition algorithm that is given in Figure 5.

Computation of the values of Next Neighbor

G ′ [S],σ [ ].
Let G be a graph, S a subset of the vertex set of G, σ an ordering of the vertices in S, and let G ′ [S] be the chordal completion of the subgraph G[S] with respect to σ. For each vertex x ∈ S, we want to determine the leftmost among the neighbors of x that are to the right of x (w.r.t. σ) in G ′ [S]. In order to avoid computing the graph G ′ [S], we take advantage of the following property of the chordal completion:

Lemma 3.3 Let G be a graph, let (v 1 , v 2 , . . . , v k
) be an ordering of a vertex set S ⊆ V (G), and let G ′ be the graph resulting from the subgraph G[S] after we had applied chordal completion on it with respect to the ordering of the vertices in S (i.e., after having added edges so that, for all i = 1, 2, . . . , k, vertex v i is simplicial in the subgraph induced by the vertices v i , v i+1 , . . . , v k ). Then, the graph G ′ contains the edge v r v j , where r < j, if and only if there exists an edge v i v j in G such that i ≤ r and the vertices v i , v r belong to the same connected component of the subgraph of G induced by the vertices v 1 , v 2 , . . . , v i , . . . , v r .

Proof: (=⇒) Suppose that v r v j ∈ E(G ′ ). We will show the following:

Proposition. If v r v j ∈ E(G ′ )
, then there exists a vertex v i , where i ≤ r, such that v i v j is an edge of G and the vertices v i , v r belong to the same connected component of the subgraph G[{v 1 , v 2 , . . . , v i , . . . , v r }].

We use induction on r.

Basis: r = 1. Then, since v 1 v j ∈ E(G ′ ), it can only be that v 1 v j ∈ E(G)
and the proposition holds with v i being v 1 .

Inductive hypothesis: Suppose that the proposition holds for all r < r, where r ≥ 2.

Inductive step: We show that the proposition holds for r = r.

Hence, suppose that v r v j ∈ E(G ′ ). If v r v j is an edge of G, then the proposition clearly holds with v i being v r . Otherwise, the edge v r v j must have been added while making a vertex v t simplicial; then, t < r < j and v t v r , v t v j ∈ E(G ′ ). Since v t v r ∈ E(G ′ ) and t < r, then by the inductive hypothesis, there exists a vertex v p , where p ≤ t < r, such that v p v r is an edge of G and v p , v t belong to the same connected component of G[{v 1 , v 2 , . . . , v t }]. Similarly, by the inductive hypothesis for the edge v t v j of G ′ , there exists a vertex v q , where q ≤ t < j, such that v q v j is an edge of G and v q , v t belong to the same connected component of G[{v 1 , v 2 , . . . , v t }]. Therefore, the vertices v p , v q belong to the same connected component of G[{v 1 , v 2 , . . . , v t }]. Then, the existence of the edge v p v r in G and the fact that p ≤ t < r imply that v p , v r belong to the same connected component of G[{v 1 , v 2 , . . . , v r }]; moreover, since v p v j is an edge of G and p ≤ t < r < j, the proposition holds with v i being v p .

The induction then implies that the proposition holds for all edges v r v j ∈ E(G ′ ), where r < j.

(⇐=) Suppose now that for vertices v r , v j of G, where r < j, there exists a vertex v i , where i ≤ r, such that v i v j is an edge of G and the vertices v i , v r belong to the same connected component of the subgraph

G[{v 1 , v 2 , . . . , v r }]. We will show that v r v j ∈ E(G ′ ). If v r v j ∈ E(G), then clearly v r v j ∈ E(G ′ ). Suppose now that v r v j / ∈ E(G). Since the vertices v i , v r be- long to the same connected component of G[{v 1 , v 2 , . . . , v r }], there exists a simple path v r v p1 v p2 • • • v p ℓ v i from v r to v i in G[{v 1 , v 2 , . . . , v r }]; then, clearly, p t < r for all t = 1, 2, . . . , ℓ. Since v i v j is an edge of G, then v r v p1 v p2 • • • v p ℓ v i v j is a simple path from v r to v j in G,
and hence in G ′ . For ease of notation, let us set

v p0 = v r , v p ℓ+1 = v i , and v p ℓ+2 = v j , so that the path from v r to v j becomes v p0 v p1 v p2 • • • v p ℓ+1 v p ℓ+2 .
Let p s be the minimum among p 1 , p 2 , . . . p ℓ+1 , i.e., v ps is the leftmost (with respect to σ) vertex among v p1 , v p2 , . . . v p ℓ+1 ; then, since for all t = 1, 2, . . . , ℓ + 1 it holds that p t < r < j, we have that p s < p s-1 and p s < p s+1 . The definition of the graph

G ′ implies that v ps is simplicial in G ′ [{v ps , v ps+1 , . . . , v k }]; since v ps is adjacent in G ′ to v ps-1 and to v ps+1 , G ′ contains the edge v ps-1 v ps+1 . Thus, v p0 v p1 • • • v ps-1 v ps+1 • • • v p ℓ+2 is a simple path in G ′ from v r to v j , i.e.
, we obtained a path in G ′ from v r to v j where the leftmost vertex v ps has been removed. The process of removing the leftmost (w.r.t. σ) vertex among the vertices of the path can be repeated over and over, and in each case we obtain a shorter simple path in G ′ from v r to v j . Since p t < r < j for all t = 1, 2, . . . , ℓ + 1, eventually all the vertices v p1 , v p2 , . . . , v p ℓ+1 will be removed and we will have that v p0 v p ℓ+2 = v r v j is a path (= edge) in G ′ , as desired. ✷

We note that the above lemma implies Lemma 2 of [START_REF] Hoàng | Finding houses and holes in graphs[END_REF] as a corollary. Lemma 3.3 implies that for the computation of the value

N ext N eighbor G ′ [S],σ [v r ], where σ = (v 1 , v 2 , . . . , v k ), it suffices to find the leftmost (w.r.t. σ) vertex among v r+1 , v r+2 , . . . , v k which is adjacent in G to a vertex in the connected component of G[{v 1 , v 2 , . . . , v r }]
to which v r belongs. This can be efficiently done by processing the vertices v 1 , v 2 , . . . , v k in order from v 1 to v k . In detail, the algorithm to compute the contents of the array

N ext N eighbor G ′ [S],σ [ ] is presented in Figure 6; note that if a vertex v i ∈ S has no neighbors in G ′ [{v i , . . . , v k }], then the entry N ext N eighbor G ′ [S],σ [v i ] is not assigned a value.
It is important to observe the following:

Observation 3.1 At the completion of the processing of vertex v j in Algorithm Compute-Next Neighbor, the sets of vertices maintained by the algorithm are in a bijection with the connected components of

G[{v 1 , v 2 , . . . , v j }];
The observation follows from the fact that while processing v j , we consider the edges v i v j where i < j, and we union the set containing v j (which has vertex v j as its rightmost vertex with respect to σ) to another set iff v j is adjacent to a vertex in that set. The correctness of Algorithm Compute-Next Neighbor is established in the following lemma. processing vertex v s , v i indeed is the rightmost (w.r.t. σ) vertex in the set to which it belongs, and thus the entry N ext N eighbor G ′ [S],σ [v i ] will be assigned a value (it will be set equal to v s during the processing of vertex v s ). The proof will be complete if we show that, whenever the Algorithm Compute-Next Neighbor assigns a value to an entry N ext N eighbor G ′ [S],σ [v r ], it assigns the correct value. Observe that whenever the algorithm executes an assignment N ext N eighbor G ′ [S],σ [v r ] ← v j , then r < j and there exists an edge v i v j in G such that i < j and the vertices v i , v j belong to the same connected component of the subgraph

G[{v 1 , v 2 , . . . , v r }]. Then, Lemma 3.3 implies that the chordal completion G ′ [S] of the subgraph G[S]
of G induced by the elements of S contains the edge v r v j . We need to show that v r is not adjacent in the chordal completion of G[S] to any vertex v t , where r < t < j. Suppose for contradiction that there existed such a vertex v t . Then, by Lemma 3.3, there exists a vertex v s such that s < r, v s v t ∈ E(G), and v s , v r belong to the same connected component of G[{v 1 , v 2 , . . . , v r }]. But then, while processing the vertex v t , v t will be included in the set containing v r , in contradiction to the fact that, while processing v j (which is done after processing v t since t < j), the rightmost (w.r.t. σ) vertex in the set containing v r is precisely v r ; recall that r < t. Therefore, all the assignments to the entries of the array N ext N eighbor G ′ [S],σ [ ] are correct. ✷ Time and Space Complexity. Let m be the number of edges of the graph G; recall also that |S| = k.

If we ignore the operations to process sets (i.e., make a set, union sets, or find the rightmost (w.r.t. σ) vertex in a set) while running Algorithm Compute-Next Neighbor(G, S, σ), then the rest of the execution of the algorithm takes O(k + m) time. The sets are maintained by our algorithm in a fashion amenable for Union-Find operations, where additionally the representative of each set also carries a link to the node storing the rightmost (w.r.t. σ) vertex in the set. Then,

• making a set which contains a single vertex v i requires building the set and setting the rightmost (w.r.t. σ) vertex in the set to v i ;

• finding the rightmost (w.r.t. σ) vertex in the set, say, A, to which a vertex v j belongs, requires performing a Find operation to locate the representative of the set A, from which the rightmost vertex is obtained in constant time;

• unioning two sets requires constructing a single set out of the elements of the two sets, and updating the rightmost (w.r.t. σ) vertex information; since we always union a set with the set containing v j , where v j is the rightmost vertex in any of the sets, then the rightmost vertex of the resulting set is v j , and this assignment can be done in constant time per union.

As the Algorithm Compute-Next Neighbor creates one set for each one of the vertices v 1 , v 2 , . . . , v k , it executes k make-set operations; this also implies that the number of union operations is less than k. The number of times to find the rightmost (w.r.t. σ) vertex in a set is O(m), since the algorithm executes one such operation for each edge of the subgraph G[S]. The sets may be represented as disjoint-set forests, in which case, the time to execute p make-set, find, and union operations involving q elements is O(p α(p, q)) [START_REF] Tarjan | Data structures and network algorithms[END_REF], where α( , ) denotes the very slowly growing functional inverse of Ackerman's function; since Algorithm Compute-Next Neighbor performs p operations, where k ≤ p = O(k + m), on k elements, and the function α(p, q) decreases as the ratio p/q increases, the use of disjoint-set forests implies a time complexity of O(m α(k, k)). Alternatively, the sets may be represented by linked lists, and the time to execute p make-set, find, and union operations involving q elements is O(p+q log q) [START_REF] Cormen | Introduction to Algorithms[END_REF]; thus, in this case, the time complexity is O(m + k log k). In either case, the space required (in addition to the space needed to store the graph G) is O(k). The Algorithm Recognize-HH-free consists of applying the Algorithm Non-in-HHB on every vertex of the input graph G. If G is connected, then n = O(m) and processing all the vertices of G takes O( v min{m α(n, n), m + n log n}) time and O(n + m) space. If G is not connected, then we compute its connected components [START_REF] Cormen | Introduction to Algorithms[END_REF] and work on each of them separately (note that a hole and a house are both connected); clearly, the subgraph of G induced by each such component is connected and has O(n) vertices and O(m) edges. Then, the computation of the components and the processing of all the vertices of G takes O(n + m + v min{m α(n, n), m + n log n}) total time and O(n + m) space. Summarizing, we obtain the following corollary: Corollary 3.1 Algorithm Recognize-HH-free determines whether a graph G on n vertices and m edges contains a hole or a house (i.e., is not HH-free) in O(n min{m α(n, n), m+n log n}) time and O(n+m) space.

Providing a Certificate

The Algorithm Recognize-HH-free can be made to provide a certificate (a hole or a house) whenever it decides that the input graph G is not HH-free. In particular, we augment the Algorithm Not-in-HHB(G, v) (5) as follows:

• When processing vertex u, we add a reference to u to each element of the set X formed in Step 4, so that for each vertex w, each element of the set A(w) carries a reference to the vertex during whose processing this element was added to A(w) (see Step 7).

Our approach follows the proof of Theorem 3.1. The Algorithm Recognize-HH-free answers that the graph G is not HH-free when a call to Algorithm Not-in-HHB(G, v) for a vertex v returns "false," i.e., when in Step 8 the difference A(u)-N (u) is non-empty for a non-neighbor u of v in G. Let x ∈ N (v) be an element in A(u) -N (u); the vertex x is associated with a vertex y ∈ M (v) during whose processing vertex x was added to A(u) (then, clearly, u = N ext N eighbor G ′ [M (v)],σv [y]). (ii) . Then, we can obtain a hole or a house of G by doing the following:

1. We traverse the neighbors of vertex u and find a vertex x ′ which is adjacent to v and not adjacent to y; such a vertex always exists since n(v, y) ≤ n(v, u) (note that y precedes u in the DegMNordering σ v ) and x ∈ N (y) ∩ N (v) whereas x / ∈ N (u) ∩ N (v).

2. We consider the subgraph of G induced by u, y and the vertices preceding y in σ v , and we apply BFS on it starting at y until u is reached (note that u will be eventually reached, because u = N ext N eighbor G ′ [M (v)],σv [y], and thus y and u belong to the same connected component of the subgraph of G induced by u, y and the vertices preceding u in σ v ; see Lemma 3.3); let a 1 a 2 • • • a q , where a 1 = y and a q = u, be the path in the BFS-tree from y to u, which is thus chordless. Moreover, {a 1 , a 2 , . . . , a q-1 } ∩ N (x ′ ) = ∅ (otherwise, the algorithm would have exited while processing a vertex preceding u; see proof of Theorem 3.1).

We compute

p = max{ i | x ∈ N (a i ) }. Then, if xx ′ / ∈ E(G), the vertices v, x, a p , . . . , a q-1 , u, x ′ induce a hole in G; if xx ′ ∈ E(G), the vertices v, x, a p , u, x ′ induce a house in G if p = q -1, whereas if p ≤ q -2, the vertices x, a p , . . . , a q-1 , u, x ′ induce a hole.
The correctness of the computation follows from the proof of Theorem 3.1. Regarding the time and space complexity, we first note that the augmentation of the Algorithm Not-in-HHB does not asymptotically increase the time and space complexity of the Algorithm Recognize-HH-free. In turn, if we assume that we have an adjacency-list representation of the input graph G and that we use two auxiliary arrays (of size n) to mark the neighbors of v and of y, it is not difficult to see that all three steps of the certificate computation take O(n + m) time and O(n) space, where n, m are the numbers of vertices and edges of G, respectively. Therefore, we have: Theorem 3.3 The Algorithm Recognize-HH-free can be easily augmented to provide a certificate whenever it decides that the input graph G is not HH-free; if G has n vertices and m edges, the certificate computation takes O(n + m) time and O(n) space.

Recognition of HHD-free and WPO-Graphs

In this section, we present two applications of the ideas and of the algorithm for recognizing HH-free graphs. In particular, we show how to use the HH-free graph recognition algorithm in order to recognize HHD-free graphs within the same time and space complexity, and how the ideas can be used to determine if the complement of a given graph is HH-free so that we can recognize WPO-graphs.

(ii) It must be noted that vertex x may have been added in A(u) more than once by different vertices; yet, x and any of these vertices suffice for our purposes. pointers for every edge ab connecting the record storing b in the adjacency list of a to the record storing a in the adjacency list of b and back, then obtaining G[{v i+1 , v i+2 , . . . , v n }] from G[{v i , v i+1 , . . . , v n }] takes time proportional to the degree of v i in G[{v i , v i+1 , . . . , v n }] and hence O(deg(v i )) time, where deg(v i ) denotes the degree of vertex v i in G. Additionally, in order to check whether a vertex is semisimplicial, we take advantage of the following result of Hoàng and Khouzam (which was also used in [START_REF] Hoàng | Finding houses and holes in graphs[END_REF]):

Welsh-Powell Opposition Graphs

Our algorithm for recognizing WPO-graphs relies on the fact that a graph G is a WPO-graph if and only if G is HHP-free and its complement G is HH-free, which follows from the following characterization due to Olariu and Randall [START_REF] Olariu | Welsh-Powell opposition graphs[END_REF]: Theorem 4.4 (Olariu and Randall [START_REF] Olariu | Welsh-Powell opposition graphs[END_REF]) A graph G is a WPO-graph if and only if G contains no induced C 5 , P 5 , house, or "P".

Eschen et al. [START_REF] Eschen | Recognition of some perfectly orderable graph classes[END_REF] described an O(n m)-time algorithm for recognizing whether a graph G on n vertices and m edges is HHP-free by using the modular decomposition tree of G and Theorem 4.2 due to Hoàng and Khouzam [START_REF] Hoàng | On brittle graphs[END_REF]. We next show that we can detect whether the complement G of G contains a hole or a house in O(n m) time. Combining these two algorithms, we get an O(n m)-time algorithm for recognizing WPO-graphs.

The obvious approach of running Algorithm Recognize-HH-free on the complement G of G, in order to check whether G contains a hole or a house, proves to be expensive. Thus, instead, we process the vertices of G in turn; for each vertex v, we consider a (different) auxiliary graph G v as follows:

• V ( G v ) = V (G) • E( G v ) = { vy | y ∈ M (v) } ∪ { xy | x ∈ N (v

Fig. 2 :

 2 Fig. 2: The perfect elimination ordering testing algorithm.

Theorem 3 . 1

 31 Algorithm Not-in-HHB(G, v) returns "false" if and only if the vertex v belongs to a hole or is the top of a house or a building in G. Algorithm Not-in-HHB(G, v) 1. Compute a DegMN-ordering σ v = (y 1 , y 2 , . . . , y k ) of the non-neighbors of v in the graph G; compute the array N ext N eighbor G ′ [M (v)],σv [ ] for the chordal completion G ′ [M (v)] of the subgraph G[M (v)] with respect to the ordering σ v ;

  r is well defined since x ∈ N (b 1 ), and r < q since x / ∈ N (b q )recall that b 1 = y and xy ∈ E(G), and b q = z and xz /∈ E(G). Since x ∈ N (b r ) and b r+1 = N ext N eighbor G ′ [M (v)],σv [b r ],the processing of vertex b r will result in the addition of vertex x in the set A(b r+1 ); then, the Algorithm Not-in-HHB will return "false" when it processes vertex b r+1 , because Algorithm Recognize-HH-free 1. for each vertex v of the input graph G do

Lemma 3 . 5

 35 Thus, the computation of the values of the array N ext N eighbor G ′ [S],σ [ ] for the k elements of the set S takes a total of O(min{(k + m) α(k, k), m + k log k}) time and O(k) space. Therefore, we have: Let G be a graph on m edges, S a subset of vertices of G, and σ an ordering of the elements of S. Algorithm Compute-Next Neighbor(G, S, σ) correctly computes the values of the entries of the array N ext N eighbor G ′ [S],σ [ ] in O(min{(k + m) α(k, k), m + k log k}) time and O(k) space, where k is the cardinality of the set S.

3. 2 Theorem 3 . 2

 232 Complexity of the Algorithm Recognize-HH-freeLet us assume that the graph G has n vertices and m edges and that vertex v of G has k non-neighbors in G. It is not difficult to see that the execution of the Algorithm Not-in-HHB(G, v) for vertex v takes O(n + m) time and space plus the time and space needed for the computation of the entries of the arrayN ext N eighbor G ′ [M (v)],σv [ ].For the latter computation, we run Algorithm Compute-Next Neighbor on G, M (v), and σ v , which takes O(min{(k+m) α(k, k), m+k log k}) = O(min{(n+m) α(n, n), m+ n log n}) time and O(k) = O(n) space (Lemma 3.5); note that the function α(i, i) increases as i increases (see definition in[START_REF] Tarjan | Data structures and network algorithms[END_REF]). Therefore, Algorithm Not-in-HHB(G, v) takes O(n+ m + min{(n + m) α(n, n), m + n log n}) = O(min{(n + m) α(n, n), m + n logn}) and O(n + m) space. Hence, we have: Let G be a graph on n vertices and m edges. Algorithm Not-in-HHB determines whether a vertex v of G belongs to a hole or is the top of a house or a building in O(min{(n + m) α(n, n), m + n log n}) time and O(n + m) space.

Theorem 4 . 2 (

 42 Hoàng and Khouzam [8]) Let G be a graph and x be a semi-simplicial vertex of G. If x is not simplicial, then each big co-component of the subgraph G[N (x)] is a module of G.(A connected component or co-component of a graph is called big if it has at least two vertices; we also note that if a vertex x is simplicial then none of the co-components of the subgraph G[N (x)] is big.) Since computing the subgraph induced by the neighbors of vertex v i in G[{v i , v i+1 , . . . , v n }], computing its cocomponents, and testing whether a vertex set is a module in G[{v i , v i+1 , . . . , v n }] can all be done in time and space linear in the size ofG[{v i , v i+1 , . . . , v n }], step 3 takes a total of O i n + m + deg(v i ) = O(n m) time and O(n + m) space. Finally, step 4 takes constant time. Therefore, we obtain the following theorem. Theorem 4.3 Let G be an undirected graph on n vertices and m edges. Then, Algorithm Recognize-HHD-free determines whether G is an HHD-free graph in O(n min{m α(n, n), m + n log n}) time and O(n + m) space.

  ), y ∈ M (v), and xy / ∈ E(G) } ∪ { xx ′ | x, x ′ ∈ N (v) and xx ′ / ∈ E(G) }

Concluding Remarks

We have presented recognition algorithms for the classes of HH-free and HHD-free graphs running in O(n min{m α(n, n), m + n log n}) time, and for WPO-graphs running in O(n m) time, where n is the number of vertices and m is the number of edges of the input graph. Our proposed algorithms are simple and require O(n+m) and O(n 2 ) space, respectively. Moreover, our HH-free graph recognition algorithm can be easily augmented to yield a certificate (a hole or a house) whenever it decides that the input graph is not HH-free.

We leave as an open problem the designing of O(n m)-time algorithms for recognizing HH-free and HHD-free graphs; note that an O(n m)-time algorithm for recognizing HH-free graphs directly implies an O(n m)-time recognition algorithm for HHD-free graphs. Additionally, in light of the O(n m)-time recognition of P 4 -comparability, P 4 -simplicial, bipolarizable, and WPO-graphs, it would be worth investigating whether the recognition of brittle and semi-simplicial graphs is inherently more difficult.

Algorithm Compute-Next Neighbor(G, S, σ)

1. {let σ = (v 1 , v 2 , . . . , v k ) be the given ordering of the vertices in S} make a set containing the vertex v 1 ;

2.

for j = 2, 3, . . . , k do 3. make a set containing the vertex v j ;

4.

for each edge v i v j of G, where i < j, do

5.

v r ← the rightmost (w.r.t. σ) vertex in the set to which v i belongs;

then {v i and v j belong to different sets}

9. union the sets to which v i and v j belong; Proof: First, we show that, for a vertex v r ∈ S, the Algorithm Compute-Next Neighbor assigns a value to the entry

] is assigned a value if, during the processing of a vertex v j , where j > r, there exists an edge in G connecting v j to a vertex v i , and v r is the rightmost (w.r.t. σ) vertex among the vertices in the set containing v i (Step 5 of Algorithm Compute-Next Neighbor). Since the vertices v i and v r belong to the same set, which corresponds to the same connected component of the subgraph G[{v 1 , v 2 , . . . , v j-1 }] (Observation 3.1), and since v r is the rightmost vertex in the set, then v i , v r belong to the same connected component of G[{v 1 , v 2 , . . . , v r }]. Due to this and due to the fact that v r v j ∈ E(G), where r < j, Lemma 3.3 implies that the chordal completion G ′ [S] of the subgraph G[S] of G induced by the elements of S contains the edge v r v j .

Suppose now that a vertex v i is adjacent in G ′ [S] to a vertex in {v i+1 , v i+2 , . . . , v k }; we show that the Algorithm Compute-Next Neighbor assigns a value to the entry

to which v i belongs. We show that right before processing v s , the rightmost (w.r.t. σ) vertex in the set to which v i belongs is precisely v i . Suppose for contradiction that this is not the case and let v s ′ be the rightmost vertex, where s ′ > i. Then, there exists a simple path in

a path in G and p t ≤ i for all t = 0, 1, . . . , t -1, the vertices v p t-1 and v i belong to the same connected component of G[{v 1 , v 2 , . . . , v i }]; however, these facts come to a contradiction with the definition of v s , because i < p t < s. Therefore, right before Algorithm Recognize-HHD-free 1. if the input graph G is not HH-free then return("the graph is not HHD-free");

2. Run LexBFS on G starting at an arbitrary vertex w, and let (v 1 , v 2 , . . . , v n ) be the resulting ordering, where v n = w.

then return("the graph is not HHD-free");

4. return("the graph is HHD-free").

Fig. 7: The algorithm for determining whether a graph G is HHD-free.

HHD-free Graphs

Our HHD-free graph recognition algorithm is motivated by the corresponding algorithm of Hoàng and Sritharan [START_REF] Hoàng | Finding houses and holes in graphs[END_REF], which in turn is motivated by the work of Hoàng and Khouzam [START_REF] Hoàng | On brittle graphs[END_REF] and relies on the following characterization of HHD-free graphs proved by Jamison and Olariu:

Theorem 4.1 (Jamison and Olariu [START_REF] Jamison | On the semi-perfect elimination[END_REF]) The following two statements are equivalent:

(i) The graph G is HHD-free;

(ii) For every induced subgraph H of the graph G, every ordering of vertices of H produced by LexBFS is a semi-perfect elimination.

In fact, we could use the Algorithm Not-in-HHB(G, v) in Hoàng and Sritharan's HHD-free graph recognition algorithm in order to determine if vertex v is high, and we would achieve the improved time and space complexities stated in this paper. However, we can get the much simpler algorithm which we give in Figure 7. Note that, after step 1, we need only check whether the input graph G contains a domino; this is why, we only process the n -5 vertices v 1 , v 2 , . . . , v n-5 in step 3. Additionally, it is important to observe that, for all i = 1, 2, . . . , n, the ordering (v i , v i+1 , . . . , v n ) is an ordering which can be produced by running LexBFS on the subgraph G[{v i , v i+1 , . . . , v n }] starting at vertex v n . The correctness of the algorithm follows from Theorem 4.1 and the fact that if the currently processed vertex v i in step 3 is semi-simplicial then clearly it cannot participate in a domino (note that none of the vertices of a domino is semi-simplicial in any graph containing the domino as induced subgraph).

by removing vertex v i and all its incident edges; if the graph G is stored using a (doubly-connected) adjacency-list representation with Note that in G the neighbors of v are the non-neighbors M (v) of v in G, and its non-neighbors are the neighbors N (v) of v in G. Thus, the graph G v is precisely G without any edges between neighbors of v. This implies that:

(i) v cannot be the top of a house or a building in G v , and (ii) if v is the top of a house or a building in G, then it belongs to a hole in G v .

Then, in order to check whether vertex v belongs to a hole or is the top of a house or a building in G, it suffices to execute Algorithm Not-in-HHB( G v , v), and answer "true" if and only if Algorithm Not-in-HHB( G v , v) returns "false." Thus, we have the following result. Proof: It suffices to establish the theorem for a connected graph G. If G is not connected, then, because the complement of a house and the complement of a hole are both connected, we work with the connected components of G, which can be computed in O(n + m) time and space [START_REF] Cormen | Introduction to Algorithms[END_REF]. Thus, suppose that G is connected; then, n = O(m). In order to facilitate the construction of the auxiliary graphs, we compute and store the adjacency matrix of G, which takes O(n 2 ) time and space. Then, for any vertex v of G, the graph G v has n vertices and O(n


Andreas Brandstädt

Tilo Klembt

Suhail

Suhail Mahfud

P 6 -and Triangle-Free Graphs Revisited: Structure and Bounded Clique-Width

Keywords: Maximum Weight Stable Set Problem, clique-width of graphs, efficient graph algorithms

P6-and triangle-free graphs revisited: structure and bounded clique-width

Introduction

Basic problems on graphs such as Vertex Cover and Maximum Weight Stable Set (MWS) which are NPcomplete in general can be solved efficiently for various graph classes. Thus, for example, the problems Vertex Cover and MWS are NP-complete even for triangle-free graphs [START_REF] Poljak | A note on stable sets and colorings of graphs[END_REF] but can be solved in polynomial time for bipartite graphs. Mosca [START_REF] Mosca | Stable sets in certain P 6 -free graphs[END_REF] has shown that MWS can be solved in time O(n 4.5 ) for any P 6 -and triangle-free graph. Let P k denote the induced path of k vertices and let S i,j,k denote the tree with exactly one vertex r of degree 3 and three leaves which have distance i, j, k from r, respectively.

In this paper, we give a complete structure analysis of P 6 -and triangle-free graphs by showing that such graphs which are not bipartite but prime in the sense of modular decomposition have simple structure which implies bounded clique-width for these graph classes. This leads to the following improvements over previous results:

• it improves the time bound of the MWS algorithm in [START_REF] Mosca | Stable sets in certain P 6 -free graphs[END_REF] from O(n 4.5 ) to O(n 2 ) by using the clique-width approach;

1365-8050 c 2006 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

• it leads to more efficient algorithms not only for the MWS problem but also for problems such as Maximum Clique, Minimum Dominating Set, Steiner Tree, and Maximum Induced Matching and in general for all problems expressible in terms of Monadic Second Order Logic with quantification only over vertex predicates -see [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique width[END_REF] -based on a so-called k-expression of the input graph;

• it extends the previous result by Fouquet, Giakoumakis and Vanherpe [START_REF] Fouquet | Bipartite graphs totally decomposable by canonical decomposition[END_REF] on bounded clique-width from bipartite P 6 -free graphs to (P 6 ,K 3 )-free graphs;

• it extends efficient algorithms to larger classes: the input graph is not necessarily assumed to be (P 6 ,K 3 )-free. Our algorithm for constructing a k-expression of the input graph either results in such an expression or proves that the input graph contains a P 6 or K 3 . This approach is called robust in [START_REF] Spinrad | Efficient Graph Representations[END_REF].

Remark. There is great and constant interest in triangle-free graphs and in particular, P 6 -and trianglefree graphs and variants; many papers are dealing with such graphs. Some examples are:

1. Prömel, Schickinger and Steger [START_REF] Prömel | A note on triangle-free and bipartite graphs[END_REF] have shown that with "high probability", a triangle-free graph can be made bipartite by removing a single vertex (which extends the famous result by Erdös, Kleitman and Rothschild saying that almost all triangle-free graphs are bipartite).

2. Liu and Zhou [START_REF] Liu | Dominating subgraphs in graphs with some forbidden structure[END_REF] showed that a triangle-free graph G is P 6 -free if and only if every connected induced subgraph of G has a dominating complete bipartite subgraph or a dominating C 6 .

3. Brandt [START_REF] Brandt | Triangle-free graphs and forbidden subgraphs[END_REF] also studied the structure of P 6 -and triangle-free graphs but neither the results of Liu and Zhou nor the results of Brandt lead to a complete structure analysis and bounded clique-width for this graph class.

4. Sumner [START_REF] Sumner | Subtrees of a graph and chromatic number[END_REF] proved that P 6 -, C 6 -and triangle-free graphs are 3-colorable. This result was extended by Randerath, Schiermeyer and Tewes [START_REF] Randerath | Three-colourability and forbidden subgraphs. II: polynomial algorithms[END_REF] to 4-colorability of P 6 -and triangle-free graphs and a polynomial time algorithm for 3-colorability on P 6 -free graphs.

5.

In [START_REF] Lozin | Bipartite graphs without a skew star[END_REF], Lozin shows that bipartite S 1,2,3 -free graphs (an extension of P 6 -free bipartite graphs) have bounded clique-width.

Recently, there is increasing interest in classes of bipartite graphs of bounded clique-width. The motivation partially comes from applications in Model Checking which is crucial in the theory of Database Systems as well as Constraint Satisfaction of Artificial Intelligence -see [START_REF] Gottlob | Hypergraphs in model checking: acyclicity and hypertree-width versus clique-width[END_REF]. The model checking problem can be formulated in terms of hypergraphs, and the corresponding bipartite vertex-hyperedge incidence graph of a hypergraph H uniquely determines H. It turns out that bounded clique-width of this bipartite incidence graph is one of the most general conditions under which the model checking problem can be solved efficiently.

Subsequently, we always focus on the nonbipartite case since bipartite P 6 -free graphs were studied in [START_REF] Fouquet | Bipartite graphs totally decomposable by canonical decomposition[END_REF][START_REF] Lozin | Bipartite graphs without a skew star[END_REF]. The main result of this paper, namely Theorem 1, gives a complete structure analysis of P 6 -and triangle-free graphs and implies bounded clique-width of these graphs.

Basic Notions and Tools

Throughout this paper, let G = (V, E) be a finite undirected graph without self-loops and multiple edges and let

|V | = n, |E| = m. For a vertex v ∈ V , let N (v) = {u | uv ∈ E} denote the neighborhood of v in G,
and, more generally, let N i (v) denote the set of vertices with distance i to v, i ≥ 1.

Disjoint vertex sets X, Y form a join, denoted by X 1 Y (co-join, denoted by X 0 Y ) if for all pairs x ∈ X, y ∈ Y , xy ∈ E (xy / ∈ E) holds. Subsequently, we will consider join and co-join also as operations, i.e., the join operation between disjoint vertex sets X, Y adds all edges between them, whereas the co-join operation for X and Y is the disjoint union of the subgraphs induced by X and Y (without edges between them).

Let

u ∼ v if uv ∈ E and u ∼ v otherwise. We will call u ∼ v a coedge. A vertex z ∈ V distinguishes vertices x, y ∈ V if zx ∈ E and zy / ∈ E. A vertex set M ⊆ V is a module if no vertex from V \ M distinguishes
two vertices from M , i.e., every vertex v ∈ V \ M has either a join or a co-join to M . A vertex set is trivial if it is empty, one-elementary or the entire vertex set. Note that trivial vertex sets are modules, the so-called trivial modules. Nontrivial modules are called homogeneous sets.

A graph is prime if it contains only trivial modules. The notion of module plays a crucial role in the modular (or substitution) decomposition of graphs (and other discrete structures) which is of basic importance for the design of efficient algorithms -see e.g. [START_REF] Möhring | Substitution decomposition for discrete structures and connections with combinatorial optimization[END_REF] for modular decomposition of discrete structures and its algorithmic use and [START_REF] Mcconnell | Modular decomposition and transitive orientation[END_REF] for a linear-time algorithm constructing the modular decomposition tree of a given graph.

For U ⊆ V , let G[U ] denote the subgraph of G induced by U . Throughout this paper, all subgraphs are understood to be induced subgraphs. Let F denote a set of graphs. A graph is F-free if none of its induced subgraphs is in F.

A vertex set U ⊆ V is stable (or independent) in graph G if the vertices in U are pairwise nonadjacent. For a given graph with vertex weights, the Maximum Weight Stable Set (MWS) Problem asks for a stable set of maximum vertex weight.

Let co-G = G = (V, E) denote the complement graph of G. A vertex set U ⊆ V is a clique in G if U is a stable set in G. Let K ℓ denote the clique with ℓ vertices, and let ℓK 1 denote the stable set with ℓ vertices. K 3 is called triangle.

Recall that for k ≥ 1, P k denotes a chordless path with k vertices and k -1 edges, and for k ≥ 3, C k denotes a chordless cycle with k vertices and k edges.

Moreover, recall that S i,j,k denotes the tree with exactly one vertex r of degree 3 and three leaves which have distance i, j, k from r, respectively. Thus, the S 1,2,3 has vertices a, b, c, d, e, f, g and edges ab, bc, cd, de, ef, cg.

The paw has vertices a, b, c, d and edges ab, ac, bc, cd. The house is the co-P 5 . The bull has vertices a, b, c, d, e and edges ab, bc, cd, be, ce. The double-gem has vertices a, b, c, d, e, f and edges ab, ac, bc, bd, cd, ce, de, df , ef .

For In what follows, we need the following classes of bipartite and co-bipartite graphs:

• G is matched co-bipartite if its vertex set is partitionable into two cliques C 1 , C 2 with |C 1 | = |C 2 | or |C 1 | = |C 2 | -
Z = Z 1,3 ∪ Z 2,4 ∪ Z 3,5 ∪ Z 4,1 ∪ Z 5,2 . Obviously, {v 1 , . . . , v 5 } ∪ X ∪ Y ∪ Z is a partition of V .
Lemma 1 Let G be a triangle-free graph containing a C 5 C with vertices v 1 , . . . , v 5 and edges {v i , v i+1 }, i ∈ {1, . . . , 5}. Then the following properties hold for all i ∈ {1, . . . , 5}:

(i) Y i and Z i,i+2 are stable sets; (ii) Y i 0 (Z i,i+2 ∪ Z i-2,i ); (iii) Z i,i+2 0 Z i+2,i+4 ; (iv) if G is connected P 6 -free then the set X of 0-vertices of the C 5 C is a stable set, Y i 0 X, and Y i 1 Y i+2 as well as Y i 0 Y i+1 .
Lemma 2 Let G be a prime (P 6 ,K 3 )-free graph containing a C 5 C with vertices v 1 , . . . , v 5 and edges {v i , v i+1 }, i ∈ {1, . . . , 5}. Then the following properties hold for all i ∈ {1, . . . , 5}:

(i) every vertex in Z i-1,i+1 with a neighbor in Y i has a join to Z i-2,i and to Z i,i+2 ;
(ii) vertices in Y i can only be distinguished by vertices in Z i-1,i+1 ;

(iii) coedges between consecutive 2-vertex sets cannot be distinguished by 0-vertices;

(iv) there are no two 0-vertices x, y ∈ X with x adjacent to Z i,i+2 and y adjacent to Z i+2,i+4 ;

(v) if |Y i | ≥ 2 then Y i-2 = Y i+2 = ∅; (vi) if x ∼ y is a coedge with x ∈ Z i,i+2 and y ∈ Z i+1,i+3 then x 1 Y i+3 and y 1 Y i ; (vii) vertices x ∈ Z i,i+2 , y ∈ Z i+1,i+3 with x ∼ y cannot be distinguished by vertices in Y i+4 ;
Proof: In this proof and subsequent ones, without loss of generality, we choose some fixed values for i ∈ {1, . . . , 5}.

(i) If x ∈ Y 3 , y ∈ Z 2,4 and z ∈ Z 3,5 with x ∼ y and y ∼ z then x, y, v 2 , v 1 , v 5 , z induce a P 6 in G. (ii) By Lemma 1, Z i-2,i and Z i,i+2 have a co-join to Y i . Assume that x, y ∈ Y 3 and z ∈ Z 5,2 such that x ∼ z and y ∼ z. Then v 1 , v 5 , z, x, v 3 , y induce a P 6 in G. ( iii) If x ∈ Z 1,3 , y ∈ Z 2,4 and z ∈ X such that x ∼ y and z ∼ x, z ∼ y then z, x, v 1 , v 5 , v 4 , y induce a P 6 in G.
( iv) Assume that there are vertices x, y ∈ X, x = y and u

∈ Z 1,3 , v ∈ Z 3,5 such that x ∼ u, y ∼ v. Since x, u, v 1 , v 5 , v, y induce no P 6 , either x ∼ v or y ∼ u but if x ∼ v and y ∼ u then v 2 , v 1 , u, x, v
, y induce a P 6 . Thus, x and y have the same neighborhood in Z 1,3 and Z 3,5 . Since G is prime, there must be a vertex z distinguishing x and y, say z ∼ x and z ∼ y. Recall that by Lemma 1 ( iv), no 0and no 1-vertex can distinguish x and y. Thus, z must be a 2-vertex.

If z ∈ Z 5,2 then y, v, x, z, v 2 , v 1 induce a P 6 , and similarly for z ∈ Z 4,1 . Finally, assume that

z ∈ Z 2,4 . Note that z ∼ u and z ∼ v since z ∼ x, x ∼ u, x ∼ v and G is triangle-free but now v, y, u, v 1 , v 2 , z induce a P 6 -contradiction. ( v) If |Y 3 | ≥ 2 then, since Y 3 is no module, there are s, s ′ ∈ Y 3 , s = s ′ , and x ∈ Z 2,4 such that x ∼ s and x ∼ s ′ . If Y 1 = ∅ and r ∈ Y 1 then s ′ , r, s, x, v 4 , v 5 induce a P 6 . (vi) If x ∈ Z 1,3 , y ∈ Z 2,4 and u ∈ Y 4 (v ∈ Y 1 , respectively) with x ∼ y and x ∼ u (y ∼ v, respectively) then u, v 4 , y, v 2 , v 1 , x (v, v 1 , x, v 3 , v 4 , y, respectively) induce a P 6 in G. ( vii) If x ∈ Z 1,3 , y ∈ Z 2,4 and z ∈ Y 5 such that x ∼ y and x ∼ z, y ∼ z then z, x, v 1 , v 2 , y, v 4 induce a P 6 in G.

✷

Lemma iv can also be expressed in the following way: If the set of 0-vertices adjacent to Z i,i+2 is nontrivial then the set of 0-vertices adjacent to Z i+2,i+4 is empty.

An immediate consequence of Lemma v is Corollary 1 At most two of the 1-vertex sets are nontrivial, namely consecutive ones.

For the next section we need the following notions:

Z 0 i,i+2 := {x | x ∈ Z i,i+2
and x has a nonneighbor in Z i-1,i+1 or in Z i+1,i+3 } for i ∈ {1, . . . , 5}, and let

Z 0 := 5 i=1 Z 0 i,i+2 . We say that 2-vertices v ∈ Z 0 are of type 0 and 2-vertices v ∈ Z \ Z 0 are of type 1.
Let X 0 denote the set of 0-vertices being adjacent to a vertex in Z 0 , and let

G 0 := G[X 0 ∪ Z 0 ]. 3 Structure of the Subgraph G 0 := G[X 0 ∪ Z 0 ]
Throughout this section, let G be a P 6 -and triangle-free graph containing C 5 C with vertices v 1 , . . . , v 5 and edges {v i , v i+1 }, i ∈ {1, . . . , 5}. The aim of this section is to describe the structure of G 0 as a first step of the complete structure description of G. We first focus on the structure of the subgraph G[Z 0 ]. In the subsequent Lemmas 3, 4, 5 and 6, primality of the graph is not required.

Lemma 3 (i)

There are no four vertices x, u ∈ Z i,i+2 , y, v ∈ Z i+1,i+3 such that x ∼ y, x ∼ v, u ∼ y, and u ∼ v.

(ii) There are no four vertices x ∈ Z i-1,i+1 , y, y ′ ∈ Z i,i+2 and z ∈ Z i+1,i+3 such that x ∼ y, x ∼ y ′ , y ∼ z, and y ′ ∼ z.

(iii) There are no four vertices u

∈ Z i-1,i+1 , v ∈ Z i,i+2 , x ∈ Z i+1,i+3 , y ∈ Z i+2,i+4 such that u ∼ v, v ∼ x and x ∼ y.
Proof:

(i) If there are four vertices x, u ∈ Z 1,3 , y, v ∈ Z 2,4 such that x ∼ y, x ∼ v, u ∼ y, and u ∼ v then u, v 1 , x, y, v 4 , v induce a P 6 in G.
( ii) If there are four vertices x ∈ Z 1,3 , y, y ′ ∈ Z 2,4 and z ∈ Z 3,5 such that x ∼ y, x ∼ y ′ , y ∼ z, and

y ′ ∼ z then y, x, v 1 , v 5 , z, y ′ induce a P 6 in G. (iii) If there are four vertices u ∈ Z 5,2 , v ∈ Z 1,3 , x ∈ Z 2,4 , y ∈ Z 3,5 such that u ∼ v, v ∼ x and x ∼ y then v, x, v 2 , u, v 5 , y induce a P 6 in G.
✷ Figure 1 shows the three forbidden configurations of Lemma 3 (boldface edges indicate P 6 ). A simple consequence of Lemma 3 is the following:

Lemma 4 If there are x ∈ Z 0 i,i+2 , y ∈ Z 0 i-1,i+1 , z ∈ Z 0 i-2,i such that x ∼ y and y ∼ z then Z 0 i+1,i+3 = ∅. Analogously, if there are x ∈ Z 0 i,i+2 , y ∈ Z 0 i-1,i+1 , z ∈ Z 0 i-2,i such that x ∼ y and y ∼ z then Z 0 i-3,i-1 = ∅. Proof: Let x ∈ Z 0 5,2 , y ∈ Z 0 4,1
and z ∈ Z 0 3,5 such that x ∼ y and y ∼ z. Then x 1 Z 0 1,3 , since otherwise there is a u ∈ Z 0 1,3 with x ∼ u, and then z, y, x, u contradict to Lemma 3 ( iii). Since x ∈ Z 0 , x must have a nonneighbor y ′ ∈ Z 0 4,1 . Assume that there is a vertex u ∈ Z 0 1,3 . Then u 1 Z 0 2,4 , since otherwise there is a w ∈ Z 0 2,4 with u ∼ w, and then y ′ , x, u, w contradict to Lemma 3 ( iii). Thus, since u ∈ Z 0 , u must have a nonneighbor x ′ ∈ Z 0 5,2 . Now x ′ ∼ y ′ , otherwise y ′ , x ′ , x, u contradict to Lemma 3 ( ii), and x ′ ∼ y, otherwise y, y ′ , x, x ′ contradict to Lemma 3 ( i), but now z, y, x ′ , u contradict to Lemma 3 ( iii) Thus, Z 0 1,3 = ∅. The second claim follows by symmetry. ✷

Another consequence of Lemma 3 ( i) and Lemma 2 is the following property:

Lemma 5 Vertices x, x ′ ∈ Z 0 i,i+2 having a common nonneighbor y ∈ Z 0 i-1,i+1 (y ∈ Z 0 i+1,i+3 , respectively) can only be distinguished by a vertex y ′ ∈ Z 0 i+1,i+3 (y ′ ∈ Z 0 i-1,i+1
, respectively).

Proof: Let x, x ′ ∈ Z 0 5,2 and let y ∈ Z 0 4,1 be a common nonneighbor of x and x ′ . By Lemma 2 ( iii) x and x ′ cannot be distinguished by 0-vertices of C since a 0-vertex z being adjacent to x is also adjacent to y and thus to x ′ . Since G is K 3 -free, x and x ′ do not have edges to Y 5 and Y 2 . By Lemma 2 ( i), x and x ′ do not have edges to Y 1 . By Lemma 2 ( vi, x and x ′ have a join to Y 4 . By Lemma 2 ( vii), x and x ′ cannot be distinguished by Y 3 vertices. By Lemma 3 ( i), x and x ′ cannot be distinguished by a vertex from Z 4,1 . Thus, if y ′ distinguishes x and x ′ then necessarily y ′ ∈ Z 0 1,3 . ✷ Lemma 6 If there is an edge between a vertex in Z 0 i,i+2 and Z 0 i+1,i+3 then the following conditions are fulfilled:

(i) Z 0 i+2,i+4 = ∅ or Z 0 i-1,i+1 = ∅. (ii) If Z 0 i-1,i+1 = ∅ then Z 0 i-1,i+1 0 Z 0 i,i+2 .
Proof: Let xy ∈ E be an edge with x ∈ Z 0 5,2 and y ∈ Z 0 4,1

( i) Assume that Z 0 1,3 = ∅ and Z 0 3,5 = ∅. If y has a nonneighbor in Z 0 3,5 then by Lemma 4, Z 0 1,3 = ∅, and analogously, if x has a nonneighbor in Z 0 1,3 then by Lemma 4, Z 0 3,5 = ∅. Thus, for every edge xy ∈ E, x ∈ Z 0 5,2 , y ∈ Z 0 4,1 , x 1 Z 0 1,3 and y 1 Z 0 3,5 holds. Since x ∈ Z 0 5,2 , x has a nonneighbor y ′ ∈ Z 0 4,1 , and analogously, y has a nonneighbor x ′ ∈ Z 0 5,2 . By Lemma 3 ( i), x ′ ∼ y ′ . Now let z ∈ Z 0 1,3 . By Lemma 4, applied to y ′ , x, z, Z 0 2,4 = ∅ follows. Thus, z must have a nonneighbor x ′′ ∈ Z 0 5,2 , x ′′ = x, x ′′ = x ′ (note that by Lemma 3 ( ii), applied to z, x, x ′ , y ′ , also x ′ ∼ z). If x ′′ has a neighbor y ′′ ∈ Z 0 4,1 then by Lemma 4, z, x ′′ , y ′′ imply Z 0 3,5 = ∅ -contradiction. Thus, x ′′ has a co-join to Z 0 4,1 , but now x, y, x ′′ , y ′ contradict to Lemma 3 ( i). Thus ( i) holds.

( ii) Let Z 0 3,5 = ∅ and assume that there is an edge between Z 0 3,5 and Z 0 4,1 . Then by ( i), Z 0 1,3 = Z 0 2,4 = ∅. Let z ∈ Z 0 3,5 have a neighbor y ′ ∈ Z 0 4,1 , and recall that x ∈ Z 0 5,2 has neighbor y ∈ Z 0 4,1 . If x and z have no common neighbor in Z 0 4,1 (i.e., x ∼ y ′ and z ∼ y) then x, y, y ′ , z contradicts to Lemma 3 ( ii). Thus x and z have a common neighbor, say w ∈ Z 0 4,1 . Since Z 0 1,3 = Z 0 2,4 = ∅, x has a nonneighbor u ∈ Z 0 4,1 and z has a nonneighbor u ′ ∈ Z 0 4,1 . If x and z have no common nonneighbor in Z 0 4,1 then x, u, u ′ , z contradict to Lemma 3 ( ii). Thus let u ∈ Z 0 4,1 be a common nonneighbor of x and z. Then w has a nonneighbor x ′ ∈ Z 0 5,2 or z ′ ∈ Z 0 3,5 ; without loss of generality, say x ′ w / ∈ E. By Lemma 3 ( i), x ′ ∼ u but now x ′ , u, w, z contradict to Lemma 3 ( ii). Thus, ( ii) holds.

✷

Lemma 7 Let G be a prime P 6 -and triangle-free graph containing C 5 as above. If there is an edge between a vertex in Z 0 i,i+2 and a vertex in

Z 0 i+1,i+3 then G[Z 0 i,i+2 ∪ Z 0 i+1,i+3
] is a co-matched bipartite graph.

Proof: Let ab ∈ E with a ∈ Z 0 4,1 and b ∈ Z 0 5,2 . By Lemma 6 ( i), Z 0 1,3 = ∅ or Z 0 3,5 = ∅, say Z 0 1,3 = ∅. Assume that Z 0 4,1 ∪ Z 0 5,2 do not induce a co-matched bipartite graph. Then two vertices in one of the two sets have a common nonneighbor in the other. First assume that x, x ′ ∈ Z 0 5,2 have a common nonneighbor y ∈ Z 0 4,1 . Then, by Lemma 5, only vertices in Z 0 1,3 can distinguish x and x ′ but Z 0 1,3 = ∅. Now assume that x, x ′ ∈ Z 0 4,1 have a common nonneighbor y ∈ Z 0 5,2 . Then, again by Lemma 5, only vertices in Z 0 3,5 can distinguish x and x ′ but by Lemma 6 ( ii), there are no edges between Z 0 3,5 and

Z 0 4,1 . Since G is prime, G[Z 0 4,1 ∪ Z 0 5,2 ] is co-matched bipartite. ✷ Corollary 2 G[Z 0
] is either the disjoint union of two co-matched bipartite graphs (which are possibly empty or one of their color classes is empty and the other is trivial) or for each i ∈ {1, . . . , 5}, |Z 0 i,i+2 | = 1.

Proof: If there are no edges between consecutive sets Z 0 i,i+2 , i ∈ {1, . . . , 5}, then by Lemma 5, all Z 0 i,i+2

are modules, and since G is prime,

|Z 0 i,i+2 | ≤ 1.
If in addition at least one of them is empty, G[Z 0 ] is the disjoint union of two (trivial) co-matched bipartite graphs. Now assume without loss of generality that there is an edge between Z 0 4,1 and Z 0 5,2 . Then by Lemma 7, Z 0 4,1 and Z 0 5,2 induce a co-matched bipartite graph, and by Lemma 6 ( i), Z 0 3,5 = ∅ or Z 0 1,3 = ∅, say Z 0 1,3 = ∅, and if also Z 0 3,5 = ∅ then Z 0 2,4 = ∅ by definition of type 0 2-vertices. If Z 0 3,5 = ∅ then Z 0 3,5 0 Z 0 4,1 by Lemma 6 ( ii). Now, if there is an edge between Z 0 2,4 and Z 0 3,5 then again by Lemma 7, Z 0 2,4 and Z 0 3,5 induce a co-matched bipartite graph, and if there is no edge between Z 0 2,4 and Z 0 3,5 then by Lemma 5, both sets have at most one vertex since G is prime In either case, G[Z 0 ] is the disjoint union of two co-matched bipartite graphs. ✷ Now, we add the 0-vertices X 0 being adjacent to

Z 0 to G[Z 0 ]. A copath in G[Z 0
] is a sequence of coedges x i x i+1 , i ∈ {1, . . . , k}, such that x i ∈ Z 0 j,j+2 , x i+1 ∈ Z 0 j+1,j+3 or x i ∈ Z 0 j,j+2 , x i+1 ∈ Z 0 j-1,j+1 for some j ∈ {1, . . . , 5}. A cocomponent in G[Z 0 ] is a maximal vertex subset U ⊆ Z 0 such that for every x and y in U , there is a copath connecting x and y.

Lemma 8 For each cocomponent Q in G[Z 0 ], the set X Q of 0-vertices being adjacent to Q is a module in G.
Proof: Let Q be a cocomponent in G[Z 0 ], and let X Q denote the set of 0-vertices being adjacent to Q. Assume that X Q is no module in G. Then there are x, y ∈ X Q and z / ∈ X Q such that x ∼ z and y ∼ z. By Lemma 2 ( iii), every 0-vertex adjacent to Q has a join to Q, i.e., x 1 Q and y

1 Q. Let u ∈ Z 0 1,3 , v ∈ Z 0 2,4
, u ∼ v, be neighbors of x, y: {x, y} 1 {u, v}. By Lemma 1 ( iv), the distinguishing vertex z is no 0-vertex since X is a stable set, and z is no 1-vertex since X 0 Y . Thus, z must be a 2-vertex.

By Lemma 2 ( iv), z ∈ (Z 3,5 ∪ Z 4,1 ∪ Z 5,2 ). Thus, let z ∈ Z 1,3 (z ∈ Z 2,4 , respectively). Then z ∼ v (z ∼ u, respectively), since otherwise x, z, v (x, z, u, respectively) induce a triangle but now z and v (z and u, respectively) form a coedge distinguished by y, a contradiction to Lemma 2 ( iii).

✷ Since G is prime, |X Q | ≤ 1 for all cocomponents Q of G[Z 0 ]. Thus, if G[Z 0 ]
has only one cocomponent then there is at most one 0-vertex being adjacent to Z 0 . Note that by Lemma 6 ( ii) and by Corollary 2, if G[Z 0 ] consists of two nonempty co-matched bipartite graphs then it has only one cocomponent. In the case in which G[Z 0 ] consists of only one co-matched bipartite graph, it may have arbitrarily many cocomponents (which are just single coedges), and then by Lemma 8, every coedge of G[Z 0 ] can have exactly one neighbor in X. Since G is K 3 -free, every 0-vertex is adjacent to at most one coedge (note that in a co-matched bipartite graph every two coedges are connected by two edges).

4 Structure of Nonbipartite Prime (P 6 ,K 3 )-free Graphs

The aim of this section is to give a complete structure description of nonbipartite prime (P 6 ,K 3 )-free graphs G which also will lead to bounded clique-width. For this purpose, we subdivide G into the subgraph G 0 and into five bipartite subgraphs based on the other 2-vertex sets, the 1-vertex sets and the other 0-vertices. It is already clear that {v 1 , . . . , v 5 }, X, Y and Z define a partition of the vertex set V of G.

Let Z 1 i,i+2 := Z i,i+2 \ Z 0 i,i+2 and Z 1 := Z \ Z 0 . For i ∈ {1, . . . , 5}, let X i denote the set of 0-vertices being adjacent to Z 1 i-1,i+1 . Now, if for i ∈ {0, 1, . . . , 5}, X i is trivial, we will omit the single vertex in X i , i.e., let

X ′ i = X i if X i is nontrivial ∅ otherwise For i ∈ {1, . . . , 5}, let B i := G[X ′ i ∪ Y i ∪ Z 1 i-1,i+1 ]
. By Lemma 1 ( iv), X ∪ Y i is a stable set, and thus, B i is bipartite. Let X T denote the union of trivial X i , i ∈ {0, 1, . . . , 5}.

The basic subgraphs in G are the subgraphs G 0 and B i , i ∈ {1, . . . , 5}.

Lemma 9

The vertex sets X ′ 0 , Z 0 of G 0 and the vertex sets

X ′ i , Y i , Z 1 i-1,i+1 of B i , i ∈ {1, . . . , 5}, define a partition of V \ ({v 1 , . . . , v 5 } ∪ X T ).
Proof: Obviously, X, Y and Z define a partition of V \ {v 1 , . . . , v 5 }, Z 0 and Z 1 define a partition of Z, and Z 1 i,i+2 , i ∈ {1, . . . , 5}, define a partition of Z 1 . Moreover, G 0 contains no 1-vertices, and Y i , i ∈ {1, . . . , 5}, define a partition of Y . Claim 4.1 If a 0-vertex is adjacent to some Z 1 i,i+2 then it is not adjacent to Z 0 i,i+2 . Proof. Without loss of generality, let x ∈ Z 1 1,3 and y ∈ Z 0 1,3 with a nonneighbor z ∈ Z 0 2,4 , z ∼ y. If for a 0-vertex u, u ∼ x and u ∼ y then by Lemma 2 ( iii), u ∼ z but now x, u, z induce a trianglecontradiction. This shows Claim 4.1.

Claim 4.2 If a 0-vertex from X ′

i+1 is adjacent to some Z 1 i,i+2 then it is not adjacent to Z 0 j,j+2 and not adjacent to Z 1 j,j+2 for j = i. Proof. Since G is K 3 -free, a 0-vertex being adjacent to Z 1 i,i+2 is nonadjacent to Z i-1,i+1 and Z i+1,i+3 , and by Lemma 2 ( iv), if X i+1 is nontrivial then no vertex of X i+1 is adjacent to Z i-2,i or Z i+2,i+4 . This shows Claim 4.2. By Claims 4.1 and 4.2, X 0 ∩ (X 1 ∪ . . . ∪ X 5 \ X T ) = ∅. Now by Claim 4.2 the sets X i , X j , i = j, are disjoint Thus, X 0 , X 1 , . . . , X 5 form a partition of X \ X T . This completes the proof of Lemma 9. ✷ Recall that by Lemma 2 ( ii), vertices in Y i can only be distinguished by vertices in Z i-1,i+1 . Thus, every vertex in Z i-1,i+1 has either a join or a co-join to Y i+2 (Y i+3 , respectively).

Let Z i-1,i+1;00 (Z i-1,i+1;01 , Z i-1,i+1;10 , Z i-1,i+1;11 , respectively) be the set of 2-vertices in Z i-1,i+1 having a co-join to Y i+2 and Y i+3 (having a co-join to Y i+2 and a join to Y i+3 , having a join to Y i+2 and a co-join to Y i+3 , having a join to Y i+2 and Y i+3 , respectively). Moreover, let Z a i-1,i+1;bc = Z a i-1,i+1 ∩ Z i-1,i+1;bc , a ∈ {0, 1}, bc ∈ {00, 01, 10, 11}.

The basic vertex subsets of G are X ′ 0 , X ′ 1 , . . . , X ′ 5 , Y 1 , . . . , Y 5 , and Z a i-1,i+1;bc , i ∈ {1, . . . , 5}, a ∈ {0, 1}, bc ∈ {00, 01, 10, 11}.

Lemma 10 For all pairs of basic vertex subsets U, W from different basic subgraphs, either

U 1 W or U 0 W . Proof: First assume that U ∈ {X ′ 0 , X ′ 1 , . . . , X ′ 5 }. If also W ∈ {X ′ 0 , X ′ 1 , . . . , X ′ 5 } then U 0 W since by Lemma 1 ( iv), X is a stable set.
If W ∈ {Y 1 , . . . , Y 5 } then U 0 W since by Lemma 1 ( iv), there are no edges between 0-vertices and 1-vertices.

If W is a basic subset of 2-vertices, we have the following cases: First assume that U = X ′ 0 . Let W = Z 1 i-1,i+1;bc (note that W = Z 0 i-1,i+1;bc is impossible since W belongs to another basic subgraph). Assume that u ∈ U with u being adjacent to some x ∈ Z 0 4,1 and

y ∈ Z 0 5,2 , x ∼ y. Then u 0 W for W ∈ {Z 1 3,5 , Z 1 4,1 , Z 1 5,2 , Z 1 1,3 } since G is K 3 -free, and u 0 W for W = Z 1 2,4 by Lemma 2 ( iv) since X ′ 0 is assumed to be nontrivial or empty. Now assume that U ∈ {X ′ 1 , . . . , X ′ 5 }, say U = X ′ 1 .
Then, by Lemma 9, U 0 Z 0 since X 0 ∩ X ′ 1 = ∅. This completes the case analysis when U is a basic set of 0-vertices.

Next assume that

U ∈ {Y 1 , . . . , Y 5 }. If also W ∈ {Y 1 , . . . , Y 5 } then U 1 W or U 0 W by Lemma 1 ( iv).
Now, without loss of generality, let U = Y 1 , and assume that W is a basic subset from another basic subgraph. Since G is K 3 -free, U 0 Z 4,1 ∪ Z 1,3 . By Lemma 2 ( i), U 0 Z 0 5,2 . By definition of the basic subsets Z a 2,4;bc and Z a 3,5;bc , U has join or co-join to all these basic subsets. Finally, the connections between basic 2-vertex subsets from different basic subgraphs are join or cojoin by Lemma 1 ( iii), by definition of Z 1 i,i+2 and by the definition of B i and G 0 . Thus, Z 1 i,i+2 has a join to Z i-1,i+1 and Z i+1,i+3 and a co-join to Z i-2,i and Z i+2,i+4 , i ∈ {1, . . . , 5}.

This shows Lemma 10. ✷

An immediate consequence of Lemma 9 and Lemma 10 is the following decomposition of G which is the main result of this paper (notation of basic subsets and basic subgraphs as above):

Theorem 1 (Structure Theorem) Let G be a prime (P 6 ,K 3 )-free graph which is not bipartite, and let C be a C 5 in G. Then the vertex set of G[V \ (V (C) ∪ X T )] can be partitioned into the (possibly empty) basic subgraph G 0 = G[Z 0 ∪X 0 ] and into the five (possibly empty) basic bipartite subgraphs B 1 , . . . , B 5 such that the connections between the basic vertex subsets of different basic subgraphs are only join or co-join.

Recall that G 0 consists of the bipartite subgraph G[Z 0 ] which, according to Corollary 2, is either the disjoint union of two co-matched bipartite graphs or fulfills |Z 0 i,i+2 | = 1 for i ∈ {1, . . . , 5}, and the 0-vertices in X 0 being adjacent to Z 0 . Thus, for instance, the clique-width of a graph with nine vertices is at most seven. Another helpful tool is Lemma 12 ([1]) Let G = (V, E) be a graph and V = F 1 ∪ F 2 be a partition of V with |F 2 | ≤ s for some s. If there is a t-expression for G[F 1 ] then there is a (2 s • (t + 1))-expression for G.

This lemma means that adding a constant number s of vertices to a graph H from a class of bounded clique-width maintains bounded clique-width. This allows to disregard certain specific vertices and thus to reduce graph G to its essential part G ′ .

We also need the following principle:

Principle 1 ([3]) Let G = (V, E) be a graph and V = V 1 ∪ . . . ∪ V p be a partition of V .
If there is a t-expression for G then there is a p • t-expression for G such that finally for each i ∈ {1, 2, . . . , p}, vertices in V i get the same label and l(u) = l(v) for each pair u ∈ V i , v ∈ V j , i = j.

Our clique-width analysis of (P 6 ,K 3 )-free graphs is based on the following results by Lozin [START_REF] Lozin | Bipartite graphs without a skew star[END_REF] and, slightly earlier, by Fouquet, Giakoumakis and Vanherpe [START_REF] Fouquet | Bipartite graphs totally decomposable by canonical decomposition[END_REF].

Theorem 3 ([17])

The clique-width of bipartite S 1,2,3 -free graphs is at most 5.

Theorem 4 ([12])

The clique-width of bipartite P 6 -free graphs is at most 4, and given such a graph, a 4-expression can be constructed in linear time.

We also need:

Proposition 2
The clique-width is at most 4 for matched co-bipartite as well as for co-matched bipartite graphs, and corresponding k-expressions, k ≤ 4, can be obtained in linear time.

The proof of Proposition 2 is straightforward.

To give an example, we describe how a graph G = (X ∪ Y ∪ Z, E) with pairwise disjoint vertex sets X, Y, Z, each of size n, consisting of a prime co-matched bipartite graph B = (X, Y, E) with coedges x i y i , i ∈ {1, . . . , n}, and with an additional neighbor z i ∈ Z, i ∈ {1, . . . , n}, to each coedge x i y i , can be constructed with 6 labels: α 1 := ρ 5→6 (η 5,2 (η 5,1 (5(z 1 ) ⊕ (1(x 1 ) ⊕ 2(y 1 )))))

For i := 2 to n let α i := ρ 4→2 (ρ 3→1 (ρ 5→6 (η 3,2 (η 4,1 (η 5,4 (η 5,3 (5(z i ) ⊕ (3(x i ) ⊕ (4(y i ) ⊕ α i-1 ))))))))). Now, Theorem 1 implies:

Corollary 3 The clique-width of (P 6 ,K 3 )-free graphs is bounded.

Proof: If G is bipartite then by Theorem 4, its clique-width is at most 4. Now assume that G is prime and not bipartite. Then Theorem 1 describes its structure. If all sets of 0-, 1-and 2-vertices are trivial then G has at most 16 vertices and, by Lemma 11, its clique-width is at most 13. The clique-width of G 0 is at most 6 as the example above shows, and for every i ∈ {1, . . . , 5}, B i is bipartite and thus, by Theorem 4, its clique-width is at most 4. Now, applying Principle 1, the 2-vertex subsets in the basic subgraphs G 0 and B i are subdivided into the four basic subsets. It is clear that there are k-expressions for G 0 and B i where the basic subsets finally get different labels. By Theorem 1, the edge sets between basic subsets from different basic subgraphs are only join or co-join. Thus, finally these edges can easily be generated. This gives bounded clique-width for G. ✷

A more detailed analysis shows that the clique-width bound for (P 6 ,K 3 )-free graphs can be improved to 36 since in all cases, some of the subsets are trivial.

In [START_REF] Mahfud | Effiziente Algorithmen zur Bestimmung der Unabhängigkeitszahl in Graphen[END_REF], it is shown that (S 1,1,3 ,K 3 )-free graphs as well as (S 1,2,2 ,K 3 )-free graphs have bounded cliquewidth.

The clique-width of (P 6 ,K 4 )-free graphs is unbounded since in [START_REF] Brandstädt | Clique-Width for Four-Vertex Forbidden Subgraphs[END_REF], it is shown that the clique-width for the smaller class of (2K 2 ,K 4 )-free graphs is unbounded (the 2K 2 is the complement of C 4 ). In the same paper, it is mentioned that for P 7 -free bipartite graphs, it is unknown whether the clique-width of these graphs is bounded or unbounded. It also seems to be unknown whether the clique-width of (P 7 ,K 3 )-free graphs is bounded or unbounded.

6 Time Bound for Robustly Constructing a k-Expression for G By a result of Giakoumakis and Vanherpe [START_REF] Giakoumakis | Linear time recognition and optimization for weak-bisplit graphs, bi-cographs and bipartite P 6 -free graphs[END_REF], P 6 -free bipartite graphs can be recognized in linear time. By Theorem 4, the clique-width of these graphs is at most 4, and given such a graph, a 4-expression can be constructed in linear time. From now on, we focus on nonbipartite graphs.

The aim of this section is to give an efficient algorithm which for arbitrary prime nonbipartite input graph G either determines a k-expression of G or finds out that G is not (P 6 ,K 3 )-free. The time bound of our algorithm is O(n 2 ). Algorithm 1 does not check whether the input graph is indeed (P 6 ,K 3 )-free; instead, it tries to find an induced C 5 or K 3 or P 6 in G, and if a C 5 is found, it checks whether G fulfills the conditions of the Structure Theorem. Thus, for constructing a k-expression for G, it is of crucial importance to find a C 5 in G.

Algorithm 1: Input: An arbitrary prime nonbipartite graph G = (V, E).

Output: An induced C 5 or K 3 or P 6 in G.

(1) Pick a vertex v ∈ V and determine the levels N i (v), i ≥ 1, by applying Breadth-First Search to G with start vertex v.

(2) Check whether N 5 (v) = ∅. If yes then G contains a P 6 -STOP. {Otherwise, from now on, N k (v) = ∅ for k ≥ 5.}

(3) Check whether N (v) is a stable set. If not then G contains a K 3 -STOP.

(4) Check whether N 2 (v) is a stable set. If not then let x ∼ y for some x, y ∈ N 2 (v).

(4.1) Check whether x and y have a common neighbor in N (v). If yes then G contains a K 3 -STOP.

(4.2) Otherwise, let u x (u y ) be a neighbor of x (y) in N (v). Then v, u x , x, y, u y is a C 5 -STOP.

(5) Check whether N 3 (v) is a stable set. If not then let x ∼ y for some x, y ∈ N 3 (v).

(5.1) Check whether x and y have a common neighbor in N 2 (v). If yes then G contains a K 3 -STOP.

(5.2) Otherwise, let u x (u y ) be a neighbor of x (y) in N 2 (v). Check whether u x and u y have a common neighbor w in N (v). If yes then w, u x , x, y, u y is a C 5 -STOP. Otherwise, let w x (w y ) be a neighbor of u x (u y ) in N (v). Then w x , u x , x, y, u y , w y is a P 6 -STOP.

(6) {Now, since G is not bipartite, N 4 (v) is not a stable set.} Determine an edge x ∼ y for some x, y ∈ N 4 (v).

(6.1) Check whether x and y have a common neighbor in N 3 (v). If yes then G contains a K 3 -STOP.

(62) Otherwise, let u x (u y ) be a neighbor of x (y) in N 3 (v). Check whether u x and u y have a common neighbor w in N 2 (v). If yes then w, u x , x, y, u y is a C 5 -STOP. Otherwise, let w x (w y ) be a neighbor of u x (u y ) in N 2 (v). Then w x , u x , x, y, u y , w y is a P 6 -STOP. Steps ( 2), ( 3), ( 4), ( 5) and ( 6): can obviously be done in linear time.

Steps (4.1) and (4.2), (5.1) and (5.2), (6.1) and (6.2): can obviously be done in time O(n 2 ). ✷

If Algorithm 1 ends with a C 5 C then the next task is to classify the vertices not in C as k-vertices, 0 ≤ k ≤ 5. If there is a k-vertex for k ∈ {3, 4, 5} then G contains a K 3 . Otherwise, check whether C together with its 0-, 1and 2-vertices fulfill all the conditions of the Structure Theorem. If not then G is not (P 6 ,K 3 )-free. Otherwise, a k-expression for G can be constructed by Corollary 3.

Conclusion

In this paper, we give a complete structure description of (prime) (P 6 ,K 3 )-free graphs. Moreover, we show that the clique-width of these graphs is bounded, and we give a robust algorithm which, for an arbitrary nonbipartite input graph G, either constructs a corresponding k-expression of G if Algorithm 1 returns a C 5 and G fulfills the conditions of the Structure Theorem or states that G does not fulfill these conditions (in which case it cannot be (P 6 ,K 3 )-free) or finds an induced P 6 or K 3 in G. The running time of this algorithm is at most O(n 2 ).

The fact that (P 6 ,K 3 )-free graphs have bounded clique-width can be extended to (P 6 ,paw)-free graphs by the following observation by Olariu [START_REF] Olariu | Paw-free graphs[END_REF]: A graph G is paw-free if and only if each component of G is either triangle-free or complete multipartite.

Moreover, in [START_REF] Olariu | On the closure of triangle-free graphs under substitution[END_REF], Olariu has observed that if a prime graph contains a triangle then it contains a house, bull or double-gem (these are the minimal prime extensions of the non-prime paw graph). Thus also (P 6 ,house,bull,double-gem)-free graphs have bounded clique-width.

It remains a challenging open problem whether there is a linear time algorithm for constructing kexpressions of (P 6 ,K 3 )-free graphs (k-expressions for (P 6 ,house,bull,double-gem)-free graphs, respectively) and whether the class of (S 1,2,3 ,K 3 )-free graphs has bounded clique-width.

Fig. 1 :

 1 Fig. 1: Forbidden configurations of Lemma 3

Theorem 5

 5 Algorithm 1 is correct and works in time O(n 2 ).Proof: Correctness: Assume that G is a nonbipartite graph andN k (v), k ≥ 1, is a hanging of G with start vertex v. Obviously, if N 5 (v) = ∅ then G contains a P 6 . Otherwise, since G is not bipartite, one of the levels N k (v), 1 ≤ k ≤ 4, contains an edge x ∼ y. Let k 0 be the smallest index k such that N k (v) contains an egde. If k 0 = 1 then G contains a K 3 ; if k = 2 then G contains a K 3 or C 5depending on the question whether x and y have a common neighbor in N (v); if k = 3 then G contains a K 3 , C 5 or P 6 depending on the criteria given in steps (5.1), (5.2) of the algorithm. Finally, if k = 4 then again G contains a K 3 , C 5 or P 6 depending on the criteria given in steps (6.1), (6.2) of the algorithm. This shows the correctness of the algorithm.Time bound:Step (1): Breadth-First Search for one start vertex v can be done in linear time O(n + m).

  a subgraph H of G, a vertex not in H is a k-vertex of H (or for H) if it has exactly k neighbors in H. We say that H has no k-vertex if there is no k-vertex for H. The subgraph H dominates the graph G if there is no 0-vertex for H in G.

  1 such that the edges between C 1 and C 2 are a matching and at most one vertex in C 1 and C 2 is not covered by the matching.• G is co-matched bipartite if G is the complement graph of a matched co-bipartite graph.If a graph is triangle-free but not bipartite, it must contain an odd cycle of length at least 5. For P 6 -free graphs, this must be a C 5 , say, C with vertices v 1 , . . . , v 5 and edges {v i , v i+1 }, i ∈ {1, . . . , 5} (throughout this paper, all index arithmetic with respect to a C 5 is done modulo 5). Obviously, in a triangle-free graph, a C 5 C has no 3-, 4and 5-vertex, and 2-vertices of C have nonconsecutive neighbors in C. Let X denote the set of 0-vertices of C, and for i ∈ {1, . . . , 5}, let Y i denote the set of 1-vertices of C being adjacent to v i , and let Z i,i+2 denote the set of 2-vertices of C being adjacent to v i and v i+2 .Moreover, let Y = Y 1 ∪ . . . ∪ Y 5 and

Acknowledgements

We are grateful to Van Bang Le for helpful discussions and to three anonymous referees for their valuable comments which lead to considerable improvements in the presentation of our results.

5 Bounded Clique-Width of (P 6 ,K 3 )-free Graphs

The P 4 -free graphs (also called cographs) play a fundamental role in graph decomposition; see [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF] for linear time recognition of cographs, [START_REF] Corneil | Complement reducible graphs[END_REF][START_REF] Corneil | Cographs: recognition, applications, and algorithms[END_REF][START_REF] Corneil | A linear recognition algorithm for cographs[END_REF] for more information on P 4 -free graphs and [START_REF] Brandstädt | Graph Classes: A Survey[END_REF] for a survey on this graph class and related ones.

For a cograph G, either G or its complement is disconnected, and the cotree of G expresses how the graph is recursively generated from single vertices by repeatedly applying join and co-join operations. Note that the cographs are those graphs whose modular decomposition tree contains only join and co-join nodes as internal nodes.

Based on the following operations on vertex-labeled graphs, namely (i) create a vertex u labeled by integer ℓ, denoted by ℓ(u),

(ii) disjoint union (i.e., co-join), denoted by ⊕, (iii) join between all vertices with label i and all vertices with label j for i = j, denoted by η i,j , and

(iv) relabeling all vertices of label i by label j, denoted by ρ i→j , the notion of clique-width cwd(G) of a graph G is defined in [START_REF] Courcelle | Handle-rewriting hypergraph grammars[END_REF] as the minimum number of labels which are necessary to generate G by using these operations. It is easy to see that cographs are exactly the graphs whose clique-width is at most two.

A k-expression for a graph G of clique-width k describes the recursive generation of G by repeatedly applying these operations using at most k different labels.

Proposition 1 ([10, 11]) (i) The clique-width cwd(G) of a graph G is the maximum of the clique-width of its prime induced

subgraphs if G has nontrivial prime subgraphs.

In [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique width[END_REF], it is shown that every problem expressible in a certain kind of Monadic Second Order Logic, called LinEMSOL(τ 1,L ), is linear-time solvable on any graph class with bounded clique-width for which a k-expression can be constructed in linear time.

Roughly speaking, MSOL(τ 1 ) is Monadic Second Order Logic with quantification over subsets of vertices but not of edges; MSOL(τ 1,L ) is the extension of MSOL(τ 1 ) with the addition of labels added to the vertices, and LinEMSOL(τ 1,L ) is the extension of MSOL(τ 1,L ) which allows to search for sets of vertices which are optimal with respect to some linear evaluation functions. Observe that, trivially, the clique-width of a graph with n vertices is at most n. The following result by Johansson gives a slightly sharper bound. Lemma 11 ([15]) If G has n vertices then cwd(G) ≤ nk as long as 2 k + 2k ≤ n.