Virginie Goetz
email: goetz.virginie.m@gmail.com

Pierre Gibot
email: pierre.gibot@cnrs.fr

Al/SnO 2 nanothermites ESD desensitization by means of the elaboration of tailored SnO 2polypyrrole composites

Keywords: Spark sensitivity, polypyrrole, microstructuring, desensitization, energetic formulations, conducting polymer

Incidents can occur when handling energetic materials (EMs) due to their sensitivity to external solicitations. Mechanical (friction, impact) and electrical (electrostatic discharge (ESD)) stimuli can trigger unvolunteered ignition of EMs. Nanothermites, defined as highly reactive mixtures of metal and metal oxide, show interesting reactive properties (high temperature/amount of heat…). However, their extreme sensitivity to ESD is a significant drawback in their development. With a sensitivity threshold lower than the millijoule, and considering the human body capacity discharge at a few tens of millijoule, the handling of such energetic mixtures is extremely hazardous. ESD desensitization is therefore of crucial importance for the use of these materials. To achieve this goal, polypyrrole (PPy) conductive polymer was used as an additive within an Al/SnO 2 energetic formulation. This polymer is able to easily conduct the electrostatic charges which is useful to avoid an ignition after a spark solicitation. PPy was added in the nanothermite through the elaboration of SnO 2 -PPy composites. Delaying the SnO 2 introduction time during pyrrole's polymerization (t = 0, 1, 24 h) changed the microstructure of composites. The various SnO 2 -PPy composites highlighted that the additive's distribution within the composite is a key component for the modulation of ESD sensitivity. For example, this threshold is higher for a nanothermite formulated with the composite elaborated at t = 0 h (96.5 mJ with 7.5 vol.% of polymer) than a composition based on the composite at t = 24 h (16.9 mJ with 8.2 vol.% of polymer).

Meanwhile, the reactive properties are decreased. The loss of reactivity (e.g. combustion speed) was explained by the thermal insulating property of the additive. Overall, the aim of this study is to help in the understanding of ESD desensitization of nanothermites in order to make them safer for operators and adapted to the required applications.

Introduction

Electrostatic discharge, often referred as ESD, is a phenomenon known since decades and is defined as a sudden electric current between two electrically charged objects for these an electrical potential difference occurs [START_REF] Moureaux | Phénomènes Electrostatiques -Risques Associés et Prévention INRS ED 6354[END_REF] . This phenomenon explains many cases of explosions of dust, powders, flammable substances and/or fires [START_REF] Glor | Hazards due to Electrostatic Charging of Powders[END_REF][START_REF] Luttgens | Electrostatic Hazards[END_REF] . ESD is also a high constraint in the development of energetic materials considering their sensitivity to this solicitation. Any electrostatic solicitation could trigger an ignition of these specific materials due to an excessive charge accumulation on the particle surface [START_REF] Williams | Ignition of Fully Dense Nanocomposite Thermite Powder by an Electric Spark J. Propuls[END_REF][START_REF] Beloni | Ignition of Aluminium Powders by Electrostatic Discharge Combust[END_REF] .

Among energetic materials, nanothermites -mixtures of metal (fuel) and metal oxide (oxidizer) nanoparticles [6][START_REF] Fischer | Theoretical Energy Release of Thermites[END_REF] -could not develop their potential because of their extreme sensitivity to electrostatic discharge [START_REF] Lafontaine | Les Nanothermites -Préparation, Propriétés, Applications et Perspectives ISTE Editions[END_REF] . Even if there are many stated benefits (release of high amount of heat, modulation of components, easy processing, combustion velocity up to 2500 m/s [START_REF] Fischer | Theoretical Energy Release of Thermites[END_REF][START_REF] Lafontaine | Les Nanothermites -Préparation, Propriétés, Applications et Perspectives ISTE Editions[END_REF][START_REF] Wang | The Behavior of Nanothermite Reaction Based on Bi 2 O 3 /Al[END_REF] ), nanothermites react very easily to a spark stimulus (< 1 mJ [START_REF] Beloni | Ignition of Aluminium Powders by Electrostatic Discharge Combust[END_REF][START_REF] Lafontaine | Les Nanothermites -Préparation, Propriétés, Applications et Perspectives ISTE Editions[END_REF][START_REF] Weismiller | Effects of Fuel and Oxidizer Particle Dimensions on the Propagation of Aluminium Containing Thermites[END_REF] ). Given a human body capacity discharge value between 7 and 20 mJ 1, 11-13 , the handling of nanothermites is hazardous. To prevent this risk and enable the development of these promising energetic materials, the scientific community has addressed the concept of desensitization for several years. Authors emphasized the modulation of sensitivity by adding a third component of various nature (carbon [START_REF] Siegert | Reduced-Sensitivity Nanothermites Containing Manganese Oxide Filled Carbon Nanofibers[END_REF][START_REF] Pichot | Nanodiamond for Tuning the Properties of Energetic Composites[END_REF][START_REF] Thiruvengadathan | Enhanced Combustion Characteristic of Bismuth Trioxide-Aluminum Nanocomposites Prepared through Graphene Oxide Direct Self-Assembly Propellants[END_REF][START_REF] Gibot | Mechanical Desensitization of an Al/WO 3 Nanothermite by means of Carbonaceous Coatings Derived from Carbohydrates C[END_REF] , polymers [START_REF] Foley | Development of Nanothermite Composites with Variable Electrostatic Discharge Ignition Thresholds Propellants Explos[END_REF][START_REF] Dai | Facile Formation of Nitrocellulose-Coated Al/Bi 2 O 3 Nanothermites With Excellent Energy Output and Improve Electrostatic Discharge Safety Mater[END_REF][START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF][START_REF] Apperson | On-Chip Initiation and Burn Rate Measurements of Thermite Energetic Reactions Mater[END_REF] , oxides [START_REF] Prentice | Effect of Nanocomposite Synthesis on the Combustion Performance of a Ternary Thermite[END_REF][START_REF] Yang | Hierarchical MnO 2 /SnO 2 Heterostructures for a Novel Free-Standing Ternary Thermite Membrane Inorg[END_REF] and metals [START_REF] Bohlouli | Thermo-Chemical Characterization of Al Nanoparticle and NiO Nanowire Composite Modified by Cu Powder Thermochim[END_REF][START_REF] Shen | Effects of Nano-Ag on the Combustion Process of Al-CuO Metastable Intermolecular Composite[END_REF] ...). For example, adding carbon or polymer additive as nanotubes (in each case) lead to the raise of ESD threshold from 0,14 mJ (without additive) to 41 mJ and 120 mJ with respectively 3 wt.% of carbon [START_REF] Poper | Controlling the Electrostatic Discharge Ignition Sensitivity of Composite Energetic Materials Using Carbon Nanotube Additives[END_REF] and 5 wt.% of polymer [START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF] . However, the additive introduction has a negative impact on the reactivity of compositions especially with a decrease of the combustion velocity [START_REF] Siegert | Reduced-Sensitivity Nanothermites Containing Manganese Oxide Filled Carbon Nanofibers[END_REF][START_REF] Pichot | Nanodiamond for Tuning the Properties of Energetic Composites[END_REF][START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF] . Consequently, the addition of a third component within nanothermites should be performed with care in order to desensitize nanothermites without reducing their reactive behaviour.

Recent works showed the influence of the additive structuring to meet this challenge. Through elaboration of composites between a well-chosen additive and one component of the nanothermite (the oxide), it seems possible to reach a compromise by reducing the sensitivity properties and maintaining an acceptable reactive behaviour [START_REF] Gibot | SnO 2 -Polyaniline Composites for the Desensitization of Al/SnO 2 Thermite Composites[END_REF][START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF] . Conductive polymers were selected as additive for their remarkable electrical conduction properties [START_REF] Shirakawa | Synthesis of Electrically Conducting Organic Polymers: Halogen Derivates of Polyacetylene (CH) x[END_REF][START_REF] Yi | Conducting Polymers and their Biomedical Application Biosynthetic Polymers for Medical Applications[END_REF] . They can help to prevent electrostatic charges accumulation on the reactant's particles surface which enable a raise of the electrostatic discharge sensitivity threshold. For instance, polyaniline (PAni) presents encouraging results for the ESD desensitization of nanothermite [START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF][START_REF] Gibot | SnO 2 -Polyaniline Composites for the Desensitization of Al/SnO 2 Thermite Composites[END_REF][START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF] . Indeed, the elaboration of a SnO 2 -Polyaniline composite led to ESD desensitization (47,7 mJ) with only 2 wt. % of polymer within the Al/SnO 2 energetic composition [START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF] . In the same time, the combustion velocity was measured closed to 480 m/s. This property was kept at an interesting level, i.e. about 60 % of Al/SnO 2 binary energetic system (800 m/s). The structuring of the additive with the oxide leads to desensitization but also maintains the reactivity of the energetic mixture due to the small amount of additive introduced.

This study focuses on the investigation of the polypyrrole (PPy) conducting polymer and specifically on its microstructure in the SnO 2 -PPy composite. The polymer was already used as a desensitizer thanks to a ternary addition within the energetic medium and showed promising results for the ESD desensitization [START_REF] Gibot | Polypyrrole Material for the Electrostatic Discharge Sensitivity Mitigation of Al/SnO 2 Energetic Composites[END_REF] . The Al/SnO 2 composition, chosen for this work, is extremely sensitive to the ESD solicitation with a threshold below 0,14 mJ (device limits). This extreme value represents a significant risk for the operators during handling (human body discharge capacity estimated between 7 and 20 mJ) 1, 11-13 . To avoid any risk, the goal is to conduct efficiently and quickly the charges through the medium to avoid hot spots formation by using the conducting polymer. Based on the encouraging results obtained by using SnO 2 -PAni composites, the elaboration of SnO 2 -PPy composites was performed using in-situ polymerization [START_REF] Sapurina | Polypyrrole Nanotubes: the Tuning of Morphology and Conductivity[END_REF] . Compared to the previous works, the aim of this study is to go further by focusing an additive's arrangement in the SnO 2 -PPy composite. By a late addition of the oxide during the polymerization step, the polymerization occurs differently and different organisations were obtained between the oxide and the polymer. Thus, from an experimental point of view, two main parameters were modulated during the study: the introduction time of SnO 2 particles during the polymerisation and the polymer rate within the composites. All oxide-polymer composites were mixed with aluminium nanoparticles to formulate nanothermites. Sensitivity properties and reactive performance were evaluated and discussed herein.

Experimental section

Chemicals

Nanopowders of tin (IV) oxide (SnO 2 , ≤ 100 nm powder) aluminium (pure Al wt.% of 69.3) were purchased from Alfa Aesar and Intrinsiq Materials, respectively. Pyrrole (C 4 H 5 N, ≥ 97.0 %), methyl orange (C 14 H 14 N 3 NaO 3 S, dye content 85 %) and acetonitrile (CH 3 CN, > 99.8%) were obtained from Sigma Aldrich. Iron (III) chloride hexahydrate (FeCl 3 6H 2 O) and hydrochloric acid (HCl, 37%) were from Carl Roth.

Synthesis of polypyrrole and SnO 2 -Polypyrrole composites

The work of Sapurina et al. [START_REF] Sapurina | Polypyrrole Nanotubes: the Tuning of Morphology and Conductivity[END_REF] was followed for the elaboration of the SnO 2 -PPy composites. The different SnO 2 -PPy composites were made by the oxide introduction at different times during the pyrrole polymerization process (t = 0 h, 1 h and 24 h).

For instance, in the experiment with an early SnO 2 addition (t = 0 h), 0.563 g of iron (III) chloride hexahydrate were dissolved in 125 mL of water. In a separate way, pyrrole (0.14 mL) was dissolved in water (125 mL), then 0.03 g of methyl orange were added. The molar ratio of iron (III) chloride hexahydrate to pyrrole monomer was equal to 1. After 30 seconds of ultrasounds, 0.5 g of SnO 2 particles were added under stirring. The solution of pyrrole-SnO 2 was added to the oxidant solution to start the polymerization. The mixture was stirred during 30 minutes and left at rest for 24 hours at cold temperature (5°C). Then, the solid was retrieved by centrifugation (4500 rpm, 4 min) and washed with 1 M hydrochloric acid and ethanol. Finally, the composite was dried under vacuum overnight at 80 °C.

Concerning the preparation of the other SnO 2 -PPy composites, the same process was followed but with a delayed SnO 2 introduction, 1 hour (t = 1 h) and 24 hours (t = 24 h) after the beginning of the polymerization. In particular, the SnO 2 addition was followed by 30 minutes of stirring to boost the mix of oxide within the medium. The concentration of polypyrrole in SnO 2 -PPy was modulated from 1 to 20 vol %.

Formulation of ternary PPy-doped Al/SnO 2 nanothermites

The ternary PPy-doped Al/SnO 2 nanothermites were prepared by physical mixing of the SnO 2 -PPy composites with aluminium. The combustion reaction between fuel and oxidizer can be written as (1):

(1) 4 Al (s) +3 SnO 2 (s) → 2Al 2 O 3 (s) +3 Sn (s) +ΔH
where ΔH is the amount of energy released during the reaction.

To enhance reactive performance, an excess of aluminium is frequently preferred [START_REF] Granier | Laser Ignition of Nanocomposite Thermites Combust[END_REF] . The excess of metal fuel is determined on the basis of the equivalence ratio (ф) in Equation (2). For the Al/SnO 2 energetic system, this ratio is set to 1.2 34 :

(

2) Φ = ( 𝑀 𝐹 𝑀 𝑂 ) exp. ( 𝑀 𝐹 𝑀 𝑂 ) st.
where M F /M O corresponds to the mass ratio of fuel (Al) to oxidizer (SnO 2 ) and the subscripts "exp." and "st." mean experimental and stoichiometric conditions, respectively.

Experimentally, aluminium (Al), tin oxide (SnO 2 ), polypyrrole (PPy) or tin oxide-polypyrrole composites (SnO 2 -PPy) nanopowders were mixed in a round bottom flask with 100 mL of acetonitrile.

The dispersion was stirred during one hour with ultra-sonication interruptions (5 min each 30 min) to from a homogeneous mixture. The solvent was evaporated under 200 mbar of pressure at 80 °C until dry greyish powder was obtained. Before complete recovery, the resulting energetic powder was dried at 80 °C for 4 hours. An Al/SnO 2 composition without PPy additive was formulated for comparison purposes.

For the sake of clarity, the PPy-enriched Al/SnO 2 nanothermites were named according to SnO 2 introduction time -during the polymerization of pyrrole -and the polymer concentration. The ternary nanothermites with the composites elaborated with an early SnO 2 particles introduction time (t = 0 h) were identified with the upper-case alphabet namely Al/SnO 2 -PPy-A (B C and D for the different PPy concentrations). In the same way, the nanothermites formulated thanks to SnO 2 -PPy composites with a late oxide introduction were labelled with the lower-case alphabet Al/SnO 2 -PPy-a (b c and d) for 1-hour delay (t = 1 h) and with the Greek alphabet Al/SnO 2 -PPy-α (β γ and δ) for 24-hour delay (t = 24 h).

Characterization techniques

The chemical composition of oxide-polymer composites was identified by Fourier transform infrared (FTIR) spectroscopy. The analyses were conducted using a Bruker Tensor 27 spectrometer in transmission mode (KBr disks). Spectra were recorded in the 4000 -400 cm -1 range with a resolution limit of 4 cm -1 . The concentrations of polymer within oxide-polymer composites were determined using thermogravimetric analyses (TGA). The analyses, performed on a SDT Q600 device from TA Instrument, were conducted between ambient temperature to 900 °C under air (100 mL/min) and following a 5 °C/min heating rate. The morphological characterizations of polymer-based components were performed by a scanning electron microscope (SEM FEI NovaSEM 450, FEI) working at 10 kV.

The electrical conductivities of energetic compounds were measured with a two-point probing set up.

The measurements were carried out with a low noise multimeter (Model 2010, Keithley). The powdered sample (± 50 mg) was placed in an insulating hollow cylindrical mold (inner diameter = 4 mm). A copper electrode was inserted on either side of the mold. The sample was pressed at 2.5 MPa (1 min), pressure allowing to have a stable electrical conductivity measurement for all investigated samples. The electrical conductivity was determined by using the Equation ( 3):

(3)

𝜎 = 1 𝑅 * 𝑒 𝑆
with R the electrical resistance (Ω, average value on five measurements taken all minute), e the thickness of the sample (cm) and S the section surface (cm 2 ) of the pelletized materials.

The performance of nanothermites, especially the sensitivity and the reactivity properties, were characterized by using specific devices. These properties were determined on loose powders.

The sensitivities of the energetic compositions towards the mechanical (impact, friction) and electrostatic discharge solicitations were determined according to standard procedures from NATO organization [START_REF]Standardization Agreement (STANAG) on Explosives, Impact Sensitivity Tests[END_REF][START_REF]Standardization Agreement (STANAG) on Explosives, Friction Sensitivity Tests[END_REF][START_REF]NATO STANAG 4490 In: Standardization Agreement (STANAG) on Explosives, Electrostatic discharge Sensitivity Tests[END_REF] . Impact and friction tests were performed, respectively, on a BAM Fall Hammer device (BFH-12) and on a BAM Friction apparatus (FSKM-10) from OZM Research. For the electrostatic discharge, the sensitivity tests were performed on an ESD 2008 testing device (OZM Research). These tests were described in details in the literature [START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF][START_REF] Bach | Modulation of the Reactivity of a WO 3 /Al Energetic Material with Graphitized Carbon Black as Additive[END_REF] .

The reactive properties were determined in an open burn configuration. The samples were ignited by means of an optical flash igniter equipped with a Xenon lamp and providing an energy density of about 0,11 J/cm 2 39 . In details, a small amount of energetic powder (10 mg) was placed on glass substrate over the igniter device. To delimit the optical flash to the surface covered by the investigated sample, a metal washer (inner diameter = 4 mm) was inserted between the igniter and glass slide. The combustion process of nanothermites, prepared with and without polymer additive, was recorded using a Photron FASTCAM high-speed camera (10 000 frames per second).

Results and discussion

Characterization of SnO 2 -Polypyrrole composites

The presence of the PPy conducting polymer in the organic/inorganic composites was verified by Fourier transformed infrared spectroscopy. For the sake of clarity, one SnO 2 -PPy composite at each deformation vibrations in the ring [START_REF] Stejskal | Conducting Polypyrrole Nanotubes: a Review[END_REF][START_REF] Blinova | Polyaniline and Polypyrrole: a Comparative Study of the Preparation[END_REF] . The polypyrrole polymer was characterized as conductive salt form, according to the bands at 1545, 1170, 1092 cm -1 , even if a band at 1470 cm -1 could be attributed to the deprotonation of polypyrrole [START_REF] Stejskal | Conducting Polypyrrole Nanotubes: a Review[END_REF][START_REF] Blinova | Polyaniline and Polypyrrole: a Comparative Study of the Preparation[END_REF] . Other infrared bands (1620, 1600, 1385, 1115, 1006, 838 and 819 cm -1 ) were assigned to the methyl orange used as a structuring agent in the synthesis (despite multiples washes) [START_REF] Sapurina | Polypyrrole Nanotubes: the Tuning of Morphology and Conductivity[END_REF][START_REF] Varga | The Ageing of Polypyrrole Nanotubes Synthesized with Methyl Orange[END_REF] .

Then, the SnO 2 -PPy composites were characterized by thermogravimetric analyses to determine the weight percentage of polymer within the inorganic/organic composites. the polymer matrix. The second weight loss, recorded between 200 and 600 °C, was attributed to the degradation of the polypyrrole organic phase [START_REF] Stejskal | Conducting Polypyrrole Nanotubes: a Review[END_REF] . Above 600 °C, no mass loss was observed, confirming complete polymer degradation and thermal stability of the tin oxide (IV) material [START_REF] Manivel | Optical and Electrochemical Studies of Polyaniline/SnO 2 Fibrous Nanocomposites[END_REF] .

The polymer concentrations within the SnO 2 -PPy composites were reported in Table 1 with volume percentage for a better understanding on the polymer distribution within the composite. The volume percentages of the species were calculated from the ratio of their own volume to the volume of a sample pellet (considering porosity). The volume of the species considered was determined from its mass (determined by TGA) and density. The microstructures of the SnO 2 -PPy composites were characterized by SEM (Figure 3). Two kinds of populations were distinguished in each sample (regardless the SnO 2 particle's introduction time): spherical particles and fibrous elements. The spherical particles could be attributed to the tin (IV) oxide particles and the fibrous elements to polypyrrole material. Indeed, according to the work of Sapurina et al. [START_REF] Sapurina | Polypyrrole Nanotubes: the Tuning of Morphology and Conductivity[END_REF] , the polymerization of pyrrole leads to the preparation of long nanotubes (several micrometres in length), as characterised by TEM analysis (Supporting Information S3). an earlier stage of polymerization (t = 0 and 1 h) seems to prevent the formation of nanotubes but instead promote the formation of a polymer coating on SnO 2 particles (in an inhomogeneous way). On the other hand, when the oxide was added at the end of the polymerization, the nanotubes grow (independently)

as nanotubes of several microns in length.

Characterization of ternary Al/SnO 2 -Polypyrrole nanothermites

-PPy composites. A and B corresponded to SnO 2 -PPy-A (t = 0 h), C and D to SnO 2 -PPy-a (t = 1 h), E and F to SnO 2 -PPy-α (t = 24 h).

The different composites SnO 2 -PPy were mixed with an aluminium nanopowder to formulate Al/SnO 2 -PPy nanothermites with a polymer content in the range of 1.5 and 12.4 vol.% (Table 2).

Electrical conductivity of PPy-enriched Al/SnO 2 energetic composition and sensitivity to electrostatic discharge (ESD)

Before processing to the determination of ESD sensitivity thresholds, electrical conductivity measurements were performed on the different Al/SnO 2 -PPy nanothermites (Figure 4).

According to Figure 4, the conductivity changed when the PPy concentration increased within nanothermites, regardless of the SnO 2 particle's introduction time (t = 0 h, t = 1 h, t = 24 h). This increase comes from the electrical conduction of the pure PPy value, measured at 0.85 S/cm. In details, in the Figure 4, two trends were observed:

-For less than 5 vol. %, low values of electrical conductivities were reported. By comparison to the conductivity value of the nanothermite without polymer (0 vol. %, σ = 6.16 x 10 -7 S/cm), it seems that the introduction of SnO 2 particles during polymerization (t = 0, 1, 24 h) had no significant impact on the electrical conductivity.

-On the contrary, for more than 5 vol. %, the electrical conductivity raises for all type of composites and as a function of the PPy concentration. Here, the microstructure of the conducting polymer in the SnO 2 -PPy composite has an influence on the electrical conductivity values. A delayed introduction time of SnO 2 (t > 1 h ) led to higher conductivity values in contrast to nanothermites with SnO 2 -PPy composites synthesized at the beginning of the polymerization (t = 0 h). For example, the conductivity value of the nanothermite elaborated from a SnO 2 -PPy composite at t = 0 h and with 7.5 vol. % of polypyrrole (σ = 4.14 x 10 -7 S/cm) was two orders of magnitude lower than that obtained for a nanothermite consisting of SnO 2 -PPy composites created at t = 1 and 24 h, measured at 1.58 x 10 -5 S/cm (8.5 vol. %) and 6.76 x 10 -5 S/cm (8.2 vol. %), respectively. This difference argues that the organization of polymer within the nanothermite have an influence on the ability to conduct the charges. As suggested in study about oxide-polymer composite microstructure (section 3.1, Figure 3), the SnO 2 -PPy composite present more nanotubes of polymer as the delay of SnO 2 particle introduction is important (t = 1 and 24 h). With a large amount of nanotubes, it might be easier to develop a continuous three-dimensional conductive network within the nanothermite and thus obtain significant electrical conductivity values. SEM analysis seems to validate this assumption of a continuous network with the presence of an important amount of polypyrrole nanotubes within the energetic sample (Figure 5C D E andF). For the sample where SnO 2 particles have been added early (t = 0 h), the electrical conductivity values were lower. In this case, the conductive phase is less significant due to the lack of polypyrrole nanotubes (which enables the conductive phase to be the three-dimensional) (Figure 5A andB).

Then, PPy-enriched Al/SnO 2 nanothermites were characterized by means of ESD sensitivity tests (Figure 6). All values were compared to the sensitivity threshold of the Al/SnO 2 binary nanothermite (< 0,14 mJ) to quantify the impact of the introduction of a conductive compound on the ESD sensitivity.

Moreover, to guarantee the operators safety and by extent to be sure that the nanothermite is effectively desensitized, the human body discharge capacity is taken as reference at 20 mJ (values in literature are between 7 and 20 mJ [START_REF] Moureaux | Phénomènes Electrostatiques -Risques Associés et Prévention INRS ED 6354[END_REF][11][START_REF] Greason | Electrostatic Discharge Characteristics for the Human Body and Circuit Packs[END_REF][START_REF] Talawar | Primary Explosives: Electrostatic Discharge Initiation, Additive Effect and its Relation to Thermal and Explosive Characteristics[END_REF] ). introduction time within composites (t = 0 and 1 h), sensitivity thresholds exceeded the reference value (20 mJ) with a PPy rate around 5 vol. %. On the contrary, for a delayed SnO 2 particles introduction, a higher amount of PPy (> 8 vol. %) is required to overcome this value. Moreover, when the polymer rate increased (11 -12 vol. %), the nanothermite with an earlier SnO 2 introduction (t = 0 and 1 h) showed a higher ESD sensitivity threshold than nanothermite with a delayed oxide introduction (t = 24 h): 246.40 mJ for t = 0 and 1 h against 120.74 mJ for t = 24 h. This difference in ESD sensitivity threshold can be surprising. Indeed, similar electrical conductivities were measured for these compositions (10 -2 -10 -3 S/cm, Figure 4). It seems that the electrical conductivity study of nanothermite is not the only factor to explain the trend of the ESD sensitivity threshold of nanothermites. As mentioned before, the evolution of ESD threshold for Al/SnO 2 -PPy at t = 0 h and 1 h were similar as their organisation: they have some fibrous element in low amount and as well as a polymer layer on the oxide particles (especially for nanothermites at t = 0 h) (Figure 5A B C D). With this kind of structuring, electrostatic charges could be dissipated easier thanks to the polymer which is present in a homogenous way inside of the energetic matter. Polymer and oxide materials were closely linked together and there were many contact areas between the two elements. This was advantageous to prevent the charges accumulation during the spark solicitation. Due to the presence of the polymer, the aluminothermy reaction needs more energy to ignite.

As a result, the ESD sensitivity threshold gets higher. By contrast, for the Al/SnO 2 -PPy t = 24 h nanothermites, a lot of PPy nanotubes were identified (Figure 5E F) and a heterogeneous distribution of PPy and SnO 2 were observed in all the volume of nanothermite. In this case, the nanothermite ignition required a lower energy. The ESD threshold remained at a risky level: the polymer did not play the role of charges dissipater. These results highlight the importance of the homogeneous distribution of conductive polymer for desensitization of nanothermite.

Sensitivity tests to mechanical solicitations (friction, impact)

Mechanical stimuli sensitivities of the different PPy-rich nanothermites were studied by means of friction and impact tests. The values measured are gathered in Table 3. The Al/SnO 2 binary nanothermite, taken as a reference, has an insensitivity to friction and impact tests, with thresholds over devices limits: i.e. > 360 N and > 100 J, respectively. At first, all nanothermites studied have sensitivity thresholds above international standards defined for the transport of dangerous goods and established at 80 N for the friction and 2 J for the impact tests [START_REF]Recommendations on the Transport of Dangerous Goods: Manual of Tests and Criteria, 4 th Rev Ed[END_REF] .

Therefore, Al/SnO 2 -PPy nanothermite could be transported on public roads without any risks regarding mechanical solicitations.

On the one hand, a slight phenomenon of sensitivity to friction was noted for nanothermites with less than 5 vol. % of PPy (Table 3). To explain this trend, a hypothesis could be formulated in relation with the thermal decomposition of polypyrrole, which occurs at lower temperature (200 -500 °C, Figure 1)

than the nanothermite ignition (> 500 °C [START_REF] Pantoya | Combustion Behaviour of Highly Energetic Thermites: Nano versus Micron Composites Propellants, Explos[END_REF] ), could trigger this phenomenon. The gaseous residues from the decomposition of the polymer can heat the Al and SnO 2 reactants, with the formation of hot spots on their surface leading to an earlier thermite reaction. For nanothermites with a higher PPy content, the amount of polymer is enough to act as a physical barrier between the reactive species [START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF] , thus requiring more energy for ignition, resulting in higher friction sensitivity threshold values.

On the other hand, the sensitivity to impact was quite different depending on the kind of Al/SnO 2 -PPy nanothermites. For the Al/SnO 2 -PPy t = 24 h nanothermites, no mitigation on impact sensitivity was noted. A sensitization was observed at low PPy content (< 7 vol. %) within Al/SnO 2 -PPy at t = 0 and 1 h. The difference of sensitivity threshold could be explained by a more homogenous PPy distribution for these latter compositions, leading to a possible thinner polymer thickness between aluminium and oxide nanoparticles. With a thinner polymer thickness, the polymer can decompose more easily because of the profitable thermal energy available (coming from the transformation of mechanical to thermal energy during the impact phenomena). As a result, the compression of PPy decomposition gases can lead to the formation of hot spots at the Al/SnO 2 interface and allow the ignition of the nanothermite.

For energetic composition with more than 7 vol. %, the polymer content is enough to delay the ignition by the formation of a physical barrier between reactive with low thermal conductivity. More energy is needed to obtain the ignition, meaning a raise of sensitivity threshold.

Reactivity test in open burn configuration

The reactive properties of Al/SnO 2 -PPy nanothermites were studied in an open mode using a flash technique described in section 2.4. Taking into consideration the ESD sensitivity results presented in the previous section, the reactive properties of nanothermites were focused on compositions in accordance with safety reference (20 mJ), meaning that only nanothermites with more than 5 vol. % of polypyrrole for the series at t = 0 and 1 h, and more than 8 vol. % for t = 24 h, are described here. The data about combustions events of the different Al/SnO 2 -PPy nanothermites is available in Supporting Information S4.

The combustion of nanothermite without any polymer was quick and complete (no residual matter was found on the glass slide). An intense luminous flash was noted and the combustion time was determined equal to 4.6 ± 0.1 ms (Figure 7).

The reactive behaviour of Al/SnO 2 -PPy nanothermites depend on the polypyrrole content within nanothermite: the higher the amount of polymer, the slower the combustion rate (Figure 7). This could be explained by the low thermal properties of the polypyrrole and especially the thermal conductivity with a value between 0.02 -0.12 W/m.K [START_REF] Misra | Nanostructured Polypyrrole: Enhancement in Thermoelectric Figure of Merit Through Suppression of Thermal Conductivity[END_REF] . This value is lower than the other reactants within the nanothermite: i.e 27.3 W/m.K for Al 2 O 3 [START_REF] Kumari | Thermal Properties of CNT-Alumina Nanocomposites Compos[END_REF][START_REF] Zhan | Carbon Nanotube Reinforced Alumina-Based Ceramics with Novel Mechanical, Electrical and Thermal Properties Int[END_REF] (at the surface of aluminium particles), 30 W/m.K for SnO 2 [START_REF] Fayette | Influence of Grain Size on the Thermal Conductivity of Tin Oxide Ceramics[END_REF] and 237 W/m.K for aluminium [START_REF] Chen | Thermal Properties of Aluminium-Graphite Composites by Powder Metallurgy Composites[END_REF] . In this way, the polymer acts as a thermal barrier. It consequently restricts the heat transfer through the energetic material. That is why combustion time of PPy-rich nanothermites were increased, meaning a decreased of the combustion rate. In Figure 7, it appears that the combustion time varies slightly with the nanostructuring of polymer with the oxide. For example, a comparison was made between the nanothermites with high PPy rate meaning: Al/SnO 2 -PPy-A (PPy rate = 12 vol. %), Al/SnO 2 -PPy-a (PPy rate = 12.4 vol. %), Al/SnO 2 -PPy-α (PPy rate = 11.5 vol. %).

Among these three energetic compositions, the Al/SnO 2 -PPy-α nanothermite (t = 24h) showed a faster combustion time (66.0 ± 1.0 ms) than the two other compositions (83.0 ± 1.0 ms for Al/SnO 2 -PPy-a and 69.0 ± 1.0 ms for Al/SnO 2 -PPy-A). However, considering the gap between the above-mentioned values, it seems to be quite difficult to argue that the reactive behaviour really depends on the polymer microstructure within nanothermites.

Discussion

According to the literature, the desensitization of nanothermites was studied by the introducing different kind of additives such as carbon [START_REF] Siegert | Reduced-Sensitivity Nanothermites Containing Manganese Oxide Filled Carbon Nanofibers[END_REF][START_REF] Thiruvengadathan | Enhanced Combustion Characteristic of Bismuth Trioxide-Aluminum Nanocomposites Prepared through Graphene Oxide Direct Self-Assembly Propellants[END_REF][START_REF] Gibot | Mechanical Desensitization of an Al/WO 3 Nanothermite by means of Carbonaceous Coatings Derived from Carbohydrates C[END_REF][START_REF] Poper | Controlling the Electrostatic Discharge Ignition Sensitivity of Composite Energetic Materials Using Carbon Nanotube Additives[END_REF] , oxides [START_REF] Prentice | Effect of Nanocomposite Synthesis on the Combustion Performance of a Ternary Thermite[END_REF][START_REF] Yang | Hierarchical MnO 2 /SnO 2 Heterostructures for a Novel Free-Standing Ternary Thermite Membrane Inorg[END_REF] , metals [START_REF] Bohlouli | Thermo-Chemical Characterization of Al Nanoparticle and NiO Nanowire Composite Modified by Cu Powder Thermochim[END_REF][START_REF] Shen | Effects of Nano-Ag on the Combustion Process of Al-CuO Metastable Intermolecular Composite[END_REF] and polymers [START_REF] Foley | Development of Nanothermite Composites with Variable Electrostatic Discharge Ignition Thresholds Propellants Explos[END_REF][START_REF] Dai | Facile Formation of Nitrocellulose-Coated Al/Bi 2 O 3 Nanothermites With Excellent Energy Output and Improve Electrostatic Discharge Safety Mater[END_REF][START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF][START_REF] Apperson | On-Chip Initiation and Burn Rate Measurements of Thermite Energetic Reactions Mater[END_REF] . Encouraging results were obtained after adding conductive polymers as a third component [START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF][START_REF] Gibot | SnO 2 -Polyaniline Composites for the Desensitization of Al/SnO 2 Thermite Composites[END_REF][START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF][START_REF] Gibot | Polypyrrole Material for the Electrostatic Discharge Sensitivity Mitigation of Al/SnO 2 Energetic Composites[END_REF] . The introduction of conductive polymer as an additive was done by two main ways: as an individual third component and as via the elaboration of a polymer/oxide composite before adding aluminium fuel. These two ways showed a possible desensitization to ESD but at different level.

Indeed, according to previous works [START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF][START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF] , the addition of polyaniline (PAni) as a third component required a significant amount of polymer to increase the ESD threshold. The morphology of polymer was investigated and the authors showed that fibres of polymer with a high L/Ø shape factor (length (L) = 1 -2 µm, diameter (Ø) = 50 nm) were more advantageous to conduct easily the charges within the medium. The addition of long fibres of polymer increased the ESD threshold with 5 wt.% of PAni (ESD = 120 mJ) [START_REF] Gibot | Safer and Performing Energetic Materials Based on Polyaniline-Doped Nanocomposites[END_REF] . Nevertheless, by the structuring between the oxide and the polymer additive, the desensitization to spark solicitation (ESD = 47 mJ) was obtained with the addition of only 2 wt. % of PAni [START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF] . The authors highlighted the important effect of the additive dispersion to prepare desensitized nanothermites. The elaboration of oxide-additive composites leads to a homogenous polymer dispersion within the energetic material, which is very efficient and suitable for rapidly conducting the charges.

Therefore, a better raise of ESD threshold was achieved in this case.

Thanks to this current study, it seems interesting to consider the additive microstructure as a parameter for the ESD desensitization of nanothermites. The close link between the oxide and the polymer is a significant parameter in order to rapidly dissipate the charges after the electrostatic solicitation. Based on this work, it is better to formulate the composite at the beginning of the polymerization in order to prepare a composite with a polymer covering around the oxide particle surface. Compared to the literature, the sensitivity threshold reached here (ESD = 24 mJ -6.4 vol.% of PPy or 4.2 wt.% of PPy), which allows to consider the composition as desensitised, is slightly higher than that reported in 28.

These authors highlighted that 2 wt.% of additive is enough to desensitize the nanothermite (ESD = 47 mJ). Nevertheless, the comparison is a bit tricky because different polymers were used in these two studies: polypyrrole (in this work) versus polyaniline [START_REF] Goetz | Spark Sensitivity and Light Signature Mitigation of an Al/SnO 2 Nanothermite by the Controlled Addition of a Conductive Polymer[END_REF] .

A complete study of desensitization should take the reactive aspect into account. By the introduction of an inert component with low thermal properties as those of the conducting polymer, the reactive properties were slowed down compared to the composition without additive (Figure 7). But combustions events were maintained for the different energetic compositions (Supporting Information S4), which is encouraging for the preparation of safer and reactive nanothermites.

Conclusion

In this study, the oxide-conductive polymer structuring was investigated for the desensitization of nanothermites.

Different kind of structuring between the oxide and the conductive polymer additive were proposed especially by delaying the oxide particle introduction time during the polymerization process; i.e at t = 0 h, 1 h and 24 h (end of polymerization). By delaying the SnO 2 particles' introduction time, the microstructure of the inorganic/organic composite was clearly modified. This had consequences on ESD sensitivity of derived energetic composites. When the oxide was added earlier during the polymerization, an ESD desensitization was achieved at low polymer content (5 vol. %) than structuring obtained after a long time of polymerization. The closer structuring between the polymer and the oxide is a key factor for the desensitization because it leads to a better conduction capacity and thus easier charges dissipation making energetic composites safer for operators. Tests in open burn configuration were done on the different energetic compositions. Unfortunately, the low thermal conduction property of polypyrrole coupled to its role of physical barrier between reactive components slowed the reactivity down. Shapes of incandescent particles confirmed the maintaining of combustion, even if it is less violent than in the case of binary nanothermite combustion.

The next step could be the elaboration of a composite with all the components of the nanothermite -the aluminium (Al), the oxide (SnO 2 ) and the additive. A one-step synthesis could be imagined to combine the elaboration of the nanothermite as well as the polymerization of the additive. This could lead to a complete structuring between the Al/SnO 2 nanothermite and the polymer while limiting the handling by the operator. This specific structuring would lead to the formation of a continuous conducting phase between the reactants, which could promote new performances of the as-formulated Al/SnO 2 /additive energy formulation.

SnO 2

 2 introduction time (t = 0 h, t = 1 h and t = 24 h) was represented in Figure1(SnO 2 -PPy composites with the polymer concentration modulation are available in Supporting Information S1). FTIR spectra show absorption bands of tin oxide and polypyrrole for the different composites. The vibration bands in the range of 500 -700 cm -1 correspond to the SnO 2 material 40 (the black dashed rectangle in Figure1).The two bands at 669 and 620 cm -1 could be assigned to stretching modes of O-Sn-O and Sn-O bonds inside the tin oxide (IV) oxide phase, respectively. Concerning the polypyrrole, several characteristics absorption bands of the pyrrole ring were distinguished: at 1545, 1470 and 1170 cm -1 corresponding to C-C stretching vibration, C-N stretching vibration, and C-H/C-N breathing vibration, respectively. The peaks located at 1263 and 1315 cm -1 were assigned to C-H or C-N in-plane deformation vibrations. The N-H + deformation vibration was observed at 1092 cm -1 and the peak at 1050 could be attributed to C-H or N-H in-plane deformation vibration. Below 1000 cm -1 , peaks were assigned to C-H and C-C

Figure 2

 2 represents the thermogravimetric analyses of one SnO 2 -PPy composite at each SnO 2 particles introduction time (t = 0 h, t = 1 h and t = 24 h. The Supporting Information S2 gathers the TG analyses of the other SnO 2 -PPy composites with an increasing polymer concentration. The different thermogravimetric curves were similar with two weight losses in the selected temperature domain. The first loss, in the temperature range between 25 and 200 °C, corresponds to the removal of water and solvent (ethanol) embedded in

Figure 1 :

 1 Figure 1 : FTIR spectra of the SnO 2 -PPy composites. PPy bands are identified from vertical lines and the SnO 2 material with the black dashed rectangle. The sign "+" correspond to IR bands of methyl orange.

Figure 2 :

 2 Figure 2 : Thermogravimetric curves (under air) of the SnO 2 -PPy composites at three different SnO 2 particle introduction time (SnO 2 -PPy-A for t = 0 h, SnO 2 -PPy-a for t = 1 h and SnO 2 -PPy-α for t = 24 h).

Figure 3

 3 highlights that the oxide particles introduction time has an influence on the SnO 2 -PPy composite microstructures. With a tin oxide introduction at the beginning of the polymerization of pyrrole (SnO 2 -PPy-A, Figure 3A and B) or only one hour after (SnO 2 -PPy-a, Figure 3C and D), the composites present a majority of SnO 2 spherical particles and a low amount of fibrous elements. By contrast, with a lately SnO 2 particles introduction time (SnO 2 -PPy-α, Figure 3E and F) more fibrous elements can be seen. The quantity of fibrous elements seems to increase with the delay time of oxide addition. The introduction of SnO 2 at

Figure 3 :

 3 Figure 3 : SEM images of the SnO 2 -PPy composites. A and B corresponded to SnO 2 -PPy-A (t = 0 h), C and D to

Figure 4 :

 4 Figure 4 : Electrical conductivity of Al/SnO 2 -PPy composites as a function of the PPy concentration (vol.%).

Figure 5 :

 5 Figure 5 : SEM images of the Al/SnO 2 -PPy nanothermites. A and B correspond to SnO 2 -PPy-A (t = 0 h, PPy rate = 12 vol. %), C and D to SnO 2 -PPy-a (t = 1 h, PPy rate = 12.4 vol. %), E and F to SnO 2 -PPy-α (t = 24 h, PPy rate = 11.5 vol. %).

Figure 6

 6 Figure6shows different evolution of the sensitivity thresholds according to the oxide-polymer

Figure 6 :

 6 Figure 6 : ESD sensitivity as a function of the PPy concentration (vol.%).

Figure 7 :

 7 Figure 7 : Combustion time (ms) as a function of the PPy concentration (vol.%).

Table 1 :

 1 Summary table of the different SnO 2 -PPy composites. All weight losses were determined thanks to TGAanalyses shown in Supporting Information S2. From these weight losses, attributed to the removal of the polymer, the volume percentages of the polymer in the different composites (in the form of pellets used for the electrical conductivity measurement) were calculated.

		Weight loss in % (200 -600 °C) from	Volume percentage calculated of
		TGA analyses	PPy
	SnO 2 -PPy-A	12.9	19.5
	SnO 2 -PPy-B	6.9	11.2
	t = 0 h
	SnO 2 -PPy-C	4.1	7.7
	SnO 2 -PPy-D	2.2	4.5
	SnO 2 -PPy-a	13.7	19.8
	SnO 2 -PPy-b	8.2	13.4
	t = 1 h
	SnO 2 -PPy-c	6.2	10.8
	SnO 2 -PPy-d	2.5	4.6
	SnO 2 -PPy-α	14.9	19.8
	SnO 2 -PPy-β	8.4	13.0
	t = 24 h
	SnO 2 -PPy-γ	5.0	9.4
	SnO 2 -PPy-δ	1.5	2.7

Table 2 :

 2 Summary table of the concentration of PPy in the SnO 2 -PPy composites and the equivalence for theAl/SnO 2 -PPy nanothermites. Composites and nanothermites in pellet form.

		PPy rate in SnO 2 -PPy (vol. %)	PPy rate in Al/SnO 2 -PPy (vol. %)
	SnO 2 -PPy-A	19.5	12.0
	SnO 2 -PPy-B	11.2	7.5
	t = 0 h
	SnO 2 -PPy-C	7.7	3.9
	SnO 2 -PPy-D	4.5	2.1
	SnO 2 -PPy-a	19.8	11.4
	SnO 2 -PPy-b	13.4	8.5
	t = 1 h
	SnO 2 -PPy-c	10.8	6.4
	SnO 2 -PPy-d	4.6	2.5
	SnO 2 -PPy-α	19.8	11.5
	SnO 2 -PPy-β	13.0	8.2
	t = 24 h
	SnO 2 -PPy-γ	9.4	4.9
	SnO 2 -PPy-δ	2.7	1.5

Table 3 :

 3 Mechanical sensitivity thresholds of the Al/SnO 2 -PPy energetic composites developed from SnO 2 -PPy

	composites at t = 0, 1 and 24 h.

PPy rate in Al/SnO 2 -PPy (vol. %) Friction (N) Impact (J)

	Al/SnO 2 -PPy-α	11.5	> 360	> 100
	Al/SnO 2 -PPy-β	8.2	> 360	> 100
	t = 24 h
	Al/SnO 2 -PPy-γ	4.9	252	> 100
	Al/SnO 2 -PPy-δ	1.5	324	> 100
	Al/SnO 2 -PPy-A	12.0	> 360	> 100
	Al/SnO 2 -PPy-B	7.5	> 360	75
	t = 0 h
	Al/SnO 2 -PPy-C	3.9	324	90
	Al/SnO 2 -PPy-D	2.1	288	> 100
	Al/SnO 2 -PPy-a	12.4	> 360	> 100
	Al/SnO 2 -PPy-b	8.5	> 360	> 100
	t = 1 h
	Al/SnO 2 -PPy-c	6.4	> 360	90
	Al/SnO 2 -PPy-d	2.5	192	60

Acknowledgments

The authors gratefully acknowledge the French Defence Innovation Agency (DGA/AID, Paris, France) French-German Institute of Saint-Louis (ISL, Saint-Louis, France) for the operational sponsorship and the financial support of the Ph.D. project.

The authors thank MM. Boehrer (ISL, Saint-Louis, France) and Oudot (NS3E, Saint-Louis, France) for the combustion video recordings and mechanical sensitivity tests respectively and MM. Schnell and Lallemand (NS3E, Saint-Louis, France) for the scanning electron microscopy analyses. They also thank M. Morel-Fourier and Mrs Schmelz (ISL, Saint-Louis, France) for the detailed proofreading of the manuscript.

Supporting Information

Additional graphs of FITR and TG analyses are available on Supporting Information S1 and S2. SEM images as well as images of combustion phenomena are available on Supporting Information S3 and S4.


Daniel Gonçalves

Vincent Limouzy

Pascal Ochem

Contact graphs of boxes with unidirectional contacts *

come

Introduction

A lot of graph classes studied in the literature are defined by a geometric model, where vertices are represented by geometric objects (e.g. intervals on a line, disks in the plane, chords inscribed in a circle...) and the adjacency of two vertices is determined according to the relation between the corresponding objects. A large amount of graph classes consider the intersection relation (e.g. interval graphs, disk graphs or circle graphs). However some other relations might be considered such as the containment, the overlap or also the contact between objects. Recently several groups of authors started to study graph classes defined by contact models, as for example Contact of Paths in a grid (CPG) [START_REF] Deniz | On contact graphs of paths on a grid[END_REF], Contact of L shapes in R 2 or even contact of triangles in the plane [START_REF] Hubert De Fraysseix | On triangle contact graphs[END_REF]. In this note we consider a new class defined by a contact model. More precisely we consider the class of graphs defined by contact of axis parallel boxes in R d where the contact occurs on (d -1)-dimensional object in only one direction (CBU) .

When considering graph defined by axis-parallel boxes in R d and the adjacency relation is given by the intersection it corresponds to the important notion of boxicity introduced by Roberts [START_REF] Roberts | On the boxicity and cubicity of a graph[END_REF], when the adjacency relation is given by the containment relation it correspond to comparability graphs and it is connected to the poset dimension introduced by Dushnik & Miller [START_REF] Dushnik | Partially ordered sets[END_REF] The motivation for this class of graphs originate from an article of Magnant and Martin [START_REF] Magnant | Coloring rectangular blocks in 3-space[END_REF] where a wireless channel assignment is considered. The problem considers rectangular rooms in a building and asks to find a channel assignment for each room. In order to avoid interferences rooms sharing the same wall, floor or ceiling need to use different channels. The question was to determine whether a constant number of channels would suffice to answer this problem. The first negative answer was provided by Reed and Allwright [START_REF] Reed | Painting the office[END_REF] that a constant number of channels is not sufficient. Magnant and Martin strengthened their result that for any integer k there exists a building that requires exactly k channels. In addition, their construction only requires floor-ceiling contacts.

We provide the first structural properties of this class. We first establish some links with the well-known notion of boxicity in Section 4. Then in Section 7 we consider the recognition problem and we prove that it is NP-complete to determine if a graph is d-CBU for any integer d ≥ 3. Then we provide a characterization in terms of an acyclic orientation of the class of general CBU. Thanks to this characterization, it is immediate to realize that the class of CBU constitutes a proper sub-class of Hasse diagram graph (A Hasse diagram graph is the undirected graph obtained from a Hasse diagram associated to a poset). Finally we prove in Section 9 that several well studied optimization problems remains NP-hard on either 2-or 3-CBU graphs.

Preliminaries

We consider R d and d orthogonal vectors e 1 , . . . , e d and we introduce a new class of geometric intersection graphs. Here, the vertices correspond to interior disjoint d-dimensional axis-parallel boxes in R d , and two such boxes are only allowed to intersect on a (d -1)-dimensional box orthogonal to e 1 . This class of graphs is denoted by d-CBU, for Contact graphs of d-dimensional Boxes with Unidirectional contacts. We denote CBU the union of d-CBU for all d.

Note that 1-CBU correspond to the forests of paths.

Claim 1 For every d ≥ 1, d-CBU graphs are triangle-free.

Indeed, note that orienting the edges according to vector e 1 and labeling each arc with the coordinate of the corresponding (d -1)-hyperplane, one obtains an acyclic orientation such that for every vertex, all the outgoing arcs have the same label, all the ingoing arcs have the same label, and the label of ingoing arcs is smaller than the label of outgoing arcs. We call such a labeling of the arcs an homogeneous arc labeling. Note that an oriented cycle cannot admit such a labeling. A triangle abc oriented acyclically is, up to automorphism, such that Claim 2 For any homogeneous arc labeling of a graph G, its restriction to a short cycle is as follows.

d + (a) = 2, d + (b) = 1,
1 2 3 1 3 x x x x x (i) (ii) (iii)
Figure 1: (i) Example of a good orientation of a C 5 with some valid labels, (ii) example of bad orientation. Once a label x is fixed for one arc, this label is propagated to all the arcs leading to the conclusion that x < x. (iii) the two valid orientations of a C 4

• For a 4-cycle, the orientation is either such that there are two sources and two sinks, or it is such that there is one source and one sink linked by two oriented paths of length 2.

• For a 5-cycle, the orientation is such that there is one source and one sink linked by two oriented paths, one of length 2 and one of length 3.

Relation with Cover Graphs

An undirected graph is a cover graph if it is the underlying graph of the Hasse diagram of some partial order. It was shown by Brightwell [START_REF] Graham | On the complexity of diagram testing[END_REF] and also by Nešetřil and Rödl [START_REF] Nešetřil | Complexity of diagrams[END_REF][START_REF] Nešetřil | Erratum: Complexity of diagrams[END_REF][START_REF] Nešetřil | More on the complexity of cover graphs[END_REF] that deciding whether a graph is a cover graph is NP-complete. However, they came up with a simple characterization in terms of acyclic orientations. Their characterization states that a graph is a cover graph if and only if there exists an acyclic orientation without a quasi-cycle. A quasi-cycle, being an orientation of a cycle (v 1 , v 2 , . . . , v n ) with the arcs (v i , v i+1 ) for all 1 ≤ n -1 plus the arc (v 1 , v n ). From a homogeneous arc labelling, the orientation provided by the labelling clearly fulfills the above defined condition.

Claim 3 For any homogeneous arc labeling of a graph G, the orientation of G does not contain any quasi-cycle.

Corollary 4

The class of CBU graphs is contained in the class of cover graphs.

From the previous result, it is natural to ask whether both classes are equivalent. The following remark provides the answer.

Remark 5

The class of CBU graphs is strictly contained in the class of cover graphs. In Lemma 16 we will exhibit a graph that is not CBU but is a cover graph.

3

We will see in the following that an orientation of a triangle-free graph G, fulfilling the conditions of Claim 2 and of Claim 3 may not admit a homogeneous arc labeling.

Boxicity

The boxicity box(G) of a graph G, is the minimum dimension d such that G admits an intersection representation with axis-aligned boxes. Of course, the graphs in d-CBU have boxicity at most d. The converse cannot hold for the graphs containing a triangle, as those are not in CBU. However, some relations hold for triangle-free graphs. Let us begin with bipartite graphs.

Theorem 6 Every bipartite graphs of boxicity b belongs to (b + 1)-CBU.

Proof. Consider a bipartite graph G with vertex sets A and B. Consider a boxicity b representation of G and slightly expand each box in such a way that the intersection graph remains unchanged (we stop the expansion of the boxes before creating new intersections). Now, any two intersecting boxes intersect on a b-dimensional box. Assume that this representation is drawn in the space spanned by e 2 , . . . , e b+1 , and let us set for the first dimension (spanned by e 1 ) that the vertices of A and B, correspond to the intervals [0, 1] and [START_REF] Adiga | The hardness of approximating the boxicity, cubicity and threshold dimension of a graph[END_REF][START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF], respectively. As A and B are independent sets, it is clear that the boxes in the representation are interior disjoint and that any two intersecting boxes intersect on a b-dimensional box orthogonal to e 1 . The obtained representation is thus a (b + 1)-CBU representation of G.

2

Theorem 6 does not extend to triangle-free graphs. We will see in the following section that there exists triangle-free graphs with bounded boxicity that are not d-CBU, for any value d. Actually, Lemma 16 tells that there exists such graphs with girth 5. In other words, for a 3 ≤ g ≤ 5, there is no function f g such that every graph G, of girth at least g and of boxicity b belongs to (f g (b))-CBU.

Problem 7 For g ≥ 6, is there a function f g such that every graph G, of girth at least g and of boxicity b belongs to (f g (b))-CBU?

By Theorem 12, we know that if f 6 exists, then f 6 (2) is at least 3. Nevertheless, the following theorem shows that subdividing the edges enables to consider every triangle-free graph. An intersection representation is said proper if two objects intersect if and only if some point of the representation belongs to these 2 objects, only.

Theorem 8 For every graph G having a proper intersection representation with axis-parallel boxes in R b , the 1-subdivision of G belongs to (b + 1)-CBU.

Proof.

Consider such a representation of G and slightly expand each box in such a way that the intersection graph remains unchanged, and any two intersecting boxes intersect on a b-dimensional box. Assume that this representation is drawn in the space spanned by e 2 , . . . , e b+1 , and for the first dimension ( Corollary 9 For every triangle-free graph G of boxicity b, the 1-subdivision of G belongs to (b + 1)-CBU.

Planar graphs

While planar graphs have boxicity at most 3 [START_REF] Thomassen | Interval representations of planar graphs[END_REF][START_REF] Felsner | Contact representations of planar graphs with cubes[END_REF][START_REF] Bremner | On representing graphs by touching cuboids[END_REF], many subclasses of planar graphs are known to have boxicity at most 2. This is the case for 4-connected planar graphs [START_REF] Thomassen | Plane representations of graphs[END_REF], and their subgraphs. The subgraphs of 4-connected graphs include every triangle-free planar graph (see Lemma 4.1 in [20]). As observed earlier, for those the representation is necessarily proper. For general planar graphs, the representation in R 3 provided in [START_REF] Felsner | Contact representations of planar graphs with cubes[END_REF] is clearly proper. So Theorem 8 implies the following.

Corollary 10 For every planar graph G, the 1-subdivision of G belongs to 4-CBU. Furthermore, if G is triangle-free then it even belongs to 3-CBU.

2-CBU graphs

Given a 2-CBU representation of a graph G, and a vertical line ℓ, the top box of this representation with respect to ℓ is the highest box intersecting ℓ. Now, the top sequence of a 2-CBU representation is the sequence of top boxes obtained when parsing the representation with ℓ from left to right (see Figure 2).

v i v i-1 = v i+1 v i v j v i+1 v j-1
v i , v i-1 = v i+1 , is the top box. Right part : Adding v i+1 , . . . , v j-1
. This is done in the vertical stripe where v i and v j are the top box, successively.

One can easily see that 2-CBU graphs are planar graphs, and that every forest is a 2-CBU graph. Actually, this class contains every triangle-free outerplanar graph.

Theorem 11 Every triangle-free outerplanar graph is 2-CBU.

Proof. Let us prove that for any connected outerplanar graph G, and any facial walk v 1 , v 2 , . . . , v k , v k+1 = v 1 on the outerboundary of G (with separating vertices appearing several times in this walk), there exists a 2-CBU representation of G with top sequence v 1 , v 2 , . . . , v k , v k+1 .

We proceed by induction on the number of vertices in G. The statement clearly holds if G has only one vertex. A connected triangle-free outerplanar graph with more vertices contains either a vertex v i of degree one, or a cycle v i , . . . , v j of length at least four (i.e. j -i ≥ 3), whose vertices v i+1 , . . . , v j-1 have degree two in G.

In the first case we can add the box of v i in the representation of G \ v i obtained by induction (see Figure 3, left). In the second case we consider the representation of G \ {v i+1 , . . . , v j-1 } obtained by induction. Note that v i and v j now appear consecutively in its outerboundary, such as in the top sequence. It is thus easy to add the boxes of v i+1 , . . . , v j-1 in the representation (see Figure 3

, right). 2

Theorem 12 There are series-parallel graphs of girth 6 that are not 2-CBU.

Proof. Consider a graph G with two vertices, a and b, linked by 9 disjoint ab-paths of length three ax i y i b, for i ∈ {1, . . . , 9}. Then for each edge x i y i add a length 5 path from x i to y i . The obtained graph has girth 6 and is series-parallel (see Figure 5). Note that in a 2-CBU representation of G, the box of a (resp. b) has at most four neighbors such that their intersection contains a corner of a (resp. b). Thus, there exists an i ∈ {1, . . . , 9} such that one side of x i is contained in one side of a, and one side of y i is contained in one side of b. Now, whatever the way x i and y i intersect (a side of x i may be contained in a side of y i , or the other way around, or also their intersection may contain a corner of each box), it is not possible to have the length 5 x i y i -path (see Figure 5, right). If a side of x i is contained in a side of y i there is no place left around x i to draw a third neighbor. If the intersection of x i and y i contains a corner of x i and a corner of y i , there is space to draw a third neighbor for these vertices, say u and v respectively, but in that case the uv-path should go around a or b, but it would intersect the paths ax j y j b with j ̸ = i. Thus G does not admit a 2-CBU representation. 2

Problem 13 Is there a girth g such that every series parallel graph of girth at least g belongs to 2-CBU ?

For planar graphs, the following theorem shows that such a bound on the girth does not exist. Let us denote by W 2 g the double wheel graph, obtained from a cycle C g by adding two non-adjacent vertices, each of them being adjacent to every vertex of C g . An edge incident to one of these two vertices (i.e., an edge not contained in C g ) is called a ray. Now, let W ′ g be the graph obtained from W 2 g by subdividing ⌊g/2⌋ times every ray (see Figure 6). This graph is planar and has girth g.

Theorem 14

The graph W ′ g does not belong to 2-CBU.

Proof. For any 2-CBU representation of the cycle C of length g there is a rectangle R, for example the one with the leftmost right side, such that none of the top or bottom side of R is incident to the inner region. It is thus impossible to connect R with a ray in the inner region. On the other hand, there is no planar embedding of W ′ g where C bounds an inner face.

3-CBU graphs

Bipartite planar graphs are known to be contact graphs of axis-aligned segments in R 2 [START_REF] Ben-Arroyo Hartman | On grid intersection graphs[END_REF][START_REF] Hubert De Fraysseix | Representation of planar graphs by segments[END_REF], and their boxicity is thus at most two. By Theorem 6, we thus have the following.

Corollary 15 Every bipartite planar graph belongs to 3-CBU.

The following lemma tells us that this property does not generalize, in a strong sense, to triangle-free planar graphs.

Lemma 16 There exists a girth 4 planar graph that is not CBU.

Proof. Let us consider the graph G 1 represented in Figure 7. One can show that this graph does not admit any valid CBU orientation where in the C 4 induced by a, b, c and d, a is a source and d is a sink (nor the converse). Let us assume that there exists a CBU orientation such that a is a source and d is a sink. By fixing the orientation of edges ab and ac from a to b and from a to c respectively, and by Claim 2, the edges be and cf have to be oriented from b to e and from c to f . The edge ef is oriented in any direction, w.l.o.g. let us say from e to f . But in that case, in the C 5 induced by b, e, f, c and d contains two sources and two sinks, which is not a valid CBU orientation (By Claim 2). By adding a path of length 3 between a and d, we obtain the graph G 2 . From the previous observation, we can conclude the same property for vertices b and c. Hence, in the valid orientation of G 2 , a and d are sources and b and c are sinks (or the converse). Let us now consider the graph G 3 obtained by gluing two copies of G 2 in a special manner (see Figure 7). Let us remark that the graph obtained is planar. Let us consider, w.l.o.g., that a and d are sources and b and c are sinks in the C 4 induced by a, b, c, and d. Recall that a valid orientation of a C 5 contains exactly one source and one sink. Thus, in the C 5 induced by the vertices a, c, d, k, and j, the vertex c has to be a sink from the already fixed orientation. Hence, it forces the edge aj to be oriented from j to a and the edge dk from k to d (the edge k, j can be oriented in any direction), since the length of a path from a source to a sink in an orientation is exactly 2 for one path and 3 for the other.

Then in the partial orientation obtained, we can conclude that in the C 4 induced by a, c, i, and j, the vertex c will be a sink and vertex j will be a source. However, as mentioned in the beginning of this proof, this orientation will not lead to valid orientation, since j and c play the same role as a and d in G 1 . Hence, G 3 does not admit a valid CBU orientation.

2

Remark 17

The graph G 3 used in the proof of Lemma 16 is actually a cover graph. In Figure 7, the bottom picture depicts its Hasse diagram.

Since every planar graph with girth at least 10 has circular chromatic number at most 5/2 [START_REF] Dvořák | Density of 5/2-critical graphs[END_REF], the forthcoming Theorem 35 implies that such a graph necessarily belongs to CBU.

Problem 18 What is the lowest g ∈ [5, . . . , 10] such that every planar graph G with girth at least g belongs to CBU.

Structural properties of d-CBU and CBU

Theorem 19 For every d ≥ 1, the class of d-CBU graphs is strictly contained in the class of (d + 1)-CBU graphs.

The case d = 1 follows from the earlier observation that 1-CBU graphs correspond to forests of paths, and from the many examples of 2-CBU graphs provided above. For d ≥ 2, the following structural lemma allows us to translate the strict containment of boxicity b bipartite graphs, to the strict containment of d-CBU. Indeed, it is known that the graph obtained from the complete bipartite graph K 2b,2b by removing a perfect matching has boxicity exactly b [START_REF] Chandran | Cubicity, boxicity, and vertex cover[END_REF].

Lemma 20 Given a connected bipartite graph B, with parts X and Y , let B ′ be the graph obtained from B, by adding a path xzy and by connecting x and y to every vertex in X and Y , respectively. Then, B has boxicity at most d if and only if B ′ belongs to (d + 1)-CBU.

Proof.

Let us begin with the simpler "only if" part. We proceed as in the proof of Theorem 6 in order to obtain a (d + 1)-CBU representation of B such that every vertex of X (resp. Y ) corresponds to [0, 1] (resp. [START_REF] Adiga | The hardness of approximating the boxicity, cubicity and threshold dimension of a graph[END_REF][START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF]) in the space spanned by e 1 . Then it suffices to add the boxes for x, y and z. For a sufficiently large Ω, x is represented by

[-1, 0] × [-Ω, +Ω] × . . . × [-Ω, +Ω], y is represented by [2, 3] × [-Ω, +Ω] × . . . × [-Ω, +Ω], and z is represented by [0, 2] × [Ω -1, Ω] × . . . × [Ω -1, Ω].
For the "if" part, consider a (d + 1)-CBU representation of B ′ , and the homogeneous arc labeling of B ′ induced by this representation. We first prove that all the arcs between X and Y are oriented in the same direction. Towards a contradiction, consider a path x 1 y 2 x 3 with x 1 , x 3 ∈ X and y 2 ∈ Y , and such that the edges are oriented from x 1 to y 2 , and from y 2 to x 3 . This forces the remaining edges of the 4-cycle yx 1 y 2 x 3 to be oriented from x 1 to y, and from y to x 3 (see Claim 2). Now we cannot orient the edge y 2 x, xz, zy in such a way to fulfill Claim 2 for the 5-cycles xzyx 1 y 2 and xzyx 3 y 2 . Indeed for the first one, yz should be oriented from y to z, while for the second one it should be oriented from z to y, a contradiction.

This orientation ensures that the labels of all the arcs is the same. This implies that there is an hyperplane H orthogonal to e 1 such that for any pair of intersecting boxes x ′ ∈ X and y ′ ∈ Y , their intersection belongs to H. This implies that projecting the (d + 1)-CBU representation (restricted to B) along e 1 leads to a boxicity d representation of B.

2

It is clear that CBU is hereditary (i.e. closed under induced subgraphs) but actually it is also closed under subgraphs.

Theorem 21 For any subgraph H of G, G ∈ CBU implies that H ∈ CBU. More precisely, if there is a complete bipartite graph K a,b such that V (K a,b ) ⊆ V (G), and such that E(H) = E(G) \ E(K a,b ), then if G belongs to d-CBU then H belongs to (d + 1)-CBU.
Proof. Let A, B be the parts of K a,b . Given a CBU representation of G in R d we are going to build a CBU representation of H in R d+1 . For this, the first d intervals defining each d-box remain unchanged while the last interval is [0, 1] for the vertices in A, [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF][START_REF] Ben-Arroyo Hartman | On grid intersection graphs[END_REF] for the vertices in B, and [0, 3] for the remaining vertices. It is now easy to check that two boxes intersect if and only if they intersect in G and if they are not adjacent in K a,b . It is also clear that the intersections occur on planes orthogonal to e 1 .

2

The graph class CBU is also closed by the addition of false twins.

Theorem 22 For any graph G and any vertex v of G, consider the graph

G v obtained from G by adding a new vertex v ′ such that N (v ′ ) = N (v). Then G ∈ CBU if and only if G v ∈ CBU. Furthermore, if G ∈ d-CBU then G v ∈ (d + 1)- CBU.
Proof. The "if" part is obvious as G is an induced subgraph of G v . For the "only if" part, given a CBU representation of G in R d we are going to build a CBU representation of G v in R d+1 . For this, the first d intervals defining each d-box remain unchanged, and those of v ′ are the same as those of v. The last interval is [0, 1] for v, [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF][START_REF] Ben-Arroyo Hartman | On grid intersection graphs[END_REF] for v ′ , and [0, 3] for all the remaining vertices. It is now easy to check that two boxes intersect if and only if they intersected and if one of them is distinct from v or v ′ . It is also clear that the intersections occur on planes orthogonal to e 1 . 2

Shift graphs were introduced by P. Erdős and A. Hajnal in [START_REF] Erdős | Some remarks on set theory. ix. combinatorial problems in measure theory and set theory[END_REF] (see Theorem 6 therein). Those are the graphs H m whose vertices are the ordered pairs (i, j) satisfying 1 ≤ i < j ≤ m, and where two pairs (i, j) and (k, l) form an edge if and only if j = k or l = i. Note that such graphs admit a homogeneous arc labeling ℓ defined by ℓ({(i, j), (j, k)}) = j, and by orienting any edge {(i, j), (j, k)} from (i, j) to (j, k).

Theorem 23

The graph H m belongs to (m -1)-CBU. Furthermore, H m has a CBU representation such that in the first dimension the vertex (i, j) corresponds to interval [i, j].

Proof. This clearly holds for the one vertex graph H 2 . By induction on m consider a representation of H m-1 , add a false twin for every vertex (i, m -1) and modify the first interval of these new twins, so that the interval [i, m -1] becomes [i, m]. These boxes correspond to the vertices (i, m) with i < m-1. For the vertex (m-1, m), one should add a box [m-1, m]×[-Ω, +Ω]×. . .×[-Ω, +Ω], for a sufficiently large Ω. To deal with the intersections between this box and the boxes of the other vertices (i, m), we add a new dimension such that vertex (m -1, m) has interval [START_REF] Adiga | The hardness of approximating the boxicity, cubicity and threshold dimension of a graph[END_REF][START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF], the vertices (i, m -1) have interval [START_REF] Adiga | The hardness of approximating the boxicity, cubicity and threshold dimension of a graph[END_REF][START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF], the vertices (i, m) with i < m -1 have interval [START_REF] Ben-Arroyo Hartman | On grid intersection graphs[END_REF][START_REF] Bremner | On representing graphs by touching cuboids[END_REF], and all the other vertices have interval [START_REF] Adiga | The hardness of approximating the boxicity, cubicity and threshold dimension of a graph[END_REF][START_REF] Bremner | On representing graphs by touching cuboids[END_REF].

2

Theorem 24 For every n-vertex graph G the following properties are equivalent. Proof. We have already seen that a) ⇒ b). Let us show b) ⇒ c). Consider a homogeneous arc labeling of G, with labels in [2, m-1], for the minimum m. By minimality of m, note that all the labels are used, and thus m -2 ≤ n -1. Let H t m be the graph obtained from the shift graph H m by adding t i,j false twins of vertex (i, j) if there are t i,j + 1 vertices of G whose incoming arcs are labeled i, and whose outgoing arcs are labeled j. For the vertices without incoming (resp. outgoing) arcs assume that those are labeled 1 (resp. m). Consider now an injective mapping γ : V (G) -→ V (H t m ), such that any vertex with incoming and outgoing arcs labeled i, j is mapped to (i, j) or one of its twins. This mapping ensures us that G is a subgraph of H t m . Indeed, for any two adjacent vertices u, v of G linked by an edge labelled j oriented from u to v, their incoming and outgoing arcs are labeled i, j and j, k respectively, for some i < j < k, and thus the vertices γ(u) and γ(v) of H t m are adjacent, as they correspond to or are twins of (i, j) and (j, k).

We now show c) ⇒ d). Consider a graph H t m containing G as a subgraph, for some m, t such that m + t ≤ n + 1. By Theorem 23 and Theorem 22 we have that H t m belongs to (m -1 + t)-CBU, and so to n-CBU. Starting from H t m one can obtain G by successively deleting n -1 stars K 1,b , so by Theorem 21, we have that G belongs to (2n -1)-CBU. Finally, d) ⇒ a) is obvious.

2

It is easy to see that every complete bipartite graph belongs to 3-CBU. By Theorem 21, removing stars K 1,b centered on the smallest part, one obtains that every n-vertex bipartite graph belongs to (⌊n/2⌋ + 3)-CBU. One can reach a slightly better bound from Theorem 6, and the fact that for every graph G, box(G) ≤ ⌊n/2⌋ [START_REF] Roberts | On the boxicity and cubicity of a graph[END_REF].

Corollary 25 Every bipartite graph G belongs to CBU. Furthemore, if |V (G)| = n then G belongs to (⌊n/2⌋ + 1)-CBU.
As already mentioned, some bipartite graphs have arbitrary large boxicity, and thus there is no fixed d such that every bipartite graph belongs to d-CBU. For large girth graphs it is a different.

Theorem 26 For any g ≥ 3, there exist graphs of girth g not contained in CBU.

Proof. Indeed, for any g ≥ 3 there exist graphs of girth g with fractional chromatic number at least 4 [START_REF] Erdös | Graph theory and probability[END_REF]. (Actually, their fractional chromatic number is arbitrarily large). By Theorem 39, such graphs cannot belong to CBU. 2

Nevertheless, the following remains open.

Problem 27 Are there integers d, g such that every girth g graph G of CBU belongs to d-CBU?

The remarks above imply that testing if a bipartite graph belongs to CBU is obvious (computable in constant time), while for girth g graphs the question is more involved, as CBU has such graphs included and some other excluded. The following section treats the computational problem of recognizing CBU graphs.

Recognition

Computing the boxicity of a bipartite graph is a difficult problem. It is known that deciding whether a bipartite graph has boxicity two is NP-complete [START_REF] Kratochvíl | A special planar satisfiability problem and a consequence of its np-completeness[END_REF]. Furthermore, it is proven in [START_REF] Adiga | The hardness of approximating the boxicity, cubicity and threshold dimension of a graph[END_REF] that it is not possible to approximate the boxicity of a bipartite graph within a O(n 0.5-ε )-factor in polynomial time, unless N P = ZP P . By Lemma 20, for every bipartite graph B there is a graph B ′ (obtained in polynomial time) such that the minimum value d for which B ′ belongs to d-CBU is exactly d = box(B) + 1.

Corollary 28 It is NP-complete to decide whether a graph belongs to 3-CBU. Furthermore, unless N P = ZP P , one cannot approximate in polynomial time and within a O(n 0.5-ε )-factor, the minimum value d for which an input graph G belongs to d-CBU.

This implies that for most values d the problem of deciding whether an input graph belongs to d-CBU, cannot be computed in polynomial time, unless N P = ZP P . The hypothesis N P = P being stronger than N P = ZP P , it would be stronger to know that it is NP-complete to decide if an input graph belongs to d-CBU. Problem 31 Is it polynomial to decide whether a graph belongs to CBU?

We have seen that some triangle-free planar graphs, or some graphs with arbitrary large girth, are not in CBU. We can thus restrict the problem.

Problem 32 Is it polynomial to decide whether a planar graph G belongs to CBU? For some g ≥ 3, is it polynomial to decide whether a graph G of girth at least g belongs to CBU?

Recognition through forbidden induced subgraphs

As CBU and d-CBU are closed under induced subgraphs, they are characterized by a set of minimal excluded induced subgraphs, F CBU and F d-CBU . If one of these sets is finite, then recognizing the corresponding class becomes polynomialtime tractable. Thus by Corollary 28, the set F 3-CBU (resp. F d-CBU for d ≥ 4) is not finite, unless P = N P (resp. unless N P = ZP P ). For the set F 2-CBU (resp. F CBU ), we are sure that it is infinite. Indeed, Theorem 14 (resp. Theorem 26) provides an infinite sequence of graphs (G i ) i≥0 not in 2-CBU (resp. not in CBU) such that the girth of G i is at least i. If there was an n such that every graph in F 2-CBU (resp. F CBU ) has at most n vertices, then to exclude G n+1 one would need to have a tree in F 2-CBU (resp. F CBU ). This is not the case as for every tree T , we have that T ∈ 2-CBU ⊆ CBU .

Recognition through homogeneous arc labelings

By Theorem 24, a graph G belongs to CBU if and only if it admits a homogeneous arc labeling. If we are given an orientation of a graph G it is simple to check whether this orientation admits such labeling. For example, one can use linear programming. For each arc uv, set a variable ℓ uv corresponding to a label, and for any two incident arcs, add a constraint. For two arcs uv and uw (resp. uv and wv), the constraint is ℓ uv = ℓ uw (resp. ℓ uv = ℓ wv ). For two arcs uv and vw, the constraint is ℓ uv + 1 ≤ ℓ vw . Problem 31 thus reduces to deciding whether a graph G admits an orientation that is homogeneously labelable. In the following we characterize such orientations.

A cycle (v 0 , v 1 , . . . , v n-1 ) is said badly oriented if there is a vertex v i whose incident arcs are v i-1 v i and v i v i+1 , and if there is no vertex v j whose incident arcs are v j+1 v j and v j v j-1 (indices being considered mod n).

Theorem 33 An orientation of a graph G admits a homogeneous labeling if and only if there is no badly oriented cycle.

Proof. For the "only if" part, consider a badly oriented cycle (v 0 , v 1 , . . . , v n-1 ) with arcs v n-1 v 0 and v 0 v 1 , but with no vertex v j ̸ = v 0 whose incident arcs are v j+1 v j and v j v j-1 . This latter condition implies that in any homogeneous labeling the sequence of labels for the edges (without considering their orientation)

v 0 v 1 , v 1 v 2 , . . . , v n-2 v n-1 , v n-1 v 0 is
non-decreasing, while the former condition implies that the label of v 0 v 1 is greater than the one of v n-1 v 0 , a contradiction. Thus this orientation of G does not allow any homogeneous labeling.

For the "if" part, consider a graph G oriented without badly oriented cycle, and consider a source u, and let us denote v 1 , . . . , v n its out-neighbors. If for every vertex v i , u is its unique in-neighbor, then by recurrence on the number of vertices we assume that G \ {u} has a homogeneous labeling, and we label the arcs incident to u with a sufficiently small value, say -Ω. In that case it is easy to check that this labeling is homogeneous.

Otherwise, let v i and u ′ be vertices such that G has arcs from both u and u ′ toward vertex v i . In that case, consider the oriented graph G ′ obtained from G \ {u} by adding the arcs u ′ v 1 , . . . , u ′ v n , if missing.

Claim 34 G ′ has no badly oriented cycle.

Proof. If G ′ had a badly oriented cycle C, this one should go through a newly added arc u ′ v j . If v i / ∈ C, by replacing the arc u ′ v j by the path (u ′ , v i , u, v j ) one would obtain a badly oriented cycle in G, a contradiction. We thus assume that v i / ∈ C, and now by replacing the arc u ′ v j by the path (u ′ , v i , u, v j ) we obtain a badly oriented closed walk W (that is a walk where there are consecutive "forward" arcs, but no consecutive "backward" arcs). Let us denote P and P ′ the sub-paths of C \ {u ′ v j } ⊊ G linking v i and v j , and linking u ′ and v i , respectively.

Let us show that if the edge incident to v i in P ′ is oriented from v i to the other end, denoted v, then this arc is backward with respect to C. Indeed, the cycle C P ′ of G formed by P ′ and the arc u ′ v i , has consecutive arcs oriented in the same direction, u ′ v i and v i v, and (as G contains no badly oriented cycles) has consecutive arcs oriented in the other direction. The latter pair of arcs belonging both to P ′ ⊂ C, they are forward with respect to C, thus v i v is backward.

Similarly, let us show that if the edge incident to v i in P is oriented from v i to the other end, denoted w, then this arc is backward with respect to C. Indeed, they cycle C P of G formed by P and the arcs uv i and uv j , has consecutive arcs oriented in the same direction, uv i and v i w, and (as G contains no badly oriented cycles) has consecutive arcs oriented in the other direction. The latter pair of arcs belong both to P ⊂ C, or they are the arcs incident to v j . In the former case, these arcs are forward with respect to C, thus v i v is backward. In the latter case, replacing uv j with u ′ v j , one has that the incident arcs of v j in C are oriented in the same direction. this direction is thus the forward direction, and in that case also v i v is backward.

We thus have that the arcs incident to v i cannot be oriented in the same direction (they would form consecutive backward arcs in C), and they are not both oriented from v i to the other end (they would be both backwards although they have distinct directions). Now we distinguish cases according to the position of the consecutive forward arcs in C. We have that: a) there are two consecutive forward arcs in P ∪ {u ′ v j }, or b) there are two consecutive forward arcs in P ′ ∪ {u ′ v j }.

In case a), the cycle C P of G has consecutive forward arcs (by replacing if necessary the arc u ′ v j with uv j ). Since this cycle is not badly oriented it also contains consecutive backward arcs. According to the orientation of the arcs, those backwards arcs cannot be the arcs incident to u, or those incident to v i . Thus they belong both to P ∪ {uv j }, but this would imply that C also contains consecutive backward arcs, a contradiction.

In case b), the cycle C P ′ of G has consecutive forward arcs (by replacing if necessary the arc u ′ v j with u ′ v i ). Since this cycle is not badly oriented it also contains consecutive backward arcs. According to the orientation of the arcs, those backwards arcs cannot be the arcs incident to v i . This would imply that C also contains consecutive backward arcs, a contradiction.

This concludes the proof of the claim 2

So now, by recurrence on the number of vertices we can assume that G ′ has a homogeneous labeling, and let ℓ be the label of the arcs outgoing from u ′ . In that case one can derive a labeling of G by keeping the same labels, and by setting the label ℓ for the arcs outgoing from u. It is easy to check that this labeling is homogeneous.

2

Note that Theorem 33 provides another proof that CBU contains every bipartite graph. Indeed, orienting all the edges from one part toward the other, the direction of the arcs alternate along any cycle, and so there is no badly oriented cycle. Actually, we can go a little further.

Theorem 35 Every graph G with circular chromatic number χ c (G) ≤ 5/2 belongs to CBU.

Proof. A graph G with circular chromatic number χ c (G) ≤ 5/2 has a homomorphism into the circular complete graph K 5/2 that is the 5-cycle. As this graph belongs to CBU the theorem follows from Theorem 37.

2

Note that we cannot replace 5/2 by 8/3 in Theorem 35, as one can easily check that every orientation of K 8/3 contains a badly oriented cycle.

Problem 36 What is the largest c such that every graph G with χ c (G) ≤ c (or with χ c (G) < c) belongs to CBU.

Theorem 37 Given two graphs G, H such that there is an homomorphism γ :

V (G) -→ V (H), then if H ∈ CBU we have that G ∈ CBU.

Proof.

By Theorem 24, the graph H admits a homogeneous arc labeling, ℓ H . Orient the edges of G in such a way that uv ∈ E(G) is oriented as the edge γ(u)γ(v) ∈ E(H), that is from u to v if and only if γ(u)γ(v) is oriented from γ(u) to γ(v) in H. Similarly we copy the labeling of H's arcs by setting ℓ G (uv) = ℓ H (γ(u)γ(v)). One can easily check that this is a homogeneous arc labeling of G, and thus that G belongs to CBU. Theorem 38 (Magnant and Martin [START_REF] Magnant | Coloring rectangular blocks in 3-space[END_REF]) For any χ ≥ 1, there exists a graph in 3-CBU with chromatic number χ.

However, these graphs have bounded fractional chromatic number, and thus have linear size independent sets. Indeed, G. Simonyi and G. Tardos [START_REF] Simonyi | On directed local chromatic number, shift graphs, and borsuk-like graphs[END_REF] showed that shift graphs have fractional chromatic number less than 4. As such a bound extends by adding a false twin and by taking a subgraph, we have the following.

Theorem 39 For any graph G ∈ CBU, χ f (G) < 4, and α(G) > |V (G)|/4.

For planar graphs in CBU, this bound on χ f can be improved by one, but not more.

Theorem 40 For every planar graph G in CBU we have χ f (G) ≤ χ(G) ≤ 3. On the other hand, for every n ≡ 2 ( mod 3) there is a n-vertex planar graph G in CBU such that α(G) = (n + 1)/3, and thus χ

f (G) ≥ n/α(G) = 3 -3 n+1 . Proof.
The first statement follows from Grötzsch's theorem. The second statement follows from graphs constructed by Jones [START_REF] Fraughnaugh | Independence in graphs with maximum degree four[END_REF], which were proved to have independence number α(G) = (n + 1)/3. Those graphs form a sequence J 1 , J 2 , . . . such that J 1 is the 5-cycle (a 1 , b 1 , c 1 , d, e), and such that

J 1 J i+1 d b 1 J i c i b i+1 c i+1 c 1 a 1 e 0 2 1 0 2i 2i 2i + 2 2 2i 2i + 1 2i 2i + 2 a i+1 a i b i
Figure 8: The Jones graphs J 1 and J i+1 , with a homogeneous arc labeling. For every i ≥ 1, this embedding is such that the path a i b i c i is on the outer-boundary. Thus, adding vertices a i+1 , b i+1 , c i+1 does not break planarity. 8). It is already known that those graphs are planar, and it does only remain to show that they belong to CBU. Let us do so by exhibiting a homogeneous arc labeling ℓ. This labeling is such that for any i ≥ 1 we orient the edges a i b i and b i c i toward b i , we orient the edges x i y i+1 , for x, y ∈ {a, b, c}, from x i towards y i+1 , and we set ℓ(a i b i ) = ℓ(a i c i+1) = 2i, ℓ(c i b i ) = ℓ(c i c i+1) = 2i, and ℓ(b i a i+1) = 2i + 1. By examining Figure 8 it is clear that this is a homogeneous arc labeling. 2

J i+1 is obtained from J i by adding three vertices a i+1 , b i+1 , c i+1 such that N (a i+1 ) = {b i , b i+1 }, N (b i+1 ) = {a i+1 , c i+1 }, and N (c i+1 ) = {a i , c i , b i+1 } (see Figure
Although 2-CBU lies in the intersection of CBU and planar graphs, it might be the case that the fractional chromatic number of graphs in 2-CBU is bounded by some c < 3. Indeed, Jones graphs J i , for a sufficiently large i, seem to not be in 2-CBU.

Problem 41 Is there a c < 3 such that every graph G in 2-CBU has fractional chromatic number χ f (G) ≤ c ?

A positive answer to this question, would give support to two conjectures. Let P g≥5 be the set of planar graph with girth at least five, and let P f g≥4 be the set of planar graph with girth at least four, where every 4-cycle bounds a face. Clearly P g≥5 ⊊ P f g≥4 , since these classes avoid Jones graphs it is conjectured that graphs in P g≥5 , or more generally graphs in P f g≥4 , have fractional chromatic number at most c, for some c < 3 [START_REF] Dvořák | Fractional coloring of planar graphs of girth five[END_REF][START_REF] Dvořák | Fractional coloring of triangle-free planar graphs[END_REF]. However, our problem is not a subcase of these conjectures (as K 2,t belongs to 2-CBU \ P f g≥4 ), nor a super-case (as P g≥5 \ 2-CBU is not empty, by Theorem 14).

Computational hardness for many problems

We have seen (c.f. Theorem 8, Corollary 9, and Corollary 10) that many 1subdivided graphs belong to CBU, or even to 3-or 4-CBU. For (≥ 2)-subdivided graphs, the picture is even simpler. Theorem 42 For every graph G, if we subdivide every edge at least twice, the obtained graph belongs to 3-CBU.

Proof. Let us denote v 1 , . . . , v n the vertices of G, and let m = |E(G)|. To construct a CBU representation for any (≥ 2)-subdivision, we start by assigning each vertex v i to the box [3i, 3i + 1] × [n -i, n -i + 1] × [0, 2m]. Then consider each edge e of G in any given order. For the k th edge e assume it links v i and v j , for some i < j, and assume e is replaced by the path (v i , u 1 , . . . , u r , v j ) for some r ≥ 2. Here, u 1 is assigned to [3i + 1, 3i + 2] × [n -j, n -i + 1] × [2k -1, 2k], while the vertices u ℓ with 2 ≤ ℓ ≤ r are assigned to [3i + 2 + (ℓ -2)(3j -3i -2)/(r -1), 3i + 2 + (ℓ -1)(3j -3i -2)/(r -1)] × [n -j, n -j + 1] × [2k -1, 2k] (see Figure 9). One can easily check that the obtained representation is a 3-CBU representation of the subdivided graph.

2

Corollary 43 The problems of Minimum Feedback Vertex Set and Cutwidth are NP-hard, even when restricted to 3-CBU graphs. The problems Maximum Cut, Minimum Vertex Cover, Minimum Dominating Set, and Minimum Independent Dominating Set are APX-hard, even when restricted to 3-CBU graphs.

(i -1, j)

(i, j -1)
(i + 1, j) (i, j + 1) (i -1, j + 1) (i + 1, j -1)

Figure 11: The graph R ′ (n 1 , n 2 ) and the local modification to obtain its 2-CBU representation. From the 2-CBU representation of the grid given above, one has to delete the box of every vertex (i, j), where i and j are even, and if i + j ≡ 2 mod 4 one has to replace the box by 4 smaller boxes.

this implies that every induced subgraph of such a graph belongs to 2-CBU. As the problems Maximum Independent Set and Minimum Vertex Cover are NP-hard for this class (see the proof of Theorem 10 in [START_REF] Francis | The maximum clique problem in multiple interval graphs[END_REF]), those problems are NP-hard for 2-CBU graphs 2

  and d + (c) = 0. Now ab and ac should have the same label, such as ac and bc, but ab and bc should be distinct, a contradiction. Thus a triangle cannot admit a homogeneous arc labeling. This completes the proof of the claim. With similar arguments one obtains the following for short cycles. See Figure 1.

Figure 2 :

 2 Figure 2: The top boxes with respect to ℓ 1 , ℓ 2 , and ℓ 3 are b, d, and a, respectively. The top sequence of this 2-CBU representation is a, b, d, e, a, g, h, g, a.

Figure 3 :

 3 Figure3: Left part : Adding a degree one vertex v i in the representation. This is done in the vertical stripe where the neighbor of v i , v i-1 = v i+1 , is the top box. Right part : Adding v i+1 , . . . , v j-1 . This is done in the vertical stripe where v i and v j are the top box, successively.

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: An example of 2-CBU graph and its associated acyclic orientation

Figure 7 :

 7 Figure 7: The graph G 3 is planar and non CBU. It is however a cover graph.

  a) G belongs to CBU. b) G admits a homogeneous arc labeling. c) G is the subgraph of a graph H t m , obtained from the shift graph H m by iteratively adding t false twins, for some values m, t such that m+t ≤ n+1.

  d) G belongs to (2n -1)-CBU.

Problem 29

 29 For which values d, is it NP-complete to decide whether a graph belongs to d-CBU? Are there values d, in particular for d = 2, for which the problem is polynomial? By Lemma 20, this problem would be solved, for d ≥ 3, if the following problem admits a positive answer. Problem 30 For any d ≥ 3, is it NP-complete to decide whether a bipartite graph B has boxicity at most d? Another computational problem is testing the membership in CBU.

2 8

 2 Chromatic Number and Independent SetsWhile 2-CBU graphs have chromatic number at most 3 (by Grötzsch's theorem), 3-CBU graphs have unbounded chromatic number.

Figure 9 :

 9 Figure 9: Construction of a 3-CBU representation of a 2-subdivision of a graph.

  spanned by e 1 ) let us consider any vertex ordering, v 1 , . . . , v n . For the first dimension, a vertex v i , corresponds to the interval [2i, 2i + 1]. Clearly, none of these boxes intersect. Let us now add the boxes for the vertices added by subdividing the edges of G. For any edge v i v j , in the space spanned by e 2 , . . . , e b+1 , the expansion ensured that the intersection of v i and v j contains a box B ij , that does not intersect any other box of the representation. If i < j, the subdivision vertex of v i v j , is represented by [2i + 1, 2j] × B i,j . The obtained representation is clearly a (b + 1)-CBU representation of the subdivision of G.2

* This research is partially supported by the ANR GATO, under contract ANR-16-CE40-0009 and ANR project GRALMECO (ANR-21-CE48-0004-01)

(1, 1)

(2, 1) (1, 2) Proof. For Minimum Feedback Vertex Set and Cutwidth, this follows from the fact that these problems are NP-hard, and that for any instance, subdividing an edge does not change the solution. For Maximum Cut, it follows from its APX-hardness and the fact that the maximum cut of a graph G and its 2-subdivision

The other problems are shown APX-hard even when restricted to 6-subdivided graphs [START_REF] Chlebík | The complexity of combinatorial optimization problems on d-dimensional boxes[END_REF].

2

When restricted to 2-CBU some of these problems become simpler to handle, as every graph in 2-CBU is planar. Indeed, the Maximum Cut problem turns out to be polynomial time solvable [START_REF] Diaz | Max-cut and max-bisection are NP-hard on unit disk graphs[END_REF], while Minimum Vertex Cover, Minimum Dominating Set, and Minimum Independent Dominating Set admit PTAS [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF][START_REF] Lipton | Applications of a planar separator theorem[END_REF] (with standard techniques), such as Minimum Feedback Vertex Set [START_REF] Kleinberg | Wavelength conversion in optical networks[END_REF]. However, many problems remain NP-hard when restricted to 2-CBU.

Theorem 44 The problems Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Hamiltonian Path, and Hamiltonian cycle are NP-complete, even when restricted to 2-CBU graphs.

Proof. As these problems belong to NP, it remains to show that they are NP-hard for 2-CBU graphs. Let us first show that the induced subgraphs of grids (so called grid graphs) belong to 2-CBU. Consider the n × n grid G such that V (G) = {1, . . . , n} × {1, . . . , n}, and such that the neighbors of any vertex (i, j) are {(i, j -1)(i -1, j), (i, j + 1), (i + 1, j)} ∩ {1, . . . , n} × {1, . . . , n}. Since it suffices to delete some boxes to obtain an induced subgraph, the claim follows by constructing a 2-CBU representation for any such grid G. This construction is obtained by mapping any vertex (i, j) to the box [i+j-1, i+j]×[2i-2j, 2i-2j+3] (see Figure 10). As Domination [START_REF] Clark | Unit disk graphs[END_REF], Hamiltonian Path, and Hamiltonian cycle [START_REF] Itail | Hamilton paths in grid graphs[END_REF] are NP-hard for grid graphs, those problems are NP-hard for 2-CBU graphs.

For the problems Maximum Independent Set and Minimum Vertex Cover, we have to consider a variant of grid graphs, the graph R ′ (n 1 , n 2 ) depicted in Figure 11, and it is easy to see how to modify the construction above in order to obtain a 2-CBU representation of this type of graphs. Again,