Vanthet Ouch

Piseth Heng
email: piseth.heng@insa-rennes.fr

Quang-Huy Nguyen

Hugues Somja

Thierry Soquet

A notched connection for CLT-concrete composite slabs resisting to uplift without metallic connectors: experimental investigation

Keywords: Shear notch connectors, CLT-concrete composite slabs, Push-out tests, Flexural tests, Uplift

In search for a solution of a sustainable construction with less impact on environment while maintaining a sufficient structural performance, CLT-concrete composite slabs/beams have been increasingly proposed for medium-to-large span structures. Different types of mechanical shear connectors have been studied in the literature for these composite elements. Among them, the notch type is the most preferable due to the high shear resistance contributed by the concrete. However, steel screw or bolt is needed in the connector to limit the uplift between the timber and the concrete. In this paper, a novel type of notched connectors with a particular shape that is able to limit the uplift without the need for steel bolts is proposed. The main objective of this paper is to determine the local and global behaviours of this new shear connector by experimental investigations. Two series of experimental tests were ordered by Thierry Soquet, an architect of Architecture Plurielle and an inventor of innovative construction systems directed by Horizon Bois. A series of three symmetrical push-out tests were performed on large-scale specimens in order to determine the shear resistance, the stiffness, the deformation capacity and the failure mode of the connector. The test results have shown high shear resistance and large stiffness of the connectors. However, the ductility of the connectors is still limited, as the failure mode was governed by the shear failure of the transverse layer of the CLT. In addition, the global behaviour of the CLTconcrete slab was assessed by a series of two full-scaled flexural tests on the slab specimens under a positive bending moment. It was shown in the test results that the design of the composite slab was not limited by the flexural bearing capacity as a high value of the maximum bending moment was obtained in the tests, but governed by the deflection of the composite slab. The delay in the tests caused by the Covid crisis has moreover set in evidence the importance of the shrinkage of concrete in the total deflection.

Introduction

The high amount of carbon dioxide released to atmosphere creates serious drawbacks for concrete and steel structures. This brings back the interests of using the timber in the construction on account of environmental sustainability along with a sufficient structural performance. Timber-concrete composite members have been increasingly studied for medium-to-large span structures (e.g. [START_REF] Deam | Connections for composite concrete slab and LVL flooring systems[END_REF], [START_REF] Lukaszewska | Performance of connections for prefabricated timberconcrete composite floors[END_REF], [START_REF] Jiang | CLT-concrete composite floors with notched shear connectors[END_REF]). The global behaviour of these composite structures depends largely on the connection between the two materials. An efficient connection must ensure the transfer of shear forces between the concrete and the timber with limited slips and uplifts. Different types of mechanical shear connectors of the timber-concrete composite elements have been studied in the literature. A detailed review of these connectors is given by [START_REF] Yeoh | State of the art on timber-concrete composite structures: Literature review[END_REF]. Among them, the notch type is the most preferable in terms of high shear resistance. However, steel screws or bolts are needed in the connector to limit the uplift between the timber and the concrete, which requires tools and skills and slows down the construction process. Thierry Soquet, an architect of the Architecture Plurielle agency and a designer of the Horizons Bois building in Rennes, in collaboration with INSA Rennes developed a novel notched connector for a CLT-concrete composite slab with a particular form that is able to limit the uplift between the concrete and the CLT panels without the need for screws or bolts.

This paper presents the experimental study on the effectiveness of the proposed notched connector used in CLT-concrete composite floors by a series of three symmetrical push-out tests and two large-scale four-point bending tests.

Push-out tests

For the characterisation of a shear connection between composite members, the standard push-out test is commonly used. In this paper, symmetrical large-scale push-out tests were conducted to study the behaviour of the novel notched connection of the CLT-concrete composite slab.

Test setup

The test setup was made to conform to the push-out test given in Annex B of Eurocode 4 part 1-1 ( 2004) and EN 26891 (1991), with an adaptation to fit with the configuration of the CLT-concrete composite slab. Illustrated in Figure 1, the test setup consisted of a force jack with a capacity of 1500 kN, a loading HEB-300 steel piece, a specimen of the CLT-concrete connection and a supporting steel table. In the test setup, the specimen was placed vertically on the supporting table. The force jack applied a uniform vertical load on the top surface of the CLT block of the specimen via the HEB-300 profile while the supporting steel table provided a reaction to the reinforced concrete panels. The width of the profile (300 mm) almost covered the width of the CLT panel (330 mm) and spanned over to the concrete notches so that the loading could be as uniform as possible. In order to avoid a dangerous collapse of the specimen, four steel angles placed around the four faces of the specimen were fixed on top of the supporting steel plate by 150-mm welds in the centre of the angle. These angles were however not in contact with the specimen.

Test specimen

Three specimens (namely B1, B2 and B3) were fabricated. Each specimen was composed of two CLT panels glued to each other and placed between two reinforced concrete panels (Figure 2a). Each RC panel was connected to the CLT panel by two notched connectors. The notch connector (Figure 2b) was obtained by cutting a notch from the CLT panel. A U-shape rebar cage was put in it (Figure 2c). In the fabrication process, the concrete was casted on each CLT panel separately using the same concrete on the same day. The concrete was casted directly on the CLT panel during the fabrication of the specimen without laying plastic films nor applying any paint. After the concrete was cured, the two pieces were glued to each other at the free surface of the CLT panels (Figure 2a) using polyurethane glue. This process avoids the inconvenience of casting concrete at a different time for each concrete panel.

The dimensions of the specimens are given in Figure 3. Specimen B1 has a width of b = 500 mm whereas specimens B2 and B3 have a width of b = 400 mm. Reinforcement mesh ST15 was also placed inside the concrete panel.

Material properties

According to Annex B of Eurocode 4 part 1-1 (2004), for a preparation of the specimen in the standard push-out test, the compressive strength of the concrete at the time of testing should be 70%±10% of the specified strength of the concrete. In order to achieve this objective, the concrete at young age was used.

Based on the expressions in Eurocode 2 part 1-1 (1992) for determining the concrete strength in relation to the age of concrete, the concrete compressive strength at the age between 7 and 14 days reaches a value between 68% and 85% of the strength at 28 days.

The concrete panel had a concrete strength class of C35/40 formulated according to the norm EN 206-1, having the class of environment XF1. 2 series of three cylinder specimens with a dimension of 11×22cm were tested on the day of each push-out test using standard compressive tests for compressive strength and using Brazilian tests for tensile strength. The results are reported in Table 1. and are tensile strength of each specimen and their mean value, respectively. and are compressive strength of each specimen and their mean value, respectively. The CLT panel was made of massive wooden boards with a minimum class of C18 and a mean density of 420 kg/m 3 specified in the technical specification of the product (TOT'm X, 2020). The steel rebars have a steel grade of BST 500 S.

Instrumentation and test procedure

The compressive load, applied to the CLT panel by the force jack, was transferred to the concrete panels through concrete notches. This force was then balanced by the reaction forces provided by the supporting table.

In order to measure relative displacements between the CLT and concrete panels (slips and uplifts), the measurement using Digital Image Correlation method was adopted. In this method, a series of photos were captured during the course of the test at each increment of loading by two high resolution cameras (one at the front and the other at the back surface of the specimen). These photos were then used to employ tracking and image registration measurements of changes in the images over time. The precision determined for this test was currently ± 0.1 mm. Points were marked on the concrete and the CLT panels (see Figure 4); the change of the positions of these points was tracked and measured in order to compute the slips and uplifts. The load was applied according to the test procedure described in Annex B of Eurocode 4 part 1-1 ( 2004). With a loading rate of 1 mm/min, 25 loading/unloading cycles between 40 % and 5 % of the expected failure load were initially applied to the specimen in order to remove the friction between the concrete and CLT surfaces. The load was then monotonically increased up to failure with a loading rate of 1 mm/min. The expected failure load was (under)estimated at 400 kN for the test B1 while it was updated to 650 kN for tests B2 and B3.

Marked point

Region of interest

Results

Figure 5 shows the evolution of the force in function of the elongation of the force jack for the three tests. The maximum loads obtained for tests B1, B2 and B3 are 840 kN, 685 kN and 690 kN, respectively. In all the three tests, the failure mode was governed by a brittle shear rupture of one of the weak layers of the CLT panel, as shown in Figure 6. Figure 7 illustrates the evolution of the mean slips and the mean uplifts in function of the force per connector per meter width. The maximum value obtained from the three tests ranges between 0.8 mm and 1.6 mm for the slip and between 0.7 mm and 1 mm for the uplift. The maximum load attained per connector per meter width ( ) is 419 kN, 421 and 461 kN for test B1, B2 and B3, respectively. The mean value (µ) and the standard deviation (σ) of the maximum load for the three tests are 434 kN and 24 kN. The corresponding mean slips to the maximum force are 0.79 mm, 1.02 mm and 0.9 mm, respectively. The corresponding mean uplifts to the maximum force ( ) are 0.57 mm, 0.67 mm and 0.59 mm, respectively. While the strength of the connector is defined by the maximum load applied at failure ( ), the stiffness is quantified by slip modulus at different load levels. Based on the model proposed by [START_REF] Ceccotti | Timber-concrete composite structures[END_REF], the stiffness at service limit state (

) is determined by a secant slope of a straight line that connects the beginning of the load-slip curve to a point at 40 percent of the failure load. The stiffness at ultimate limit state ( ) is computed as equal to

. The computation of these stiffness is reported in Table 2.

Flexural tests

Four-point bending tests were applied to two large-scale specimens of the CLT-composite slab with the new notched connectors in order to validate the functioning of the connectors in real configuration, and measure the global structural response.

Specimen and test setup

Two slab specimen were fabricated. Each specimen had a dimension of 3200×6710×245mm and was composed of a CLT panel with a thickness of 165 mm connected to a reinforced concrete panel with a thickness of 85 mm by a series of 13 notched connectors (Figure 8).

The test setup consisted of a slab specimen, two supports, a force jack with a capacity of 1500 kN and a loading system to apply a four-point loading configuration (Figure 9a). In this test setup, the specimen was simply supported. It was placed on two support systems, and the load was applied vertically from the force jack onto the specimen through the loading system. The support 1 (conceptualized for supporting walls) was a linear support that gave supporting contacts to the entire width of the specimen (Figure 9b). At this support, the horizontal displacement of the CLT panel was restrained by the profile UPN 300. In test F1, the support condition was applied to fit with an actual condition, in which two point supports (conceptualized for supporting columns) placed at corners below the specimen were used for the support 2 (Figure 9c). PTFE layers were used in order to minimize the friction between the support and the CLT panel. Due to a premature shear failure of the specimen at the point supports in test F1, a linear support (Figure 9d) was adopted for the support 2 in test F2. The span between the supports and the loading positions are given in Figure 10.

Material properties

The same concrete class for concrete panels and the same wood class for the CLT panels as in pushout tests were used. Three cylinder specimens with a dimension of 11×22cm were tested on the day of each flexural test for concrete strength and reported in Table 3.

Instrumentation and loading procedure

The force generated by the hydraulic force jack was measured by an integrated double force sensors (± 500 kN and ± 1500 kN). The slips between the CLT and the concrete panels were determined by 8 LVDT sensors (4 at each side along the specimen) noted by CG1 to CG8 with a capacity of ± 2.5 mm. Four LVDT sensors with a capacity of 25 mm (CD1 to CD4) were positioned below the specimen close to the support to measure the settlement of supports for a displacement correction when computing the deflection. The positions of the sensors are given in Figure 10. Apart from the analogue sensors, three high resolution photo cameras were also installed for an analysis using digital image correlation technology (DIC). The deflection of the specimen was determined by recording the evolution of points on steel board fixed below the CLT at mid width (noted by C1 to C5). The slips (G1 and G2) and the uplifts (D1 and D2) were obtained from points on the recording areas.

The measuring positions of the areas for the DIC are presented Figure 11. Regarding the loading procedure, 25 initial loading/unloading cycles between 40 % and 5 % of the estimated failure load was applied to the specimen in order to remove the friction with a loading rate of 1 mm/min. The failure load is estimated at 403 kN. One more cycle at the estimated ultimate limit state was then performed before it was monotonically increased up to failure with a loading rate of 1 mm/min.

Influence of shrinkage effects on the deflection

The first flexural test (F1) was performed four months after the concrete casting of the specimen. This delay was due to the first period of lockdown imposed by the French government during the Covid-19 crisis. During storage, many concrete cracks (see Figure 12) were observed on the concrete panel of the specimen, which brought to light the suspicion of non-negligible effects of concrete shrinkage on the deflection. However, it was not possible to quantify the deflection caused by this effect.

It was decided later to measure the evolution of the deflection of the specimen F2 during around three months. The specimen was placed on the supports of the flexural test configuration with only the selfweight of the specimen applied on it. Laser sensor was installed at the mid-span below the specimen in order to measure the deflection over time. The specimen F2 was casted with an initial positive deflection at the mid-span of 19 mm. Figure 13 shows the evolution of the mid-span deflection over time. The deflection contributed by the shrinkage for 100 days can be vastly computed at 16 mm, being the difference between the deflections at the time of 100 days and of 0 day. This value is not negligible and calls for further investigation through a dedicated experimental campaign.

Figure 12. Specimen F1: Cracks due to shrinkage effects (dimensions in mm).

Figure 13. Specimen F2: Evolution of mid-span deflection over time.

Results of flexural tests

Figure 14 illustrates the envelop curves of the elongation evolution of the force jack and of the mid-span deflection in function of the force for both tests. The maximum force obtained for test F1 is 590 kN, corresponding to a maximum mid-span deflection of 71.40 mm. The failure mode of Test F1 was governed by a shear rupture of the concrete panel close to the point supports (Figure 15a). On the other hand, in the second test, the loading was stopped at 725 kN for security reasons when many wood layers were ruptured (Figure 15b). This was to avoid a brittle collapse of the system, as the failure seemed to be governed by the rupture of the CLT layers in tension. In addition, a large mid-span deflection of the specimen of 93 mm was already obtained (Figure 14b).

(a). Force-elongation curve. (b). Force-midspan deflection curve. Figure 14. Flexural tests: Evolution of the elongation of the force jack and the mid-span deflection.

Figure 16 represents the evolution of the slips in function of the force for both tests. The maximum slips obtained for tests F1 and F2 are 2.38 mm and 0.66 mm, respectively. The large values of the slips measured by sensors CG4 and CG5 in test F1 were relative displacements caused by shear cracks near the point supports (Figure 15a). Due to the errors in the interpretation of the DIC of G1, G2, D1 and D2 for test F1, the results are not presented here. The evolution of the uplifts by D1 and D2 for test F2 is described in Figure 17. The maximum mean uplift obtained for test F2 is 0.43 mm. It can be concluded from these results that in both tests the global response of the specimens were almost linear until the failure of the specimens.

Verification of deflection of the specimen

A simplified calculation method or "gamma method" provided in Annex B of Eurocode 5 -part 1-1, is usually adopted for the design of timber-concrete composite floors. [START_REF] Jiang | CLT-concrete composite floors with notched shear connectors[END_REF] proposed a modification of the gamma method to apply to CLT-concrete composite floor with 5-layer CLT panel.

It is interesting to verify the accuracy of this method to predict the flexural stiffness of the present CLTconcrete composite floor with the novel notched connectors. The flexural stiffness at SLS and ULS are computed with the modified gamma method using the mean value of and provided in Table 2. As illustrated in Figure 18, the gamma method predicts well the flexural stiffness of the present CLTconcrete composite floor with the new notched connectors. Load levels corresponding to a load combination for SLS and for ULS as indicated in Eurocode 2 (1992) are also given in the figure. In fact, the wood-concrete connection is very stiff compared to the effect of rolling shear within the CLT panel. It can also be seen that a small difference is obtained for the flexural stiffness when using and .

Figure 18. Flexural tests: comparison of force-deflection responses.

It is clear that the resistance of the composite floor is sufficient for the ultimate limit state design. However, with the influence of the shrinkage effects, it is needed for a service limit state verification.

Conclusion

This paper presents an experimental investigation on the behaviour of the CLT-concrete composite floor with novel notched connectors. Three symmetrical push-out tests and two full-scale four-point flexural tests were carried out in order to validate the effectiveness of the proposed notched connector in the CLT-concrete composite floor. The failure mode of all the specimens in the push-out tests was governed by the shear rupture of the weak layer of the CLT panel. The push-out test results showed high values of the shear strength and of the stiffness although low ductility was obtained. The results of the flexural tests showed the efficiency of the notched connector, as the failure mode of the specimen in test F2 was governed by the rupture of the tensile layers of the CLT, and the maximum slips and uplifts were smaller than the ultimate values obtained in the pushout tests. The modified gamma method [START_REF] Jiang | CLT-concrete composite floors with notched shear connectors[END_REF] provided a good agreement of the flexural stiffness with the experimental result. In addition, a small difference of the flexural stiffness is obtained when using the value of the stiffness and that of in the gamma method. At last, while a high bending resistance of the composite floor was obtained, the evolution of the deflection caused by the shrinkage effects requires further investigations as the deflection verification at service limit state is critical.

Figure 2 .Figure 3 .

 23 Figure 2. Pushout test: Description of test specimen (dimensions in mm). 235 187.5 375 187.5 235

Figure 4 .

 4 Figure 4. Pushout test: Zones for Digital Image Correlation method.

Figure 5 .

 5 Figure 5. Pushout test: Force-elongation curve of the force jack.

Figure 6 .

 6 Figure 6. Pushout test: Shear rupture of one of weak layers of the CLT panel.

Figure 7 .

 7 Figure 7. Pushout test: (a). Force per connector versus slips. (b). Force per connector versus uplifts.

Figure 8 .

 8 Figure 8. Flexural test: Description and dimensions of test specimen (dimensions in mm).

Figure 9 .

 9 Figure 9. Flexural test: Description of test configuration.

Figure 10 .

 10 Photo of CG1

Figure 11 .

 11 Figure 11. Areas for the DIC (dimensions in mm).

Figure 15 .Figure 16 .

 1516 Figure 15. Flexural tests: Failure of the specimen.

Figure 17 .

 17 Figure 17. Flexural tests: Evolution of uplifts in function of force for test F2.

Table 1 .

 1 Pushout tests: Concrete strength.

	Test	Age (days)	[MPa]	[MPa]	[MPa]	[MPa]
			3.16		33.82
	B1	6	3.50	3.20	34.46	34.51
			2.94		35.25
			2.80		29.31
	B2	3	2.35	2.56	28.70	29.12
			2.53		29.36
			3.72		39.73
	B3	7	3.21	3.39	38.95	39.51
			3.23		39.84

Table 2 .

 2 Shear strength and slip moduli values for one connector per one meter width.

	Test	[kN/m] µ σ	[mm] [mm]	[kN/m/m] µ	σ		[kN/m/m] µ	σ
	B1 419		0.79 0.57 1.81×10 6			1.20×10 6
	B2 421	434 24	1.02 0.67 1.38×10 6	1.49×10 6 0.28×10 6	0.92×10 6	1.00×10 6 0.18×10 6
	B3 461		0.90 0.59 1.29×10 6			0.87×10 6

Table 3 .

 3 Flexural tests: Concrete strength.

	Test	Age (days)	[MPa]	[MPa]
			56.45
	F1	120	56.33	56.60
			57.01
			56.61
	F2	147	53.25	55.35
			56.18


Marcin Pilipczuk

Ni Luh

Dewi Sintiari

Stéphan Thomassé

Nicolas Trotignon

(Theta, triangle)-free and (even hole, K 4 )-free graphs. Part 2: Bounds on treewidth

A theta is a graph made of three internally vertex-disjoint chordless paths P1 = a . . . b, P2 = a . . . b, P3 = a . . . b of length at least 2 and such that no edges exist between the paths except the three edges incident to a and the three edges incident to b. A pyramid is a graph made of three chordless paths P1 = a . . . b1, P2 = a . . . b2, P3 = a . . . b3 of length at least 1, two of which have length at least 2, vertex-disjoint except at a, and such that b1b2b3 is a triangle and no edges exist between the paths except those of the triangle and the three edges incident to a. An even hole is a chordless cycle of even length. For three non-negative integers i ≤ j ≤ k, let S i,j,k be the tree with a vertex v, from which start three paths with i, j, and k edges respectively. We denote by Kt the complete graph on t vertices.

We prove that for all non-negative integers i, j, k, the class of graphs that contain no theta, no K3, and no S i,j,k as induced subgraphs have bounded treewidth. We prove that for all non-negative integers i, j, k, t, the class of graphs that contain no even hole, no pyramid, no Kt, and no S i,j,k as induced subgraphs have bounded treewidth. To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality.

Introduction

In this article, all graphs are finite, simple, and undirected. A graph H is an induced subgraph of a graph G if some graph isomorphic to H can be obtained Figure 1: Pyramid, prism, theta, and wheel (dashed lines represent paths) from G by deleting vertices. A graph G contains H if H is an induced subgraph of G. A graph is H-free if it does not contain H. For a family of graphs H, G is H-free if for every H ∈ H, G is H-free.

A hole in a graph is a chordless cycle of length at least 4. It is odd or even according to its length (that is its number of edges). We denote by K t the complete graph on t vertices.

A theta is a graph made of three internally vertex-disjoint chordless paths P 1 = a . . . b, P 2 = a . . . b, P 3 = a . . . b of length at least 2 and such that no edges exist between the paths except the three edges incident to a and the three edges incident to b (see Fig. 1). Observe that a theta contains an even hole, because at least two paths in the theta have lengths of same parity and therefore induce an even hole.

We are interested in understanding the structure of even-hole-free graphs and theta-free graphs. Our motivation for this is explained in the first paper of this series [START_REF] Sintiari | Theta, triangle)-free and (even hole, K 4 )-free graphs. Part 1: Layered wheels[END_REF], where we give a construction that we call layered wheel, showing that the cliquewith, the rankwidth, and the treewidth of (theta, triangle)-free and (even hole, K 4 )-free graphs are unbounded. We also indicate questions, suggested by this construction, about the induced subgraphs contained in graphs with large treewidth.

In this second and last part, we prove that when excluding more induced subgraphs, there is an upper bound on the treewidth. Our results imply that the maximum independent set problem can be solved in polynomial time for some classes of graphs that are possibly of interest because they are related to several well known open questions in the field.

Results

We denote by P k the path on k vertices. For three non-negative integers i ≤ j ≤ k, let S i,j,k be the tree with a vertex v, from which start three paths with i, j, and k edges respectively. Note that S 0,0,k is a path of length k (so, is equivalent to P k+1 ) and that S 0,i,j = S 0,0,i+j . The claw is the graph S 1,1,1 . Note that {S i,j,k ; 1 ≤ i ≤ j ≤ k} is the set of all the subdivided claws and {S i,j,k ; 0 ≤ i ≤ j ≤ k} is the set of all subdivided claws and paths.

A pyramid is a graph made of three chordless paths P 1 = a . . . b 1 , P 2 = a . . . b 2 , P 3 = a . . . b 3 of length at least 1, two of which have length at least 2, vertex-disjoint except at a, and such that b 1 b 2 b 3 is a triangle and no edges exist between the paths except those of the triangle and the three edges incident to a (see Fig. 1).

We do not not recall here the definition of treewidth and cliquewidth. They are parameters that measure how complex a graph is. See [START_REF] Harvey | Parameters tied to treewidth[END_REF][START_REF] Dabrowski | Clique-width for hereditary graph classes[END_REF] for surveys about them.

Our main result states that for every fixed non-negative integers i, j, k, t, the following graph classes have bounded treewidth:

• (theta, triangle, S i,j,k )-free graphs;

• (even hole, pyramid, K t , S i,j,k )-free graphs.

The exact bounds and the proofs are given in Section 4 (Theorems 4.6 and 4.7). In fact, the class on which we actually work is larger. It is a common generalization C of the graphs that we have to handle in the proofs for the two bounds above. Also, we do not exclude S i,j,k , but some graphs that contain it, the so-called l-span-wheels for sufficiently large l. We postpone the definitions of C and of span wheels to Section 4.

To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality. Let us define them.

For two vertices

s, t ∈ V (G), a set X ⊆ V (G) is an st-separator if s, t / ∈ X and s and t lie in different connected components of G \ X. An st-separator X is a minimal st-separator if it is an inclusion-wise minimal st-separator. A set X ⊆ V (G) is a separator if there exist s, t ∈ V (G) such that X is an st-separator in G. A set X ⊆ V (G) is a minimal separator if there exist s, t ∈ V (G) such that X is a minimal st-separator in G.
Our graphs have no large cliques by definition, and by studying their structure, we prove that they cannot contain large minimal separators, implying that their treewidth is bounded.

Note that from the celebrated grid-minor theorem, it is easy to see that every graph of large treewidth contains a subgraph with a large minimal separator (a column in the middle of the grid contains such a separator). But since we are interested in the induced subgraph containment relation, we cannot delete edges and we have to rely on our reinforcement.

Treewidth and cliquewidth of some classes of graphs

We now survey results about the treewidth in classes of graphs related to the present work. Complete graphs provide trivial examples of even-hole-free graphs of arbitrarily large treewidth. In [START_REF] Cameron | Structure and algorithms for (cap, even hole)-free graphs[END_REF], it is proved that (even hole, triangle)free graphs have bounded treewidth (this is based on a structural description from [START_REF] Conforti | Triangle-free graphs that are signable without even holes[END_REF]). In [START_REF] Cameron | On the structure of (pan, even hole)-free graphs[END_REF], it is proved that for every positive integer t, (even hole, pan, K t )-free graphs have bounded treewidth (where a pan is any graph that consists of a hole and a single vertex with precisely one neighbor on the hole). It is proved in [START_REF] Sintiari | Theta, triangle)-free and (even hole, K 4 )-free graphs. Part 1: Layered wheels[END_REF] that the treewidth of (theta, triangle)-free graphs and (even hole, pyramid, K 4 )-free graphs are unbounded. Growing the treewidth in [START_REF] Sintiari | Theta, triangle)-free and (even hole, K 4 )-free graphs. Part 1: Layered wheels[END_REF] Figure 2: A subdivision of a wall and its line graph requires introducing in the graph a large clique minor and vertices of large degree. It is therefore natural to ask whether these two conditions are really needed, and the answer is yes for both of them, because in [START_REF] Aboulker | Trotignon On the tree-width of even-hole-free graphs[END_REF] it is proved that even-hole-free graphs with no K t -minor have bounded treewidth, and in [START_REF] Abrishami | Even-hole-free graphs with bounded degree have bounded treewidth[END_REF] it is proved that even-hole-free graphs with maximum degree t have bounded treewidth.

Since having bounded cliquewidth is a weaker property than having bounded treewidth but still has nice algorithmic applications, we survey some results about the cliquewidth in classes related to the present work.

It is proved in [START_REF] Cameron | Structure and algorithms for (cap, even hole)-free graphs[END_REF] that (even hole, cap)-free graphs with no clique separator have bounded cliquewidth (where a cap is any graph that consists of a hole and a single vertex with precisely two adjacent neighbors on the hole, and a clique separator is a separator that is a clique). It is proved in [START_REF] Sintiari | Theta, triangle)-free and (even hole, K 4 )-free graphs. Part 1: Layered wheels[END_REF], that (triangle, theta)-free and (even hole, pyramid, K 4 )-free graphs have unbounded cliquewidth. It is proved in [START_REF] Adler | On rank-width of even-hole-free graphs[END_REF], that (even hole, diamond)-free graphs with no clique separator have unbounded cliquewidth (the diamond is the graph obtained from K 4 by deleting an edge). The construction can be easily extended to (even hole, pyramid, diamond)-free graphs as explained in [START_REF] Chudnovsky | Computing maximum stable sets in (pyramid, even hole)-free graphs[END_REF]. It is easy to provide (theta, K 4 , S 1,1,1 )-free graphs (or equivalently (claw, K 4 )-free graphs) of unbounded cliquewidth. To do so, consider a wall W , subdivide all edges to obtain W , and take the line graph L(W ) (see [START_REF] Sintiari | Theta, triangle)-free and (even hole, K 4 )-free graphs. Part 1: Layered wheels[END_REF] for a definition and Fig. 2).

The results mentioned in this paragraph are extracted from [START_REF] Dabrowski | Clique-width of graph classes defined by two forbidden induced subgraphs[END_REF] (but some of them were first proved in other works). Let H U = {P 7 , S 1,1,4 , S 2,2,2 } and H B = {P 6 , S 1,1,3 }. If H contains a graph from H U as an induced subgraph, then the class of (triangle, H)-free graph has unbounded cliquewidth (see Theorem 7.ii.6 in [START_REF] Dabrowski | Clique-width of graph classes defined by two forbidden induced subgraphs[END_REF]). If H is contained in a graph from H B , then the class of (triangle, H)-free graphs has bounded cliquewidth (see Theorem 7.i.3 in [START_REF] Dabrowski | Clique-width of graph classes defined by two forbidden induced subgraphs[END_REF]).

The cliquewidth of (triangle, S 1,2,2 )-free graphs is bounded, see [START_REF] Brandstädt | Bounded clique-width of (s 1,2,2 , triangle)-free graphs[END_REF] or [START_REF] Dabrowski | Colouring diamond-free graphs[END_REF].

Algorithmic consequences

It is proved in [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF] that in every class of graphs of bounded treewidth, many problems can be solved in polynomial time. Our result has therefore applications to several problems, but we here focus on one because the induced subgraphs that are excluded in the most classical results and open questions about it seem to be related to our classes. An independent set in a graph is a set of pairwise non-adjacent vertices. Our results imply that computing an independent set of maximum cardinality can be performed in polynomial time for (theta, triangle, S i,j,k )-free graphs and (even hole, pyramid, K t , S i,j,k )-free graphs.

Finding an independent set of maximum cardinality is polynomial time solvable for (even hole, triangle)-free graphs [START_REF] Cameron | Structure and algorithms for (cap, even hole)-free graphs[END_REF] and (even hole, pyramid)-free graphs [START_REF] Chudnovsky | Computing maximum stable sets in (pyramid, even hole)-free graphs[END_REF]. Its complexity is not known for (even hole, K 4 )-free graphs and for (theta, triangle)-free graphs. Determining its complexity is also a well known question for S i,j,k -free graphs. It is NP-hard for the class of H-free graphs whenever H is not an induced subgraph of some S i,j,k [START_REF] Alekseev | On the local restrictions effect on the complexity of finding the graph independence number[END_REF]. It is solvable in polynomial time for H-free graphs whenever H is contained in P k for k = 6 (see [START_REF] Lokshantov | Independent set in P 5 -free graphs in polynomial time[END_REF] for H = P 5 and [START_REF] Grzesik | Polynomialtime algorithm for maximum weight independent set on P 6 -free graphs[END_REF] for H = P 6 ) or contained in S i,j,k with (i, j, k) ≤ (1, 1, 2) (see [START_REF] Alekseev | Polynomial algorithm for finding the largest independent sets in graphs without forks[END_REF] and [START_REF] Lozin | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph[END_REF] for the weighted version). It is solvable in polynomial time for (P 7 , triangle)-free graphs [START_REF] Brandstädt | Maximum weight independent sets for (P 7 , triangle)-free graphs in polynomial time[END_REF] and for (S 1,2,4 , triangle)-free graphs [START_REF] Brandstädt | Maximum weight independent sets for (S 1,2,4 , triangle)-free graphs in polynomial time[END_REF]. The complexity is not known for H-free graphs whenever H is some S i,j,k that contains either P 7 , S 1,1,3 , or S 1,2,2 .

Bounding the number of minimal separators

One possible method to find maximum weight independent sets for a class of graphs is by proving that every graph in the class has polynomially many minimal separators (where the polynomial is in the number of vertices of the graph). This was for instance successfully applied to (even hole, pyramid)-free graphs in [START_REF] Chudnovsky | Computing maximum stable sets in (pyramid, even hole)-free graphs[END_REF]. Therefore, our result on (even hole, pyramid, K t , S i,j,k )-free graphs does not settle a new complexity result for the Maximum Independent Set problem (but it still can be applied to other problems).

Note that bounding the number of minimal separators cannot be applied to (even hole, K 4 )-free graphs and to (theta, triangle)-free graphs since there exist graphs in both classes that contain exponentially many minimal separators. These graphs are called k-turtle and k-ladder, see Fig 3 . It is straightforward to check that they have exponentially many minimal separators (the idea is that a separator can be built by making a choice in each horizontal edge, and there are k of them). Moreover, k-turtles are (theta, triangle)-free (provided that the outer cycle is sufficiently subdivided) and k-ladders are (even hole, K 4 )-free.

Open questions

It is not known whether (even hole, K 4 , diamond)-free graphs have bounded treewidth (or cliquewidth). Also, for every fixed integer t ≥ 4, it is not known whether (theta, triangle)-free graphs of maximum degree t have bounded treewidth (for t = 1, 2, the treewidth is trivially bounded and for t = 3 it follows from Corollary 4.3 in [START_REF] Aboulker | Trotignon On the tree-width of even-hole-free graphs[END_REF]). It is not known whether (triangle, S 1,2,3 )-free graphs have bounded cliquewidth, see [START_REF] Dabrowski | Colouring diamond-free graphs[END_REF] for other open problems of the same flavor.

. . .

figTTF2-2.pdf

Outline of the paper

In Section 2, we explain our method to bound the treewidth. In Section 3, we give two technical lemmas that highlight structural similarities between (theta, triangle)-free and (even hole, pyramid)-free graphs. These will be used in Section 4 where we prove that graphs in our classes do not contain minimal separators of large cardinality, implying that their treewidth is bounded.

Notation

By path we mean chordless (or induced) path. When a and b are vertices of a path P , we denote by aP b the subpath of P with ends a and b.

When A, B ⊆ V (G), we denote by N B (A) the set of vertices from B \ A that have at least one neighbor in A and N (A) means N V (G) (A). Note that N B (A) is disjoint from A. We write N (a) instead of N ({a}) and N [a] for {a} ∪ N (a). We denote by G[A] the subgraph of G induced by A. To avoid too heavy notation, since there is no risk of confusion, when H is an induced subgraph of G, we write N H instead of N V (H) .

A vertex x is complete (resp. anticomplete) to A if x / ∈ A and x is adjacent to all vertices of A (resp. to no vertex of A). We say that A is complete (resp. anticomplete) to B if every vertex of A is complete (resp. anticomplete) to B (note that this means in particular that A and B are disjoint).

Treewidth and minimal separators

If a graph has large treewidth, then it contains some sub-structure that is highly connected in some sense (grid minor, bramble, tangle, see [START_REF] Harvey | Parameters tied to treewidth[END_REF]). Theorem 2.1 seems to be a new statement of that kind. It says that graphs of large treewidth must contain either a large clique or a minimal separator of large size. However, its converse is false, as shown by K 2,t that has treewidth 2 (it is a series-parallel graph) and contains a minimal separator of size t.

A variant of the following theorem can be obtained from the celebrated excluded grid theorem of Robertson and Seymour. The idea is to use a large grid to obtain a large minimal separator. But there are technicalities because we are not allowed to delete edges, so the grid might contain many crossing edges. To find two vertices that cannot be separated by a small separator, one needs to clean the grid. We do not include the details since the following provides a better bound.

Theorem 2.1. Let G be a graph and let k ≥ 2 and s ≥ 1 be positive integers. If G does not contain a clique on k vertices nor a minimal separator of size larger than s, then the treewidth of G is at most (k -1)s 3 -1.

Before proving Theorem 2.1, let us introduce some terminology and state results due to Bouchitté and Todinca [START_REF] Bouchitté | Treewidth and minimum fill-in: Grouping the minimal separators[END_REF]. For a graph G we denote by cc(G) the set of all connected components of G (viewed as subsets of

V (G)). A set F ⊆ V (G) 2 \ E(G) is a fill-in or chordal completion if G + F = (V (G), E(G) ∪ F ) is a chordal graph. A fill-in F is minimal if it is inclusion-wise minimal. If X ⊆ V (G), then every connected component D ∈ cc(G \ X) with N (D) = X is called a component full to X. Observe that a set X ⊆ V (G)
is a minimal separator if and only if there exist at least two connected components of G \ X that are full to X. An important property of minimal separators is that no new minimal separator appears when applying a minimal fill-in. Lemma 2.2 (see [START_REF] Bouchitté | Treewidth and minimum fill-in: Grouping the minimal separators[END_REF]). For every graph G, minimal fill-in F , and minimal separator X in G + F , X is a minimal separator in G as well. Furthermore, the families of components cc((G + F ) \ X) and cc(G \ X) are equal (as families of subsets of V (G)).

A set Ω ⊆ V (G) is a potential maximal clique (PMC) if there exists a minimal fill-in F such that Ω is a maximal clique of G + F . A PMC is surrounded by minimal separators. Lemma 2.3 (see [START_REF] Bouchitté | Treewidth and minimum fill-in: Grouping the minimal separators[END_REF]). For every PMC Ω in G and every component D ∈ cc(G\ Ω), the set N (D) is a minimal separator in G with D being a full component.

The following characterizes PMCs.

Theorem 2.4 (see [START_REF] Bouchitté | Treewidth and minimum fill-in: Grouping the minimal separators[END_REF]). A set Ω ⊆ V (G) is a PMC in G if and only if the following two conditions hold:

(i) for every D ∈ cc(G \ Ω) we have N (D) Ω; (ii) for every x, y ∈ Ω either x = y, xy ∈ E(G), or there exists D ∈ cc(G \ Ω) with x, y ∈ N (D).
In the second condition of Theorem 2.4, we say that a component D covers the nonedge xy. Lemma 2.5. Let G be a graph, k ≥ 2 and s ≥ 1 be integers, and let Ω be a PMC in G with |Ω| > (k -1)s 3 . Then there exists in G either a clique of size k or a minimal separator of size larger than s.

Proof. By Lemma 2.3, we may assume that for every D ∈ cc(G \ Ω) we have

|N (D)| ≤ s.
Assume first that for every x ∈ Ω the set of non-neighbors of x in Ω (i.e., Ω \ N [x]) is of size less than s 3 . Let A 0 = Ω and consider the following iterative process. Given A i for i ≥ 0, pick x i ∈ A i , and set A i+1 = A i ∩ N (x i ). The process terminates when A i becomes empty. Clearly, the vertices x 0 , x 1 , . . . induce a clique. Furthermore, by our assumption, |A i \ A i+1 | ≤ s 3 . Therefore this process continues for at least k steps, giving a clique of size k in G.

Thus we are left with the case when there exists x ∈ Ω with the set Ω

\ N [x] of size at least s 3 . Let Y = {x} ∪ (Ω \ N [x]); we have |Y | > s 3 , Y ⊆ Ω, and G[Y ] is disconnected.
Consider the following iterative process. At step i, we will maintain a partition A i of Y into at least two parts and for every A ∈ A i a set D i (A) ⊆ cc(G\Ω) with the following property: the sets

{A ∪ D∈Di(A) D | A ∈ A i } is the parti- tion of G[Y ∪ A∈Ai D∈Di(A) D] into vertex sets of connected components. In particular, for every A ∈ A i and D ∈ D i (A) we have N (D) ∩ Y ⊆ A. We start with A 0 = cc(G[Y ]) and D 0 (A) = ∅ for every A ∈ A 0 .
The process terminates when there exists A ∈ A i of size larger than s 2 . Otherwise, we perform a step as follows. Pick two distinct A, B ∈ A i and vertices

a ∈ A, b ∈ B. By the properties of A i , ab / ∈ E(G). By Theorem 2.4, there exists D ∈ cc(G\Ω) with a, b ∈ N (D). Let A = {C ∈ A i | N (D)∩C = ∅}. Note that A, B ∈ A. Furthermore, since |N (D)| ≤ s, we have 2 ≤ |A| ≤ s.
We define

A i+1 = (A i \ A) ∪ { C∈A C}. For every C ∈ A i+1 ∩ A i we keep D i+1 (C) = D i (C). Furthermore, we set D i+1 ( C∈A C) = {D} ∪ C∈A D i (C).
It is straightforward to verify the invariant for A i+1 and D i+1 . Furthermore, since every set C ∈ A i is of size at most s 2 while |Y | > s 3 we have that

|A i | > s. Since 2 ≤ |A| ≤ s, we have 2 ≤ |A i+1 | < |A i |.
Consequently, the process terminates after a finite number of steps with A i of size at least 2, D i , and some A ∈ A i of size greater than s 2 .

Let

X = A ∪ D∈Di(A) D and let y ∈ Y \ A. Note that G[X]
is connected by the invariant on A i and D i , y exists as |A i | ≥ 2, and y is anticomplete to X. We use Theorem 2.4: for every a ∈ A fix a component

D a ∈ cc(G \ Ω) covering the nonedge ya. Since |N (D a )| ≤ s while |A| > s 2 , the set D = {D a | a ∈ A} is of size greater than s. Since G[X]
is connected and y is anticomplete to X, there exists a minimal separator S with y in one full side and X in the other full side. However, then S ∩ D = ∅ for every D ∈ D. Hence, |S| ≥ |D| > s. This finishes the proof of the lemma.

Proof of Theorem 2.1.

Let G be a graph such that it does not contain a clique on k vertices and a minimal separator of size larger than s. Let F be a minimal chordal completion of G. By Lemma 2.5, every maximal clique of G + F is of size at most (k -1)s 3 . Therefore a clique tree of G + F is a tree decomposition of G of width at most (k -1)s 3 -1, as desired.

Nested 2-wheels

Let k ≥ 0 be an integer. A k-wheel is a graph formed by a hole H called the rim together with a set C of k vertices that are not in V (H) called the centers, such that each center has at least three neighbors in the rim. We denote such a k-wheel by (H, C). Observe that a 0-wheel is a hole. A 1-wheel is called a wheel (see Fig. 1). We often write (H, u) instead of (H, {u}).

A 2-wheel (H, {u, v}) is nested if H contains two vertices a and b such that all neighbors of u in H are in one path of H from a to b, while all the neighbors of v are in the other path of H from a to b. Observe that a and b may be adjacent to both u and v. As we will see in this section, the properties of 2wheels highlight structural similarities between (theta, triangle)-free graphs and (even hole, pyramid)-free graphs, in the sense that in both classes, apart from few exceptions, every 2-wheel with non-adjacent centers is nested.

For a center u of a k-wheel (H, C), a u-sector of H is a subpath of H of length at least 1 whose ends are adjacent to u and whose internal vertices are not. However, a u-sector may contain internal vertices that are adjacent to v for some center v = u. Observe that for every center u, the rim of a wheel is edgewise partitioned into its u-sectors.

In (theta, triangle)-free graphs

The cube is the graph formed from a hole of length 6, say h 1 h 2 • • • h 6 h 1 together with a vertex u adjacent to h 1 , h 3 , h 5 and a vertex v non-adjacent to u and adjacent to h 2 , h 4 , h 6 . Note that the cube is a non-nested 2-wheel with nonadjacent centers. Proof. Suppose that W is not a nested wheel. We will prove that W is the cube.

Claim 1. Every u-sector of H contains at most one neighbor of v and every v-sector of H contains at most one neighbor of u.

Proof of Claim 1. For otherwise, without loss of generality, some u-sector P = x . . . y of H contains at least two neighbors of v. Let x , y be neighbors of v closest to x, y respectively along P . Note that x y / ∈ E(G) because G is triangle-free. Since W is not nested, H \ P contains some neighbors of v. Note also that H \ P contains some neighbors of u.

So, let Q = z . . . z be the path of H \ P that is minimal length and such that uz ∈ E(G) and vz ∈ E(G). Note that z is adjacent to either x or y, for otherwise uzQz v, uxP x v, and uyP y v form a theta from u to v. So suppose up to symmetry that z is adjacent to y. So, v is not adjacent to y since G is triangle-free. It then follows that the three paths vz y, vy P y, and vx P xuy form a theta, a contradiction. This proves Claim 1.

Claim 2. u and v have no common neighbors in H.

Proof of Claim 2. Otherwise, let x be such a common neighbor. Consider a subpath x . . . y of H of maximum length with the property of being a u-sector or a v-sector, and suppose up to symmetry that it is a u-sector. By its maximality, it contains a neighbor of v different from x. So in total it contains at least two neighbors of v, a contradiction to Claim 1. This proves Claim 2.

Claim 1 and 2 prove that |N H (u)| = |N H (v)| and the neighbors of u and v alternate along H. So, let x, y, z ∈ N H (u) and x , y , z ∈ N H (v) be distinct vertices in H with x, x , y, y , z, z appearing in this order along H. If V (H) = {x, y, z, x , y , z }, then V (H) ∪ {u, v} induces the cube, so suppose {x, y, z, x , y , z } V (H). Hence, up to symmetry, we may assume that x, x , y, y , z and z are chosen such that: xz / ∈ E(G). But then the three paths vz (H \ x)z, vy (H \ y)z, and vx (H \ y)xuz form a theta, a contradiction.

The following lemma of Radovanović and Vušković shows that the presence of the cube in a (theta, triangle)-free graph entails some structure. Lemma 3.2 (see [START_REF] Radovanović | A class of three-colorable triangle-free graphs[END_REF]). Let G be a (theta, triangle)-free graph. If G contains the cube, then either it is the cube, or it has a clique separator of size at most 2.

In even-hole-free graphs

Let us consider a classical generalization of even-hole-free graphs.

A prism is a graph made of three vertex-disjoint chordless paths P 1 = a 1 . . . b 1 , P 2 = a 2 . . . b 2 , P 3 = a 3 . . . b 3 of length at least 1, such that a 1 a 2 a 3 and b 1 b 2 b 3 are triangles and no edges exist between the paths except those of the two triangles (see Fig. 1). An even wheel is a wheel (H, u) such that u has an even number of neighbors in H. A square is a hole of length 4.

It is easy to see that all thetas, prisms, even wheels, and squares contain even holes. The class of (theta, prism, even wheel, square)-free graphs is therefore a generalization of even-hole-free graphs that capture the structural properties that we need here.

A proof of the following lemma can be found in [START_REF] Chudnovsky | Computing maximum stable sets in (pyramid, even hole)-free graphs[END_REF] (where it relies on many lemmas). We include here our self-contained proof for the sake of completeness. Call a wheel proper if it is not pyramid. A cousin wheel is a 2-wheel made of a hole H = h 1 h 2 . . . h n h 1 and two non-adjacent centers u and v, such that

N H (u) = {h 1 , h 2 , h 3 } and N H (v) = {h 2 , h 3 , h 4 }. Lemma 3.3.
Let G be a (theta, prism, pyramid, even wheel, square)-free graph.

If W = (H, {u, v}) is a 2-wheel in G such that uv / ∈ E(G), then W is either a nested or a cousin wheel. Moreover, if W is nested then |N H (u) ∩ N H (v)| ≤ 1.
Proof. In the case where W = (H, {u, v}) is nested, it must be that |N H (u) ∩ N H (v)| ≤ 1, for otherwise G would contain a square. Since G contains no even wheel, it is sufficient to consider the following cases.

Case 1: N H (u) = 3 or N H (v) = 3.
Assume that W is not a nested wheel. We will prove that W is a cousin wheel. Without loss of generality, we may assume that |N H (u)| = 3, and let N H (u) = {x, y, z}. We denote by P x = y . . . z, P y = x . . . z and P z = x . . . y the three u-sectors of H.

Suppose xyz is a path of H. Then v must be adjacent to y, for otherwise W is nested, a contradiction. Since V (H) ∪ {u} and V (H \ y) ∪ {u, v} do not induce an even wheel, v has exactly two neighbors in P y . Moreover, the two neighbors of v in P y are adjacent, for otherwise H \ y, u, and v form a theta. Since (H, v) is not a pyramid, this means that one of x or z is a neighbor of v. Therefore, W is a cousin wheel. Now suppose that {x, y, z} does not induce a path. So xy, yz, and zx are non-edges. Note that v is adjacent to at most one of x, y, or z, because G contains no square. Up to symmetry, assume that vx / ∈ E(G). Let R be the v-sector of H which contains x (in its interior). Since (H, {u, v}) is not a nested wheel, the ends of R are not both in P x , or both in P y , or both in P z . So assume that R = y . . . z with z is in the interior of P z and y is not in P z . If y is in P x , then R, u, and v form a theta from x to z, a contradiction. Hence, y is not in P x , so y is in the interior of P y .

Call x the neighbor of v in H different from y and z . If x is not in the interior of P x , then P x is contained in the v-sector x Hz . Thus, there exists a v-sector S which contains P x . In particular, the hole made of S and v contains two non adjacent neighbors of u, namely y and z. Hence, S, u, and v form a theta from y to z. So, x is in the interior of P x .

This means x, y , z, x , y, z appear in this order along H. If x z / ∈ E(G), then the paths x (H \ y)z, x (H \ z)yuz, and x vy (H \ x)z form a theta from x to z, a contradiction. So, x z ∈ E(G). By symmetry, x y ∈ E(G). But then, {u, y, x z} induces a square, a contradiction.

Case 2: N H (u) ≥ 5 and N H (v) ≥ 5 For a contradiction, suppose that (H, {u, v}) is not a nested wheel. First of all, we have N H (u) = N H (v), for otherwise u, v, and two non-adjacent vertices of N H (u) would form a square. So in H, there exists a neighbor of v that is not adjacent to u. It is therefore well defined to consider the u-sector P = x . . . y of H whose interior contains k ≥ 1 neighbors of v, and to choose such a sector with k minimum. We denote by x the neighbor of x in H \ P , by y the neighbor of y in H \ P and by Q = x . . . y the path H \ P .

Note that u has some neighbor in the interior of Q, because u has at least 5 neighbors in H. We now show that v also has some neighbor in the interior of Q. Suppose that it is not the case. Then, the neighborhood of v in H is completely contained in V (P )∪{x , y }. Since (H, {u, v}) is not a nested wheel, v is adjacent to x or y -and in fact to both of them, for otherwise the hole uxP yu would contain an even number (at least 4) of neighbors of v, thus inducing an even wheel, a contradiction. Now since {u, v, x, y} does not induce a square, up to symmetry we may assume that vx / ∈ E(G). Since |N H (v)| ≥ 5, v has at least 2 neighbors in the interior of P , and so k ≥ 2. Note that u is adjacent to x , for otherwise, x would be the unique neighbor of v in the interior of a u-sector, contradicting the minimality of k. Since {u, v, x , y } does not induce a square, we know that u is not adjacent to y . But then, y is the unique neighbor of v in the interior of some u sector, a contradiction to the minimality of k. This proves that v has some neighbor in the interior of Q.

By the fact that each of u and v has some neighbor in the interior of Q, a path S from u to v whose interior is in the interior of Q exists. Let x (resp. y ) be the neighbor of v in P closest to x (resp. y) along P . If x = y , then x is an internal vertex of P , and so S and P form a theta from u to x . If x y ∈ E(G), then S and P form a pyramid. If x = y and x y / ∈ E(G), then S, uxP x v, and uyP y v form a theta from u to v. Each of the cases yields a contradiction; this completes the proof.

Bounding the treewidth

In this section, we prove that the treewidth is bounded in (theta, triangle, S i,j,k )-free graphs and in (even hole, pyramid, K t , S i,j,k )-free graphs.

For (theta, triangle)-free graphs, by Lemma 3.2, we may assume that the graphs we work on are cube-free since the cube itself has small treewidth, and clique separators of size at most 2 in some sense preserve the treewidth (this will be formalized in the proofs). For (even hole, pyramid)-free graphs, recall that we work from the start in a superclass, namely (theta, prism, pyramid, even wheel, square)-free graphs.

Since our proof is the same for (theta, triangle, S i,j,k )-free graphs and (even hole, pyramid, K t , S i,j,k )-free graphs, to avoid duplicating it, we introduce a class C that contains all the graphs that we need to consider while entailing the structural properties that we need.

Call butterfly a wheel (H, v) such that N H (v) = {a, b, c, d} with ab ∈ E(G), bc / ∈ E(G), cd ∈ E(G) and da / ∈ E(G). Let C be the class of all (theta, prism, pyramid, butterfly)-free graphs such that every 2-wheel with non-adjacent centers is either a nested or a cousin wheel. Lemma 4.1. If G is a (theta, triangle, cube)-free graph or a (theta, prism, pyramid, even wheel, square)-free graph, then G ∈ C.

Proof. If G is a (theta, triangle, cube)-free graph, then G is theta-free and (prism, pyramid, butterfly)-free (because prisms, pyramids, and butterflies contain triangles). Furthermore, every 2-wheel with non-adjacent centers is a nested wheel by Lemma 3.1.

If G is a (theta, prism, pyramid, even wheel, square)-free graph, then G is (theta, prism, pyramid)-free and butterfly-free (because a butterfly is an even wheel). Furthermore, every 2-wheel with non-adjacent centers is either a nested or a cousin wheel by Lemma 3.3.

Hence G ∈ C as claimed.

For our proof, we need a special kind of k-wheel. A k-span-wheel is a k-wheel (H, C) that satisfies the following properties.

• There exist two non-adjacent vertices x, y in H and we denote by P A = a 1 . . . a α and P B = b 1 . . . b β the two paths of H from x to y, with x = a 1 = b 1 and y = a α = b β .

• C ∪ {x, y} is an independent set.

• There exists an ordering of vertices in

C, namely v 1 , v 2 , • • • , v k .
• Every vertex of C has neighbors in the interiors of both P A and P B (and at least 3 neighbors in H since (H, C) is a k-wheel).

• For every 1

≤ i < j ≤ k and 1 ≤ i , j ≤ α, if v i a i ∈ E(G) and v j a j ∈ E(G) then i ≤ j . • For every 1 ≤ i < j ≤ k and 1 ≤ i , j ≤ β, if v i b i ∈ E(G) and v j b j ∈ E(G) then i ≤ j .
Informally, a k-span-wheel is such that, walking from x to y along both P A and P B , one first meets all the neighbors of v 1 , then all neighbors of v 2 , and so on until v k . Observe that a 1-span-wheel is a wheel, 2-span-wheel is a nested 2-wheel. Note that distinct v i and v j may share common neighbors on H (it is even possible that

N P A (v 1 ) = • • • = N P A (v k ) = {a i }).
Observe that in the following theorem, thetas, pyramids, prisms, and butterflies have to be excluded, since they do not satisfy the conclusion. Lemma 4.2. Let G be a graph in C. Let C be a minimal separator in G of size at least 2 that is furthermore an independent set, and A and B be components of G \ C that are full to C. Then:

1. There exist two vertices x and y in C, a path P A from x to y with interior in A, and a path P B from x to y with interior in B such that all vertices in C \ {x, y} have neighbors in the interior of both P A and P B . Note that V (P A ) ∪ V (P B ) induces a hole that we denote by H.

(H, C

\ {x, y}) is a (|C| -2)-span-wheel.
Proof. We first prove 1, by induction on k = |C|. If k = 2, then x, y, P A , and P B exist from the connectivity of A and B, and the conditions on C \ {x, y} vacuously hold. So suppose the result holds for some k ≥ 2, and let us prove it for k + 1. Let z be any vertex from C, and apply the induction hypothesis to C \ z in G \ z. This provides two vertices x, y in C \ z and two paths P A and P B . We denote by H the hole formed by P A and P B .

Claim 1. Every vertex in C \ {x, y, z} has neighbors in the interior of both P A and P B .

Proof of Claim 1. Follows directly from the induction hypothesis. This proves Claim 1.

Since z has a neighbor in A and A is connected, there exists a path Q A = z . . . z A in A ∪ {z}, such that z A has a neighbor in the interior of P A . A similar path Q B exists. We set Q = z A Q A zQ B z B . We suppose that x, y, P A , P B , Q A , and Q B are chosen subject to the minimality of Q.

Observe that Q is a chordless path by its minimality and the fact that A and B being anticomplete. The minimality of Q implies that the interior of Q is anticomplete to the interior of P A and to the interior of P B .

Claim 2. We may assume that Q has length at least 1.

Proof of Claim 2. Otherwise, z = z A = z B , so z has neighbors in the interior of both P A and P B . Hence, by Claim 1, x, y, P A , and P B satisfy 1. This proves Claim 2.

Let a (resp. a ) be the neighbor of z A in P A closest to x (resp. to y) along P A . Let b (resp. b ) be the neighbor of z B in P B closest to x (resp. to y) along P B .

Claim 3. If a = a and aa / ∈ E(G), then z = z A . If b = b and bb / ∈ E(G), then z = z B .
Proof of Claim 3. We give a proof only for the statement of a, since the proof for b is similar.

For suppose a = a , aa / ∈ E(G), and z = z A , let z be the neighbor of z A in Q. Set P A = xP A az a a P A y and Q = z Qz B . Let us prove that x, y, P A , P B , and Q contradict the minimality of Q. Obviously, Q is shorter than Q, so we only have to prove that every vertex in C \ {z} has neighbors in the interior of both P A and P B . For P B , it follows from Claim 1. So suppose for a contradiction that a vertex c ∈ C \ {z} has no neighbor in the interior of P A . Since by Claim 1 c has a neighbor c in the interior of P A , c is an internal vertex of aP A a . Since G is theta-free, (H, z A ) is a wheel. Note that (H, {c, z A }) is not nested because of c and some neighbor of c in the interior of P B (i.e. the neighborhood of c in H is not contained in a unique z A -sector). Since G ∈ C, by Lemma 3.3, (H, {c, z A }) is a cousin wheel. Since c has neighbors in the interiors of both P A and P B , this means that x or y is a common neighbor of c and z A , a contradiction to C being an independent set. The proof for the latter statement (with b) is similar. This proves Claim 3. Claim 4. We may assume that x has neighbors in the interior of Q and y has no neighbor in the interior of Q.

Proof of Claim 4. We show that if it is not the case, then there is a contradiction. For suppose both x and y have a neighbor in the interior of Q, then a path of minimal length from x to y with interior in the interior of Q form a theta together with P A and P B , a contradiction. Now suppose that none of x and y has a neighbor in the interior of Q. Recall that Claim 2 tells us that z A = z B . So either z = z A or z = z B . Up to symmetry, we may assume that z = z A . Hence by Claim 3, either a = a or aa ∈ E(G). So, each case leads to a contradiction. Hence, exactly one of x or y has neighbors in the interior of Q, and up to symmetry we may assume it is x. This proves Claim 4. Proof of Claim 5. First, suppose z A is adjacent to x, i.e. a = x. Then, z A = z since C is an independent set. Note that a = a is impossible since z A has neighbors in the interior of P A . So, by Claim 3, a x ∈ E(G). Now suppose z A is not adjacent to x. By Claim 4, x has a neighbor in the interior of Q, so we choose such a neighbor x closest to z A along Q. Note that by the minimality of Q, no vertex in the interior of Q has neighbor in the interior of P A and in the interior of P B . Since y is not adjacent to x (by Claim 4), x has no neighbors in (P A ∪ P B ) \ {x}. We set R = xx Qz A and observe that R has length at least 2. If a = a and aa / ∈ E(G), then xP A az A , xP B yP A a z A , and R form a theta from x to z A . If aa ∈ E(G), then P A , P B , and R form a pyramid. Therefore a = a . Note that xa ∈ E(G), for otherwise, P A , P B , and R form a theta. Hence, a x ∈ E(G).

The proof for b x ∈ E(G) is similar. This proves Claim 5.

To conclude the proof of 1, set P A = zQz A a P A y and P B = zQz B b P B y. By Claim 5, x has neighbors in the interior of both P A and P B (these neighbors are a and b ). Note that since a x, b x ∈ E(G), the interiors of P A and P B are included in the interiors of P A and P B respectively. Hence, by Claim 1, every vertex of C \ z has neighbors in the interior of both P A and P B .

Hence, the vertices z, y and the paths P A and P B show that 1 is satisfied.

Let us now prove 2. Note that (H, C \ {x, y}) is (|C| -2)-wheel (this follows because G is theta-free, every vertex in C \ {x, y} has at least three neighbors in H). It remains to prove that it is a (|C| -2)-span-wheel. Note that it is clearly true if |C| ≤ 3. We set P A = a 1 . . . a α and P B = b 1 . . . b β with x = a 1 = b 1 and y = a α = b β , as in the definition of a k-span-wheel. We just have to exhibit an ordering of the vertices of C \ {x, y} that satisfies the rest of the definition.

We first define v 1 , the smallest vertex in the order we aim to construct. Note that no vertex v ∈ C \ {x, y} is adjacent to x or y, because C is an independent set. We let v 1 be a vertex of C that is adjacent to a i with i minimum. Let j be the smallest integer such that v 1 is adjacent to b j . We suppose that v 1 is chosen subject to the minimality of j. Let i , j be the greatest integers such that v 1 is adjacent to a i and b j . Note that 1 < i ≤ i < α and 1 < j ≤ j < β. Claim 6. For every w ∈ C \ {x, y, v 1 }, we have N H (w) ⊆ V (a i P A yP B b j ).

Proof of Claim 6. We first note that the 2-wheel (H, {v 1 , w}) is not a cousin wheel, because this may happen only when x ∈ N (v 1 ) or y ∈ N (v 1 ) (recall that if it was a cousin wheel, N H (v 1 ) would induce a 3-vertex path in H).

Hence, (H, {v 1 , w}) is a nested wheel. Suppose that N H (w) ⊆ V (a i P A a α ) ∪ V (b j P B b β ). This means that w has a neighbor z in a

i -1 P A xP B b j -1 . Since (H, {v 1 , w}) is a nested wheel, N H (w) is contained in a v 1 -sector Q of (H, v 1 ).
Moreover, since w has a neighbor in the interior of both P A and P B , we have Q = a i P A xP B b j . Since H and w form a wheel, w has neighbor in the interior of Q. This contradicts the minimality of i or j. This proves Claim 6.

The order of C \ {x, y} is now constructed as follows: we remove v 1 from C, define v 2 as we defined v 1 (minimizing i, and then minimizing j), then remove v 2 , define v 3 , and so on. This iteratively constructs an ordering of C \ {x, y} showing that (H, C \ {x, y}) is a (|C| -2)-span-wheel.

For integers t, k ≥ 1, the Ramsey number R(t, k) is the smallest integer n such that any graph on n vertices contains either a clique of size t, or an independent set of size k. Theorem 4.3. An (l-span-wheel, K t )-free graph G ∈ C has treewidth at most (t -1)(R(t, l + 2) -1) 3 -1.

Proof. Suppose for a contradiction that the treewidth of G is at least (t -1)(R(t, l + 2) -1) 3 . Since G is K t -free, by Theorem 2.1 G admits a minimal separator D of size at least R(t, l + 2). Let A and B be two connected components of G \ D that are full to D. By the definition of Ramsey number, G[D] contains an independent set C of size l + 2. We define G = G[A ∪ C ∪ B], and observe that C is a minimal separator of G . Hence by Lemma 4.2 applied to G , the graph contains an l-span-wheel, a contradiction.

The following shows that in C, an l-span-wheel with large l contains S i,j,k with large i, j, k. Lemma 4.4. If a butterfly-free graph G contains a (4k + 1)-span-wheel with k ≥ 0, then it contains S k+1,k+1,k+1 .

Proof. Consider a (4k + 1)-span-wheel in G, with x, y, P A , and P B be as in the definition of span-wheel given in the beginning of the current section. Let v 1 , . . . , v 4k+1 be the centers of the span wheel. For each i = 1, . . . , 4k + 1, let a i (resp. a i ) be the neighbor of v i in P A closest to x (resp. to y) along P A . Let b i (resp. b i ) be the neighbor of v i in P B closest to x (resp. to y) along P B . We set P i = a i P A xP B b i and Q i = a i P A yP B b i .

Claim 1. P i has length at least i + 1 and Q i has length at least 4k + 3 -i.

Proof of Claim 1. We prove this by induction on i for P i . It is clear that P 1 has length at least 2 since x is not adjacent to v 1 . Suppose the claim holds for some fixed i ≥ 1, and let us prove it for i + 1. From the induction hypothesis, P i has length at least i + 1, and since v i has a neighbor in the interior of P i+1 (because it has at least three neighbors in H), the length of P i+1 is greater than the length of P i , so P i+1 has length at least i + 2.

The proof for Q i is similar, except we start by proving that Q 4k+1 has length at least 2, and that the induction goes backward down to Q 1 . This proves Claim 1.

We set l = 2k +1. So, by Claim 1, P l and Q l both have length at least 2k +2. We set v = v l , P = P l , Q = Q l , a = a l , a = a l , b = b l and b = b l . Since G is butterfly-free, we do not have aa ∈ E(G) and bb ∈ E(G) simultaneously. So, up to symmetry we may assume that either a = a ; or a = a and aa / ∈ E(G). If a = a , let u, u , and u be three distinct vertices in P such that a, u, u , and u appear in this order along P , aP u has length k + 1 and bP u has length k -1 (which is possible because P has length at least 2k + 1). Let w be in Q and such that aQw has length k + 1 (which is possible because Q has length at least 2k + 1). The three paths aP u, avbP u , and aQw form an S k+1,k+1,k+1 .

If a = a and aa / ∈ E(G), then let u, u , and u be three distinct vertices in P such that a, u, u , and u appear in this order along P , aP u has length k and bP u has length k. Let w be in Q and such that a Qw has length k. The three paths vaP u, vbP u and va Qw form an S k+1,k+1,k+1 .

The following is a classical result on treewidth and we omit its proof. Proof. By Lemma 4.5, it is enough to consider a graph G that does not have a clique separator. If G contains a cube, then Lemma 3.2 tells us that G itself is the cube. By classical results on treewidth, the treewidth of the cube is 3 (but the trivial bound 8 would be enough for our purpose), which in particular achieves the given bound. We may therefore assume that G is cube-free. Moreover, by Lemma 4.1, G is in C. Since G is S k,k,k -free, by Lemma 4.4, G contains no (4k -3)-span-wheel. Moreover, G contains no K 3 by assumption. Hence, by Theorem 4.3, G has treewidth at most 2(R(3, 4k -1)) 3 -1.

Theorem 4.7. For k ≥ 1, an (even hole, pyramid, K t , S k,k,k )-free graph G has treewidth at most (t -1)(R(t, 4k -1)) 3 -1.

Proof. Since all thetas, prisms, even wheels, and squares contain even holes, G is (theta, prism, pyramid, even wheel, square)-free. So, by Lemma 4.1, G is in C. Since G is S k,k,k -free, by Lemma 4.4, G contains no (4k -3)-span-wheel. Moreover, G contains no K t by assumption. Hence, by Theorem 4.3, G has treewidth at most (t -1)(R(t, 4k -1)) 3 -1.

Figure 3 :

 3 Figure 3: k-turtle and k-ladder (dashed lines represent paths)

Lemma 3 . 1 .

 31 Let G be a (theta, triangle)-free graph. If W = (H, {u, v}) is a 2-wheel in G such that uv / ∈ E(G), then W is either a nested wheel or the cube.

  Suppose a = a . This implies that a is in the interior of P A . If b = b , then b is in the interior of P B -so H and Q form a theta from a to b; if bb ∈ E(G), then H and Q form a pyramid; and if b = b and bb / ∈ E(G), then aP A xP B bz B , aP A yP B b z B , az A Qz B form a theta from a to z B (note that az A Qz B has length at least 2 because z A = z B ), a contradiction. So, aa ∈ E(G). Suppose that bb ∈ E(G). Note that |{a, a } ∩ {b, b } ∩ {x, y}| = 2, because x and y are not adjacent. Moreover, |{a, a } ∩ {b, b } ∩ {x, y}| = ∅, for otherwise H and Q form a prism. So, |{a, a } ∩ {b, b } ∩ {x, y}| = 1. In this last case, we suppose up to symmetry that x = a = b. So, z is in the interior of Q since it is non-adjacent to x -in particular Q has length at least 2. Hence, H and Q form a butterfly (with x = a = b being the center), a contradiction. So, bb / ∈ E(G). If b = b , then b is in the interior of P B ; thus P A , P B , and Q form a pyramid (i.e. 3P C(az A a , b), a contradiction. So, b = b , and hence by Claim 3, z B = z. This means that b = x and b = y (because C is an independent set). Therefore, aP A xP B bz, a P A yP B b z, and z A Qz form a pyramid (i.e. 3P C(aa z A , z)), a contradiction.

Claim 5 .

 5 a x ∈ E(G) and b x ∈ E(G).

Lemma 4 . 5 (

 45 [START_REF] Lovász | Graph minor theory[END_REF]). The treewidth of a graph G is the maximum treewidth of an induced subgraph of G that has no clique separator.

Theorem 4 . 6 .

 46 For k ≥ 1, a (theta, triangle, S k,k,k )-free graph G has treewidth at most 2(R(3, 4k -1)) 3 -1.

Acknowledgement

Thanks to Édouard Bonnet, Zdeněk Dvořák, Kristina Vǔsković, and Rémi Watrigant for useful discussions. We are also grateful to two anonymous referees for careful reading of the paper and valuable suggestions and comments, which have improved the presentation of the paper.

This research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement no. 714704. , CNRS, LIP, F-69342, LYON Cedex 07, France. The last three authors are partially supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR) and by Agence Nationale de la Recherche (France) under research grant ANR DIGRAPHS ANR-19-CE48-0013-01.