MD Romain ; Jouffroy

MD Thomas Baugnon

MD Pierre A Carli

Gilles

MD Gilles Orliaguet
email: gilles.orliaguet@nck.aphp.fr

Pr Gilles

A Orliaguet

David Baker

Emeritus D M Frca

A survey of blood transfusion practice in French speaking paediatric anaesthesiologists

Keywords: red blood cells, blood transfusion, anaemia, haemoglobin, children red blood cells, blood transfusion, children, anaemia, haemoglobin, paediatric anaesthesiology

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Packed Red Blood Cell (PRBC) transfusion is used during both adult and paediatric surgery and resuscitation to maintain an optimal oxygen delivery to organs and tissues in case of significant bleeding. To avoid an overutilization of erythrocyte, the question of when to start blood transfusion, especially in children having hemorrhagic surgery, should be clarified. On the one hand, decisions not to transfuse patients may lead to unnecessary harm due to impaired oxygen delivery and impaired haemostasis [START_REF] Valeri | The red cell transfusion trigger: Has a sin of commission now become a sin of omission?[END_REF][START_REF] Brown | Anemia and hypotension as contributors to perioperative loos of vision[END_REF]. On the other hand, complications associated with transfusion of PRBC are well recognized, including nosocomial infections [START_REF]Perioperative red blood cell transfusion[END_REF], multiple organ system failure [START_REF] Hebert | A multicenter, randomized, controlled clinical trial of transfusion requirements in critical care. Transfusion Requirements in Critical Care Investigators, Canadian Critical Care Trials Group[END_REF], immunosuppression [START_REF] Kessler | Abnormal T-lymphocyte subpopulations associated with transfusion of blood-derived products[END_REF] and transfusion-associated acute lung injury [START_REF] Popovsky | Diagnostic and pathogenetic considerations in transfusion-related acute lung injury[END_REF][START_REF] Silliman | The association of biologically active lipids with the development of transfusion-related acute lung injury: a retrospective study[END_REF]. The benefit of PRBC transfusion must be weighed against risk. Blood transfusions are administered to increase the blood oxygen carrying capacity [START_REF] Lucking | Dependence of oxygen consumption on oxygen delivery in children with hyperdynamic septic shock and low oxygen extraction[END_REF][START_REF] Casutt | Factors influencing the individual effects of blood transfusions on oxygen delivery and oxygen consumption[END_REF]. Most risks and benefits of PRBC are quite similar in adults and in children. For example, the risk of contracting a viral disease or of developing an adverse reaction after a PRBC transfusion is the same in adults and in children [START_REF] Desmet | Transfusion in pediatrics[END_REF]. Meanwhile, the imbalance between needs and availability of blood products has widened. These phenomena have combined to question the traditional indications for transfusion, a debate which is fuelled by the growing concern of clinicians and the public to see the therapeutic indications relying on evidence based medicine.

Recommendations have been established on transfusion thresholds in adults [START_REF] Samama | Recommendations of the French Health Products Safety Agency[END_REF]. The determination of the thresholds was enabled by research surveys of transfusion practices in adult anaesthesia and resuscitation with studies of morbidity and mortality according to various thresholds transfusions [START_REF] Hebert | A multicenter, randomized, controlled clinical trial of transfusion requirements in critical care. Transfusion Requirements in Critical Care Investigators, Canadian Critical Care Trials Group[END_REF]. Thus, clinicians were given recommendations for PRBC transfusion in adult anaesthesia and intensive care based on evidence based medicine [START_REF] Samama | Recommendations of the French Health Products Safety Agency[END_REF]. In paediatrics, scientific evidence is so far not available and there are no recommendations for transfusion thresholds. We therefore undertook a survey among French speaking paediatric anaesthesiologists, firstly to determine the transfusion threshold and secondly to assess the volumes of PRBC transfusion in paediatric anaesthesia according to different clinical situations.

Materials and Methods

This survey attempted to give an overview of the use of PRBC in routine practice by Frenchspeaking paediatric anaesthesiologists. As a result, the study was confined to all active members of the Association Des Anesthesistes Reanimateurs Pediatriques d'Expression Francaise (ADARPEF).

A postal questionnaire (Table 1), with stamped, self-addressed envelopes, was sent to all paediatric anaesthesiologists who were established members of the ADARPEF. A second mailing was sent with a covering letter 3 months later to all physicians who failed to respond. Non-responders (NR) received a third mailing 6 months later, and were directly contacted by phone by one of the investigators (RJ and TB). Overall, the survey was undertaken between November 2007 and November 2008 and the replies were collated using Microsoft Excel.

Statistical Analysis

For each scenario, the median threshold haemoglobin concentrations for transfusion, as well as the median [95% CI] volumes of PRBC to be transfused, were calculated. A two-way ANOVA was performed to compare the haemoglobin threshold and the volume of PRBC for the different scenarios and the different operative phases, followed by the Student t-test in cases of normal

Results

Out of the 324 registered ADARPEF members, 175 (54%) returned the questionnaire. Most physicians were experienced, with a mean of 15.5 years of practice in paediatric anaesthesia. Ninety seven percent of the responders had 10 years or more and 37% had more than 20 years experience in the field of paediatric anaesthesia. Thus a majority of the responders were experienced anaesthesiologists. About 9% of the responders worked in private practice while 91% worked in a public hospital. The background and the academic characteristics of the responders, the characteristics of the clinical activity and of the paediatric anaesthesiology unit as well as the type of Post Anaesthesia Care Unit (PACU) employed are listed in Table 1. The characteristics of the red blood cell resources and transfusion practice are listed in Table 2. The practices of PRBC transfusion for each scenario and according to the different operative periods are presented in the figures 1, 2 and 3. The median [95% CI] calculated haemoglobin target was 11.3 [9.8-12.8] g.dl -1 for scenario 1, 11.3 [9.7 -12.9] g.dl -1 for scenario 2, 11.2 [9.5 -12.9] g.dl -1 for scenario 3, and 12.6

Discussion

In this survey we have identified significant differences in transfusion practice patterns among paediatric anaesthesiologists with a median [95% CI] transfusion threshold of 7.6 [6.6 -8.6] g.dl -1 and a median [95% CI] PRBC volume transfusion of 11.7 [6.6 -16.8] ml.kg -1 . Anaemia, underlying medical condition, hemodynamic instability, haemostasis disorders and sepsis were the most significant factors modifying the decision to transfuse.

The response rate to the questionnaire was 54%, which is common in mailed questionnaire surveys.

The response rate in our study is comparable to the response rate observed in studies performed in the PICU on similar subjects. In fact, the response rate observed in our study is lower than in the study of Laverdiere [START_REF] Laverdiere | Survey on transfusion practices of pediatric intensivists[END_REF] but approximately the same as in the study of Nahum [START_REF] Nahum | Blood transfusion policy among European pediatric intensive care physicians[END_REF], Hansen [START_REF] Hansen | Therapeutic approaches to neonatal jaundice: an international survey[END_REF] and Sacher [START_REF] Sacher | Blood component therapy during the neonatal period: a national survey of red cell transfusion practice[END_REF].

The present survey has shown that the volume of blood transfusions among the ADARPEF members varies, ranging from 0 to more than 20 ml.kg -1 for the same case scenario. In our study, the median [95% CI] preoperative haemoglobin threshold was about 7.5 [6.8 -8.2] g.dl -1 . This value is in agreement with the study of Söderlind's [START_REF] Soderlind | Use of albumin, blood transfusion and intraoperative glucose by APA and ADARPEF members: a postal survey[END_REF] who found a value of 7.5 g.dl -1 in children aged 6 to 16 years. This study [START_REF] Soderlind | Use of albumin, blood transfusion and intraoperative glucose by APA and ADARPEF members: a postal survey[END_REF], found that a haemoglobin threshold, called 'magic haemoglobin number' (MHN), was predetermined by about 75% of the clinicians, while the others were using an individual approach. In addition, this MHN was higher for premature babies, but no information was given about the MHN for children who were not premature or under 6 years of age. The other point revealed by our study was that the ADARPEF members tended to accept lower haemoglobin concentrations before starting PRBC transfusion compared to APAGBI (Association of Paediatric Anaesthetists of Great Britain and Ireland) members [START_REF] Soderlind | Use of albumin, blood transfusion and intraoperative glucose by APA and ADARPEF members: a postal survey[END_REF]. This underlines that PRBC policy probably differs from one country to an other and that PRBC transfusion practices have evolved over time, probably in relation to the development of evidence based medicine. In the paediatric intensive care unit (PICU), transfusion triggers ranging from 7 to 13 g.dl -1 were reported in one survey [START_REF] Laverdiere | Survey on transfusion practices of pediatric intensivists[END_REF]. The difference with our survey is probably related to differences in the medical In our study, the median preoperative haemoglobin threshold varies from 6.9 g.dl -1 to 8.9 g.dl -1 and the postoperative threshold varies from 7.0 g.dl -1 to 9.2 g.dl -1 . As far as we know, there are no existing data regarding this specific point in the literature. These data emphasise the fact the ADARPEF members wait until relatively low haemoglobin levels are reached before starting PRBC transfusion. This level, of 7 to 8 g.dl -1 , could be an extrapolation to paediatric practice of the AFSSAPS's guidelines of transfusion threshold in adult patients [START_REF] Samama | Recommendations of the French Health Products Safety Agency[END_REF][START_REF] Galperine | Blood transfusion in children[END_REF].

We hypothesize that the possibility of an haemoglobin level documentation in less than 30 minutes for the majority of the cases (82%), confirmed by laboratory tests before starting PRBC transfusion (89%), could explain why only 39% of the physicians decided to transfuse using solely the Hemocue ® , a tool widely available in the operating room (97%) and in the PACU (93%).

In the PICU, many guidelines related to blood transfusion are based on expert opinion, common practice and evidence extrapolated from the studies in adults, rather than on high-quality clinical trials conducted in children [START_REF] Blanchette | Guidelines for auditing pediatric blood transfusion practices[END_REF]. Suggested transfusion thresholds published in textbooks ranged from 4 to 16 g.dl -1 according to different underlying conditions [START_REF] Dalens | Anesthésie pédiatrique[END_REF][START_REF] Miller | Médecine-Science edn[END_REF] but there is no consensus regarding the haemoglobin concentration that leads a physician to prescribe PRBC transfusion in this group [START_REF] Desmet | Transfusion in pediatrics[END_REF]. However, taking into account physiopathological considerations, a threshold of 7 g.dl -1 might be suggested, since most children are not affected by cardiovascular disease, while the delivery of oxygen to the tissues is thought to be greater in children than in adults [START_REF] Dalmas | Transfusion et épargne sanguine chez l'enfant de moins de 5 ans. Conférences d'actualisation de la SFAR[END_REF]. In the PICU setting, the study of Lacroix et al. [START_REF] Lacroix | Transfusion strategies for patients in pediatric intensive care units[END_REF] emphasizes that children may benefit from a restrictive transfusion strategy to minimize PRBC transfusion in paediatric patients with a stable hemodynamic condition. A restrictive transfusion strategy with a haemoglobin threshold of 7 g.dl -1 resulted in a 96% reduction in the number of children who had a transfusion exposure and a 44% decrease in the number of PRBC transfusions administered, without increasing the rates of new or progressive Multiple Organ Dysfunction Score in stable critically -ill children [START_REF] Lacroix | Transfusion strategies for patients in pediatric intensive care units[END_REF]. A previous 8 study, performed with a similar design, has already shown similar results in adults [START_REF] Hebert | A multicenter, randomized, controlled clinical trial of transfusion requirements in critical care. Transfusion Requirements in Critical Care Investigators, Canadian Critical Care Trials Group[END_REF]. Another retrospective study has also shown that for children with haemoglobin levels under 9 g.dl -1 , PRBC transfusions are associated with an increase in resource utilization (oxygen requirements, requirement for mechanical ventilation, requirement for vasoactive agent infusion and increase of PICU and hospital length of stay) [START_REF] Goodman | Pediatric red blood cell transfusions increase resource use[END_REF]. Here there is a major difference with our study because the health status of patients during anaesthesia is different from the health status of patients hospitalized in the PICU. Thus, during surgery the target range after transfusion is usually set higher because bleeding may still be active at the time of blood transfusion and may persist during PRBC administration, at least, until the end of surgery. So, when a paediatric anaesthesiologist decides to transfuse, he may deliberately decide to transfuse more than immediately required (ie more than required according to the actual and the targeted haemoglobin level) taking into consideration the persistent bleeding.

In our survey, we found that about 80% of physicians take the age of the child into consideration to modify the indication for PRBC transfusion. This result is in agreement with the survey by Söderlind et al. [START_REF] Soderlind | Use of albumin, blood transfusion and intraoperative glucose by APA and ADARPEF members: a postal survey[END_REF], although the target age changing the threshold for starting PRBC transfusion is not known with any accuracy. In our survey, the median [95% CI] volume transfused was 11.7 [6.6 -16.8] ml.kg -1 for all scenarios and for the scenarios where children were older than 5 years of age it was 11.1 [6.9 -15.3] ml.kg -1 suggesting a difference in favour of younger children. The cut off age is probably around one year, in agreement with what was shown by Söderlind et al. [START_REF] Soderlind | Use of albumin, blood transfusion and intraoperative glucose by APA and ADARPEF members: a postal survey[END_REF] and confirmed by Lienhart et al. [26]. Taking age into account as an important modifying factor, the median target was 11.3±1.5 g.dl -1 for children older than 5 years, whereas in scenario 4, describing a four month old infant, the median [95% CI] target was higher (12.6 [9.7 -15.5] g.dl -1 ), suggesting that one year of age could be the cutt off, which is in accordance with expert opinion [26]. The fact remains however that, there are no studies in PICU or in paediatric anaesthesia determining precisely which targeted age should be used. Another consideration relates to the volume of PRBC to be transfused. According to the study by Davies et al. [START_REF] Davies | Calculating the required transfusion volume in children[END_REF], to achieve a targeted haemoglobin value the "transfusion factor" should be taken into account to determine precisely the volume of PRBC which should be infused. One limitation of this study is that it was conducted in the PICU where the problem of the transfused volume is essential because of a potential risk of overloading, whereas during surgery anaemia is acute and often associated with hypovolemia. Thus, if the "transfusion factor" is important in the PICU setting it is less so in paediatric anaesthesia since the aim of the PRBC transfusion is to correct the anaemia, where the risk of overloading is low because of concomitant intraoperative hypovolemia.

Interestingly, in our study the determination of the volume to be transfused was based on the following formula in most of the cases (68%): [(Hb expected -Hb measured) x 3)/bodyweight (kg)], where the constant 3 corresponds to the "transfusion factor". The median [95% CI] haemoglobin target in our survey was 11.6 [9.7 -13.5] g.dl -1 and is in accordance with the results observed by Söderlind et al. [START_REF] Soderlind | Use of albumin, blood transfusion and intraoperative glucose by APA and ADARPEF members: a postal survey[END_REF], who proposed a "transfusion target level" of 10 -12 g.dl -1 .

The survey by Laverdière et al. [START_REF] Laverdiere | Survey on transfusion practices of pediatric intensivists[END_REF], found that age, clinical tolerance of anaemia, associated pathology, haemostatic disorder, hemodynamic instability and sepsis could modify the threshold of PRBC transfusion. We have observed similar results and suggest that the most important element modifying the transfusion starter is the clinical tolerance of anaemia because it is the most accessible element during anaesthesia in operating room.

Certain limitations of our study require comment. The first is that it did not involve exclusively paediatric anaesthetists. The second limitation is that responders were quite exclusively French (only 2 responders were not French), despite trying to obtain the maximum of responses. However, we feel that our results still reflect transfusion practices of ADARPEF members, with the ADARPEF including about 85% of French paediatric anaesthesiologists. The third limitation is that our survey is based on voluntary declarations of paediatric anaesthesiologists, while the daily practice of the non responders may be different from the results of our survey. On the other hand, we may assume that the responders are probably those who are most concerned and interested by In conclusion, our survey shows that the haemoglobin threshold and the volume for PRBC transfusion vary significantly among French-speaking paediatric anaesthesiologists, for the same kind of patients. The reported median [95% CI] haemoglobin threshold during the pre-operative period was 7.9 [6.9 -8.9] g.dl -1 , 7.3 [6.4 -8.2] g.dl -1 in the intra-operative and 8.1 [7.0 -9.2] g.dl -1 in the post-operative period. The declared median [95% CI] PRBC volume transfused was 11.7 [6.6 -15.8] ml.kg -1 and the median [95% CI] haemoglobin target was 11.6 [9.7 -13.5] g.dl -1 . The most important factors modifying paediatric anaesthesiologist's decisions were the clinical tolerance of anaemia, an underlying medical condition, the hemodynamic stability, a haemostasis disorder and a sepsis. We also observed that the majority of practitioners want to confirm the haemoglobin level obtained with the Hemocue using laboratory test before starting PRBC transfusion.

Responses to the Reviewer(s)' Comments Response to Reviewer: 1

In order to shorten the manuscript, I suggest that the same questions relative to each of the 4 clinical scenarii be printed only once as Annex 2, and that the last part on the clinical elements that could modify the decision to transfuse be presented as Annex 3. We agree with the suggestion of Reviewer 1. Accordingly, we have modified the Materials and Methods section of the revised manuscript and we have introduced Annex 2 and 3.

Minor remarks: -Introduction, L10: Despite the high rate of erythrocyte utilization: what do you mean?

We have modified the sentence to make it clearer. The revised version is: "To avoid an overutilization of erythrocyte, the question of when to start blood transfusion, especially in children having hemorrhagic surgery, should be clarified".

-Introduction, L18: impaired haemostasis is more caused by haemodilution than by the absence of transfusion of PRBC: please modify. This sentence has been modified:" On the one hand, decisions not to transfuse patients may lead to unnecessary harm due to impaired oxygen delivery and impaired haemostasis [START_REF] Valeri | The red cell transfusion trigger: Has a sin of commission now become a sin of omission?[END_REF][START_REF] Brown | Anemia and hypotension as contributors to perioperative loos of vision[END_REF]." -Results, L5-6: Sixteen members did not return the questionnaire and were excluded: this sentence is useless. Or do you mean that these 16 members answered without filling in the clinical questionnaire? This sentence should probably best be deleted. We agree with the reviewer that this sentence is useless; accordingly this sentence has been deleted.

-Discussion, p9, L2: delete "in critically ill children". The modification has been done and "in critically ill children" has been deleted.

-Discussion, p9, L42-44: suggesting that one year of age could be the cutt off. The suggested modification has been done in the revised version of the manuscript. Results: Out of the 324 active members of the ADARPEF, 175 (54%) completed the questionnaire. The threshold for blood transfusion varied from 6 g.dl -1 to 12 g.dl -1 depending on the scenario. The haemoglobin threshold for blood transfusion and the volume of blood transfused vary among ADARPEF physicians, for the same class of patients. The median [95% CI] haemoglobin threshold for starting blood transfusion was 7.9 [6.9-8.9] g.dl -1 , 7.3 Key words: red blood cells, blood transfusion, children, anaemia, haemoglobin, paediatric anaesthesiology

F o r P e e r R e v i e w

  A two-part questionnaire was designed. The first part of the questionnaire collected data about: the physician's background; the possibility of documentation of the indication for PRBC transfusion and the general procedure of PRBC transfusion (Annex 1). The second part of the questionnaire described four scenarios of common clinical situations in paediatric anaesthesia, each one containing six questions. The four scenarios are presented in Annex 2. For each scenario, physicians were asked to indicate the lowest haemoglobin concentration resulting in a decision to transfuse RBC (1) before, (2) during (3) and after surgery (4), as well as the volume of PRBC they would transfuse. At the end of each scenario, physicians were asked to indicate which clinical determinants could change their decision regarding PRBC transfusion. Several choices were possible (Annex 3).

[ 9 . 7 -

 97 [START_REF] Nahum | Blood transfusion policy among European pediatric intensive care physicians[END_REF].5] g.dl -1 for scenario 4.

  patients hospitalised in the PICU; for example the ASA physical status is probably higher in the PICU population than in common clinical situations of paediatric anaesthesia.

  that non -responders are seldom exposed to the problem of PRBC transfusion in children. Finally, the fourth limitation is that the survey was a scenario-based study, restricted to the recording of what paediatric anaesthesiologists say they will do rather than what actually happens.

Figure 1 :

 1 Figure 1: Haemoglobin threshold for starting blood transfusion in the preoperative period.

Figure 2 :

 2 Figure 2: Haemoglobin threshold for starting blood transfusion during the intra operative period.

Figure 3 :

 3 Figure 3: Haemoglobin threshold for starting blood transfusion at the end of surgery.

  Figure 1

Annex 1 : 1 - 2 - 3 - 4 - 8 --Dedicated to paediatric patients 9 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 1 Annex 2 : 1 A 15 - 2 A 5 - 3 A 8 - 4 A 4 -Questions 1 - 4 - 6 -Annex 3 :-

 11234891112131415161718121152538441463 Questionnaire for the survey collecting data regarding physician's background; the possibility of documentation of the indication for PRBC transfusion and the general procedure of PRBC transfusion. Academic rank? (Please select only one answer below) Type of practice? (Please select only one answer below) -Exclusively paediatric -Adult mixed with frequent paediatric activity (>50 %) -Adult mixed with occasional paediatric activity (<25%) Years of practice in paediatric anaesthesia? Type of hospital? (Please select only one answer below) Type of Post Anaesthesia Care Unit? (Please select only one answer below) -Mixed (adult and pediatric) Anaesthesiologist dedicated to the Post Anaesthesia Care Unit? Possibility of a determination of haemoglobin concentration in less than 30 minutes in the operating room? (Please select only one answer below) Availability of an Hemocue ® (HemoCue France, Meaux, France) in the operating room? Possibility of a determination of haemoglobin concentration in less than 30 minutes in the Post Anaesthesia Care Unit? Availability of an Hemocue ® (HemoCue France, Meaux, France) in the Post Anaesthesia Confirmation of the indication of PRBC transfusion using laboratory test with haemoglobin concentration measurement (excepted in case of immediate urgency)? Confirmation of the indication of PRBC transfusion based only on the results of Hemocue ® (excepted in case of immediate urgency)? Determination of the volume of PRBC transfusion based on? (Please select only one In case of use of a formula, which one? (Please select only one answer below) -[(Hb expected -Hb measured) x 3] / bodyweight (Kg) -(Ht expected -Ht measured) / bodyweight (Kg) The four scenarios of common clinical situations in paediatric anaesthesia and associated questions.-Scenario year-old adolescent, weighing 50 kg, ASA physical status 2 and suffering from an idiopathic scoliosis. Currently, 7 days following an anterior spinal fusion, the child is scheduled for the posterior spinal fusion. All the PRBC from autologous donations have already been used. The intervention cannot be postponed. The preoperative hemodynamic condition is stable.-Scenario year-old child, weighing 20 kg, ASA physical status 1, undergoing urgent laparotomy for appendicular peritonitis without shock.-Scenario year-old child, weighing 25 kg, ASA physical status 2, with asthma (2 to 3 asthma attacks per month, treated by beta 2-agonists and an inhaled corticoid), requires an emergency reintervention for hemostasis 7 days after a tonsillectomy. The hemodynamic status is stable and lung auscultation is normal.-Scenario month-old infant, weighing 5 kg, ASA physical status 1, suffering from intussusception with rectal bleeding since several hours. Surgery is required after failure of conservative management. Before surgery, indicate the lowest haemoglobin concentration resulting in a decision to transfuse RBCs? (Please select only one answer) 6 -7 -8 -9 -10 -11 -12 2-Which volume of blood do you prescribe (specify ml or ml/kg)? If yes, witch threshold do you use in the intraoperative period? (Please select only one If yes, witch threshold do you use on arrival in the PACU? (Please select only one answer) Clinical determinants of red blood cell transfusion, other than haemoglobin level, that could modify the decision to transfuse. -Child's age -Clinical tolerance of anaemia (ex: tachycardia) -Underlying medical history and associated pathology (ex: cystic fibrosis), Need for re intervention during the first 7 postoperative days. There are so far no existing consensus guidelines regarding red blood cell transfusion during paediatric surgery and there is a little information regarding red blood cell transfusion policy among paediatric anaesthesiologists. Objectives: To determine the transfusion threshold and the volumes of packed red blood cell (PRBC) transfusion among French speaking paediatric anaesthesiologists. Materials and Methods: A questionnaire of case scenarios was sent to active members of the French Language Society of Pediatrics Anesthesiologists (ADARPEF).

[ 6 .

 6 4-8.2] g.dl -1 and 8.1 [7.0-9.2] g.dl -1 in the pre-, intra-and post-operative phase respectively.The median [95% CI] PRBC volume transfused was 11.7[6.6-16.8] ml.kg -1 and the median haemoglobin target was 11.3 [9.8-12.8] g.dl -1 . Physicians ranked anaemia (99%), underlying medical conditions (95%), hemodynamic instability (89%), haemostasis disorder (86%) and sepsis (79%) as the most significant factors affecting their transfusion decisions. Most paediatric anaesthesiologists (89%) measure the haemoglobin level before PRBC transfusion.Conclusions: This survey identifies significant differences in transfusion practice patterns among paediatric anaesthesiologists with a median transfusion threshold of 7.6 [6.6-8.6] g.dl -1 and a median PRBC volume transfusion of 11.7[16.8-6.6] ml.kg -1 .

  variables, whereas Fisher's exact test was used for discrete variables, where appropriate.

	F o r
	P
	e
	e r
	R
	e
	v i e
	w

Table 1 :

 1 Background, academic characteristics and clinical activity of the 175 responders.

	6	7	8	9	10	11	12
	Postoperative haemoglobin transfusion threshold (g/dl)

Table 2 :

 2 Characteristics of the red blood cell resources and transfusion practice.Results are expressed in percentage of responders.

	Characteristics


Jaroslav Nesetril
email: nesetril@kam.ms.mff.cuni.cz

J Nešetřil

P Ossona De Mendez

X Zhu

Colouring Edges with many Colours in Cycles

Keywords: graph, colouring, arboricity 2000 MSC: 05C15 Colouring of graphs and hypergraphs

come   L'archive ouverte pluridisciplinaire

Introduction

In this paper, we consider the following problem: given a graph G, how many colours do we need to colour the edges of G in such a way that every cycle gets "many" colours?

Of course, the answer to this question depends on the precise meaning of "many". If we require that each cycle γ of length l of G gets l colours, i.e., every cycle is rainbow, then the minimum number of colours needed is equal to the maximum size of a block of G, as two edges of G belong to a common cycle if and only if they belong to the same block. If we require that every cycle gets at least 2 colours, i.e., every colour class induces a forest, then the minimum number of colours needed is the arboricity Arb(G) of G, and its determination is solved by the well-known Nash-Williams' theorem we recall now.

Denote by V (G) and E(G) the vertex set and the edge set of G. Also denote by |G| = |V (G)| (resp. G = |E(G)|) the order of G (resp. size). For A ⊆ V (G) denote by G[A] the subgraph of G induced by A. By Nash-Williams' theorem [START_REF] St | Edge-disjoint spanning trees of finite graphs[END_REF][START_REF]Decomposition of finite graphs into forests[END_REF], the arboricity of a graph G is given by the formula:

Arb(G) = max A⊆V (G),|A|>1 G[A] |A| -1 . (1)
Here we consider a generalization of these two extreme cases. A general form of our problem is captured by the following:

Given an unbounded non-decreasing function f : N → N and an integer p, what is the minimum number N f (G, p) of colours needed to colour the edges of a graph G in such a way that each cycle γ gets at least min(f (|γ|), p + 1) colours?

Thus for p = 1 and f (n) ≥ 2 we get N f (G, p) = Arb(G). For an arbitrary graph G, it is usually difficult to determine N f (G, p). Our interest is to find upper bound for N f (G, p) in terms of other graph parameters, and upper bound for N f (G, p) for some nice classes of graphs and/or for some nice special functions f . Many colouring parameters are bounded for proper minor closed classes of graphs. It is natural to ask for which functions f is N f (G, p) bounded for any proper minor closed class C of graphs. We shall prove (Lemma 1) that if f (2 p-1 ) > p -1 for some value of p then there is a (quite small) minor closed class of graphs C, such that N f (G, p) is unbounded. On the other hand, we prove (Corollary 6) that if f (x) ≤ ⌈log 2 x⌉ for all x then N f (G, p) is not only bounded on proper minor closed classes of graphs, but actually bounded on a class C if and only if C has bounded expansion (to be defined in Section 3).

Next we consider the special function f (x) = x. For this special function, the parameter N f (G, p + 1) is denoted as Arb p (G) and is called the generalized p-arboricity of G. So Arb p (G) is the number of colours needed if we require that each cycle of G gets at least p + 1 colours or is rainbow if its length is smaller than p + 1. Note that if p = 1, then Arb p (G) is the arboricity Arb(G) of G. We shall relate the generalized p-arboricities of a graph to the density of its shallow topological minors. Toward this end we define the following notions, which are analogous to those defined in [START_REF]Grad and classes with bounded expansion I. decompositions[END_REF] and [START_REF]From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits[END_REF]. The main difference is that here we consider multigraphs.

Let G be a multigraph and let r be a half integer. A multigraph H is a shallow topological minor of G at depth r if a ≤ 2r-subdivision of H is a subgraph of G. We denote by G r the class of the multigraphs which are shallow topological minors of G at depth r. Hence we have Notice that the class G 0 is exactly the monotone closure of G, that is the class of all the subgraphs of G.

We denote by ∇ / r (G) the maximum density of a graph in G r, that is:

∇ / r (G) = max H∈G r H |H| . (2)
In this paper, we will give lower and upper bounds for Arb p (G) based on ∇ / p-1 2 (G)). For p = 1, notice that it is an easy consequence of Nash-Williams' Theorem that

⌈ ∇ / 0 (G)⌉ ≤ Arb 1 (G) ≤ 2⌈ ∇ / 0 (G)⌉.
In this paper, we shall show (Theorem 15) that for any positive integer p, there is a polynomial P p such that for any graph G,

∇ / p-1 2 (G) 1/p ≤ Arb p (G) ≤ P p ( ∇ / p-1 2 (G)). ( 3
)
The paper is organized as follows: In Section 2, we consider the key case of graphs with bounded tree-depth. In particular, we establish that if f (2 p-1 ) > p -1 for some value of p then there is a minor closed class of graphs C (namely the class of graphs with tree-depth at most p) such that N f (G, p) is unbounded. In Section 3, we prove that if, for some unbounded non-decreasing function f and each fixed integer p, the value N f (G, p) is bounded for graphs in a class C, then the class C has bounded expansion. We prove also that, conversely, if C has bounded expansion and f 0 (x) = ⌈log 2 x⌉ then sup G∈C N f0 (G, p) is bounded for each integer p. In Section 4, we establish (3), which is the main result of this paper. For the sake of improving the readability of this paper, the proofs of two difficult lemmas used in Section 4 are actually postponed to Section 5. In Section 6 we consider a dual version of the problem.

Longest Cycles and Tree-Depth

Let us recall some definitions. The height of a rooted forest is the maximum number of vertices in a path from a root to a leaf. The closure of a forest F is the graph on V (F ) in which xy is an edge if and only if x is an ancestor of y or y is an ancestor of x. The tree-depth td(G) of a graph G is the minimum height of a rooted forest F such that G is a subgraph of its closure.

In this section we establish how the concept of tree-depth introduced in [START_REF]Tree depth, subgraph coloring and homomorphism bounds[END_REF] is related to the length of the longest cycle of a graph. It will follow that if f (2 p-1 ) > p-1 for some value of p then there is a minor closed class of graphs C on which N f (G, p) is unbounded. Lemma 1. Let p be an integer such that the function f satisfies f (2 p-1 ) > p -1. Let C be the class of graphs with tree-depth at most p.

Then N f (G, p) is unbounded on C.
Proof. Let N be an arbitrarily large integer. Let G be the closure of a rooted complete q-ary tree Y of height p, where q = N ( p 2 ) + 1. Let r be the root of Y . Given a leaf v of Y , there are N ( p 2 ) ways to colour the edges of the subgraph of G induced by v and its ancestors with N colours, and let φ(v) ∈ {1, . . . , N ( p 2 ) } be the encoding of this colouration corresponding to the leaf vertex v. For non leaf vertices v we define φ(v) by induction on the descending height as the majority value of φ(x) among the children of v. The root r has at least ⌈q/N ( p 2 ) ⌉ = 2 sons v with φ(v) = φ(r). Inductively, the root r is the root of a complete binary subtree Y ′ of Y , all vertices of which have the same φ-value as r. The closure of Y ′ contains a cycle γ of length 2 p-1 , and this cycle gets at most p -1 colours (see Fig 2). As min(f (|γ|), p) = p we conclude that N f (G, p) > N and thus N f (G, p) is unbounded. Remark that the proof of Lemma 1 is a variant of an old trick of R. Goldblatt. Lemma 1 shows that we cannot expect N f (G, p) to be bounded on proper minor closed classes of graphs if f (x) > ⌈log 2 x⌉. In Section 3, we shall show that if f (x) ≤ ⌈log 2 x⌉ then N f (G, p) are not only bounded on proper minor closed classes of graphs, but actually bounded on a class C if and only if C has bounded expansion. This provides yet another characterization of this robust notion.

We now prove that the connection with tree-depth shown in Lemma 1 is actually deeper in the sense that a 2-connected graph has no long cycles if and only if it has a small tree-depth. (Note that 2-connectivity has to be assumed.) Lemma 2. Let G be 2-connected graph and let L be the maximum length of a cycle in G. Then

1 + ⌈log 2 L⌉ ≤ td(G) ≤ L -1 2 + 2.
Proof. The first inequality is a consequence of the monotonicity of tree-depth and the exact values of tree-depth for cycles: td(C n ) = 1 + ⌈log 2 n⌉. The remaining of the proof will concern the second inequality. Consider a Depth-First Search tree Y of G and let r be the root of Y . Let h = height(Y ). For a vertex x let level(x) be the height of x in Y . The rooted tree Y naturally defines a partial order by x y if x belongs to the tree-path from r to y. A basic property of DFS-trees is that two adjacent vertices are always comparable with respect to (DFS-trees have no cross edges), so that G ⊆ Clos(Y ) thus td(G) ≤ h.

For a vertex x, let low(x) be the smallest vertex y (with respect to ) which is adjacent by an edge not in Y to a vertex z x. Notice that such a vertex exists as G is 2-connected and that for x = r it holds low(x) ≺ x. Moreover, if low(x) = r, the fact that low(x) is not a cut-vertex of G implies that there exists y such that low(y) ≺ low(x) ≺ y ≺ x.

Let P = (v 1 = r, . . . , v h ) be a longest root-to-leaf path of Y . We inductively define indexes a 1 , b 1 , . . . , a k , b k ∈ {1, . . . , h} as follows: let a 1 = h and let v b1 = low(v a1 ). For i ≥ 1, if b i = 1 then let v bi+1 be the minimum low of a vertex z such that v bi ≺ z ≺ v ai , let v ai+1 be such that v bi ≺ v ai+1 ≺ v ai and low(a i+1 ) = b i+1 , and let e i be a non-tree edge linking some w v ai and v bi . This process stops at some value k such that b

k = 1. Notice that a i+2 b i for 1 ≤ i ≤ k -2.
Let γ i be the fundamental cycle of e i and let γ be the symmetric difference of all the γ i 's. Then γ is a cycle and each edge of P ∪ {e 1 , . . . , e k } belongs to 2 of the cycles

γ 1 , . . . , γ k , γ. Hence 2(h+k -1) ≤ |γ 1 |+• • •+|γ k |+|γ| ≤ (k +1)L, i.e. h ≤ k+1
2 (L-2)+2 (see Fig. 2).

Moreover, γ contains at least two tree edges (either k = 1 and γ = γ 1 or k > 1 and then It is not clear whether the quadratic bound of Lemma 2 is tight. We propose the following problem (compare with [START_REF] Kenkre | A bound on the chromatic number using the longest odd cycle length[END_REF] where the chromatic number of a graph is bounded using the length of the largest odd cycle).

a 2 < a 1 and b k < b k-1 ) thus L ≥ |γ| ≥ k + 2 hence k ≤ L -2. Altogether, we obtain h ≤ L-1 2 + 2. v b 5 = r v a 1 = v h v b 1 v a 2 v b 2 v a 3 v a 5 = v b 3 v a 4 v b 4
Problem 1. For a 2-connected graph G, denote by L(G) the length of the longest cycle in G.

Does there exist a constant C such that for every 2-connected graph the following inequality holds: td(G) ≤ C L(G)?

Classes of graphs with bounded expansion

Classes with bounded expansion have been introduced in [START_REF] Nešetřil | The grad of a graph and classes with bounded expansion[END_REF][START_REF]Linear time low tree-width partitions and algorithmic consequences[END_REF][START_REF]Grad and classes with bounded expansion I. decompositions[END_REF] and are based on the boundedness of graph invariants similar to ∇ / r (G).

We denote [START_REF]Grad and classes with bounded expansion I. decompositions[END_REF][START_REF]From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits[END_REF] by G ▽ r (resp. G ▽ r) the class of the simple graphs which are shallow minors (resp. simple shallow topological minors) of G at depth r, and we denote by

∇ r (G) (resp. ∇ r (G)) the maximum density of a graph in G ▽ r (resp. in G ▽ r), that is: ∇ r (G) = max H∈G ▽ r H |H| ∇ r (G) = max H∈G ▽ r H |H| . (4)
Notice that the main difference between the definition of ∇ / r (G) and the one of ∇ r (G) stands in the way parallel edges are handled.

A class C has bounded expansion if sup G∈C ∇ r (G) is bounded for each value of r. It is obvious that ∇ r (G) ≥ ∇ r (G). However, it has been proved by Dvořák [START_REF] Dvořák | Asymptotical structure of combinatorial objects[END_REF][START_REF]On forbidden subdivision characterizations of graph classes[END_REF] that for each integer r, ∇ r (G) is bounded by a polynomial function of ∇ r (G). Hence a class C has bounded expansion if and only if sup G∈C ∇ r (G) is bounded . Theorem 3. Let f : N → N be an unbounded non-decreasing function with f (x) ≤ x and let g : N → N be defined by

g(p) = max{i, f (i) ≤ p}.
Then for every graph G and every integer r we have:

∇ r (G) ≤ N f (G, 2r + 1) 2r+1 g(2r + 1) 2 .
Proof. Let N = N f (G, 2r + 1) and let c : E(G) → [N ] be a colouring of the edges of G such that each cycle γ gets at least min(f (|γ|), 2r + 2) colours. For a subset I ∈ [N ] 2r+1 of 2r + 1 colours, let G I be the subgraph of G whose edges are coloured by colours in I. Then the maximum length of a cycle of G I is g(2r + 1). According to Lemma 2, blocks of G I have tree-depth at most g(2r+1)-1

2 + 2. Let K ∈ G ▽ r be such that K /|K| = ∇ r (G), let x 1 , . . . , x k be the roots of trees T 1 , . . . , T k of height at most r (corresponding to vertices h 1 , . . . , h k of K) and H ⊆ G[V (T 1 ) ∪ • • • ∪ V (T k )] be such that K ∼ = H/(E(T 1 ) ∪ • • • ∪ E(T k )).
If h i and h j are adjacent in K then there exists in H a path P i,j of length at most 2r + 1 linking x i and x j . Denote by A i,j a subset of 2r + 1 colours such that all the edges of P i,j have their colour in A i,j . For I ∈ [N ] 2r+1 , let H I be subgraph of H containing the edges of the paths P i,j for which A i,j = I. Let K I be the corresponding subgraph of K. As the blocks of H I are included in blocks of G I , they have tree-depth at most

g(2r+1)-1 2
+2. As tree-depth is minor monotone, this bound also applies to the blocks of K I . Observe that a graph of tree depth k has density at most k -1, because if all edges are oriented from higher level end vertex to lower level end vertex, then each vertex has out-degree at most k -1. It follows that

K I /|K| ≤ K I /|K I | ≤ g(2r+1)-1 2 + 1
. By summing up over the possible choices of I we obtain

K /|K| ≤ N 2r + 1 g(2r + 1) -1 2 + 1 ≤ N f (G, 2r + 1) 2r+1 g(2r + 1) 2 .
Corollary 4. Let C be a class of graph and let f : N → N be an unbounded non-decreasing function with f (x) ≤ x.

If sup G∈C N f (G, r) < ∞ for every r ∈ N then C has bounded expansion.

Theorem 5. Let f 0 (x) = ⌈log 2 x⌉ and let r be an integer. There exists a polynomial P r such that for every graph G it holds

N f0 (G, r) ≤ P r ( ∇ 2 r (G)).
Proof. According to [START_REF] Zhu | Colouring graphs with bounded generalized colouring number[END_REF] there exists for each p ∈ N a polynomial Q p such that every graph G has a vertex colouring c :

V (G) → [Q p ( ∇ 2 p-1 (G))
] such that the subgraph induced by any i ≤ p colours has tree-depth at most i. Let p = r + 1 and let P r (X) =

Qr+1(X) 2
. The graph G admits a vertex-colouring c :

V (G) → [Q r+1 ( ∇ 2 r (G))
] such that the subgraph induced by any i ≤ r + 1 colours has tree-depth at most i. Colour each edge {x, y} of G by the set {c(x), c(y)} (hence using P r ( ∇ 2 r (G)) colours). Let γ be a cycle of G with i ≤ r colours. By construction, the vertices of γ use at most i + 1 ≤ r + 1 colours hence td(γ) ≤ i + 1, thus |γ| ≤ 2 i . It follows that every cycle γ of G gets at least min(r + 1, f 0 (|γ|) colours.

Corollary 6. Let C be a class of graphs. Then the following are equivalent:

1. There exists non-decreasing unbounded f :

N → N such that ∀p ∈ N, sup G∈C N f (G, p) < ∞ 2. Let f 0 (x) = ⌈log 2 x⌉. Then ∀p ∈ N, sup G∈C N f0 (G, p) < ∞

the class C has bounded expansion.

Notice that the second condition is tight, according to Lemma 1.

Bounds on Arb p (G)

The lower bound

∇ / p-1 2 (G) 1/p
for Arb p (G) is easy.

Lemma 7. Let G be a graph and let p be a positive integer. Then (Arb p (G)) p is greater than or equal to the maximum arboricity of a multigraph H such that G contains a ≤ (p -1)-subdivision of H, that is, The upper bound is more involved. First, we introduce the admittedly rather technical definition of fraternal completion of oriented multigraphs.

(Arb p (G)) p ≥ max{Arb(H), H ∈ G p-1 2 } ≥ ∇ / p-1 2 (G). ( 5
A digraph G is fraternally oriented if (x, z) ∈ E( G) and (y, z) ∈ E( G) implies (x, y) ∈ E( G) or (y, x) ∈ E( G). This concept was introduced by Skrien [START_REF] Skrien | A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular arc graphs, and nested interval graphs[END_REF] and a characterization of fraternally oriented digraphs having no symmetrical arcs has been obtained by Gavril and Urrutia [START_REF] Gavril | An algorithm for fraternal orientation of graphs[END_REF], who also proved that triangulated graphs and circular arc graphs are all fraternally orientable graphs.

In the context of multigraphs, this notion may be extended as follows:

Definition 1. Let G be a directed multigraph and let a be a positive integer. A fraternal completion of G of depth a is a triple f = ((E 1 , . . . , E a ), w, κ), where

• E 1 = E( G)
is the arc set of G; for each 2 ≤ i ≤ a, E i is the arc set of a multigraph having V ( G) as its vertex set; for every 1 ≤ i < j ≤ a, E i ∩ E j = ∅ (although different arcs of E i and E j may have the same head and tail);

• for e ∈ 1≤i≤a E i , the weight w(e) of e is the integer i ∈ [a] such that e ∈ E i ;

• κ : 1<i≤a E i → 1≤i≤a E i 2 is such that for every e ∈ 1<i≤a E i with κ(e) = (f, g) we have tail(f ) = tail(g) w(e) = w(f ) + w(g)
tail(e) = tail(f ) head(e) = tail(g) head(f ) = head(g);

• conversely, for every i, j ∈ N, f ∈ E i and g ∈ E j such that i + j ≤ a, tail(f ) = tail(g) and head(f ) = head(g) there exists a unique e ∈ E i+j such that κ(e) ∈ {(f, g), (g, f )}.

We also define the arc set E f of the fraternal completion f by E f = 1≤i≤a E i (notice that E f includes no loop) and define a = depth(f) as the depth of f. A fraternal completion

f ′ = ((E ′ 1 , . . . , E ′ a ′ ), w ′ , κ ′ ) of G extends another fraternal completion f = ((E 1 , . . . , E a ), w, κ) of G (or is an extension of f) if • a ′ = depth(f ′ ) > a = depth(f), • for every 1 ≤ i ≤ depth(f) we have E ′ i = E i ,
• the restrictions of κ and κ ′ to E f coincide.

We now state an easy lemma of fraternal completions: Lemma 8. For every oriented multigraph G and every positive integer a,

• G has a unique fraternal completion of depth 1 defined by E 1 = E( G),

• every fraternal completion f of depth a has an extension of depth a + 1.

Proof. The first item is direct from the definition.

For the second item, let f = ((E 1 , . . . , E a ), w, κ) be a fraternal completion of G of depth a. Consider an arbitrary numbering ν of E f . Define

E a+1 = {e f,g : (f, g) ∈ E 2 f , w(f ) + w(g) = a + 1, ν(f ) < ν(g),
tail(f ) = tail(g), and head(f ) = head(g)},

where e f,g is an arc with tail(e f,g ) = tail(f ) and head(e f,g ) = tail(g); define the mapping κ ′ : 1≤i≤a+1 E i → E f by κ ′ (e) = κ(e) if w(e) ≤ a and κ ′ (e f,g ) = (f, g) for e f,g ∈ E a+1 ; also define w ′ : E f ∪ E a+1 by w ′ (e) = i e ∈ E i . Then f ′ = ((E 1 , . . . , E a+1 , w ′ , κ ′ ) is obviously an extension of f of depth a + 1.

Suppose f = ((E 1 , . . . , E a ), w, κ) is a fraternal completion of G of depth a. We associate to each arc e ∈ E f a walk W (e) of G defined as follows:

• If w(e) = 1 then W (e) is the walk e,

• Otherwise, if κ(e) = (f, g) then W (e) is the walk W (f ) followed by the reverse W (g) of the walk W (g), what we denote by

W (e) = W (f ) • W (g).
This way, each arc e of E f is associated a walk W (e) in G of length w(e) which has the same endpoints as e. An arc e ∈ E f is called simple if W (e) is a path. Let G be a directed multigraph, let f = ((E 1 , . . . , E a ), w, κ) be a fraternal completion of G of depth a. Let ≺ be the partial order on E f defined by transitivity from the conditions κ(e) = (f, g) =⇒ f ≺ e and g ≺ e.

Notice that if e ∈ E f and f ∈ E 1 we have e f if and only if f belongs to the walk W (e).

For i = 1, 2, . . . , a, let H i (resp. H ≤i ) be the multigraphs with vertex set V ( G) and arc set E i (resp. j≤i E j ). In particular, G = H 1 . For arcs e 1 , e 2 of G and a fraternal completion f = ((E 1 , . . . , E a ), w, κ) of G of depth a of G, say that a pair (e 1 , e 2 ) ∈ E 2 1 is a conflict if there exists arcs f 1 e 1 and f 2 e 2 and a directed path of length at most a of H ≤a starting with f 1 and ending at one of the endpoints of f 2 (notice that we allow

f 1 = f 2 ). Lemma 9. Assume G is an orientation of G, f is a fraternal completion of G of depth a. Assume that c : E( G) → [N ]
is a colouration of the edges of G such that for every conflict (e 1 , e 2 ) we have c(e 1 ) = c(e 2 ). Then every cycle γ gets at least min(|γ|, a + 1) colours.

Proof. Assume for contradiction that there exist in G a cycle γ = (v 1 , . . . , v |γ| ) which gets less than min(|γ|, a + 1) colours. We say a sequence (e 1 , e 2 , . . . , e q+1 ) of simple arcs in E f is admissible if the W (e i ) are pairwise arc-disjoint and form consecutive subpaths of γ and e 1 , . . . , e q form a directed path of H ≤a .

Choose an admissible sequence (e 1 , e 2 , . . . , e q+1 ) in such a way that i w(e i ) is maximal and then that q is minimum. Without loss of generality, we may assume that for 1 ≤ i ≤ q we have e

i = (v ai , v ai+1 ) with 1 = a 1 < a 2 < • • • < a q+1 ≤ |γ|.
First we show that q+1 i=1 w(e i ) ≥ min(a + 1, |γ|). Assume for contradiction that q+1 i=1 w(e i ) < min(a + 1, |γ|). Then e q+1 has v aq+1 and v aq+2 as endpoints with a q+1 < a q+2 < |γ| (actually we have a q+2 = i w(e i ) -1). Let g be the arc of G linking v aq+2 to the next vertex of γ. According to the maximality of i w(e i ), the sequence (e 1 , . . . , e q+1 , g) is not admissible hence e 1 , . . . , e q+1 is not a directed path, that is: e q+1 = (v aq+2 , v aq+1 ). As w(e q ) + w(e q+1 ) ≤ i w(e i ) ≤ a there exists an arc f in E f such that κ(f ) = (e q , e q+1 ) (see Fig 3). The arc f is clearly simple (W (f ) = W (e q )W (e q+1 ) or W (f ) = W (e q+1 )W (e q )). If κ(f ) = (e q , e q+1 ) then (e 1 , . . . , e q-1 , f, g) is admissible, and

q-1 i=1 w(e i ) + w(f ) + w(g) = q+1 i=1 w(e i ) + w(g) > q+1 i=1 w(e i ),

what contradicts the maximality of

i w(e i ). Otherwise, κ(f ) = (e q+1 , e q ). Then, (e 1 , . . . , e q-1 , f ) is an admissible sequence such that q-1 i=1 w(e i ) + w(f ) = q+1 i=1 w(e i ), what contradicts the minimality of q (for given i w(e i )).

Thus i W (e i ) = q+1 i=1 w(e i ) ≥ min(a + 1, |γ|).
By assumption, the cycle γ which gets less than min(|γ|, a+1) colours hence there exist

f 1 , f 2 ∈ i W (e i ) such that c(f 1 ) = c(f 2 ). Let b 1 , b 2 be such that f 1 ∈ W (e b1
) and f 2 ∈ W (e b2 ). Without loss of generality we assume b 1 ≤ b 2 . As f 1 e b1 , f 2 e b2 and as there exists by construction a (maybe empty) directed path of length at most a of H ≤a starting with e b1 and ending at one of the endpoints of e b2 we deduce that (f 1 , f 2 ) is a conflict, contradicting the hypothesis that c(f 1 ) = c(f 2 ).

To prove that Arb p (G) ≤ P p ( ∇ / p-1 2 (G)) for some polynomial P p , it suffices to find a fraternal completion f of an orientation G of G of depth p so that each edge e of G is in conflicts with at most P p ( ∇ / p-1 2 (G)) other edges. We shall see that this problem can be reduced to finding a fraternal completion with bounded in-degrees. Toward this end, let

C(f) =    j ∆ -( H ij ) : j i j < depth(f)    .
Lemma 10. For every arc e of G we have

{f ∈ E f : f e} ≤ C(f).
Proof. For each f e, there is a sequence of arcs g 1 , g 2 , . . . , g t in f such that g 1 = e, g t = f and g i covers g i-1 in ≺. So it suffices to show that for any g e with w(f ) = i, for any j > i, there are at most ∆ -( H j-i ) arcs g ′ with w(g ′ ) = j such that g ′ covers g in ≺. This is so because the number of such arcs g ′ is at most the number of arcs f ′ such that κ(g ′ ) ∈ {(g, f ′ ), (f ′ , g)} and hence at most the number of arcs f ′ with head(f ′ ) = head(g) in H j-i , which is at most ∆ -( H j-i ).

Lemma 11. For every arc e 2 of G there exist at most 3pC(f Proof. According to Lemma 10 there exists at most C(f) arcs f 2 ∈ p i=1 E i such that f 2 e 2 . Given an arc f 2 of H ≤p there exist at most (∆ -(

)(max(2, ∆ -( H p )) a arcs e 1 of G such that (e 1 , e 2 ) is a conflict. . . . γ e 1 e 2 e q e q+1 v a 1 v a 2 v a q v a q+1 v a q+2 f g
H p )-1)(1+• • •+∆ -( H p ) p-1 ) = ∆ -( H p ) p -1 arcs f 1 such
that there exists in H ≤p a directed path of length at most p starting with f 1 and ending at the head of f 2 . Similarly we have at most 1+• • •+∆ -( H p ) p arcs f 1 such that there exists in H p a directed path of length at most p starting with f 1 and ending at the tail of f 2 . Hence for each f 2 we have at most 3 max(2, ∆ -( H p ) p possibilities for f 1 . As there are |W (f 1 )| ≤ a arcs e 1 such that f 1 e 1 , we conclude. Lemma 12. Let Q 1 (X), . . . , Q p (X) be polynomials, and let P p be the polynomial defined by:

P p (X) = 6p(2 + Q p (X)) p ij <p j Q ij (X) + 1. ( 6
)
Let G be a multigraph with a fraternal completion f of depth p such that

∀1 ≤ i ≤ p, ∆ -( H i ) ≤ Q i ( ∇ / (p-1)/2 (G)). ( 7
)
Then Arb p (G) ≤ P p ( ∇ / p-2 2 (G)). ( 8
)
(Of course, the polynomial P p depends on polynomials Q 1 , . . . , Q p . This dependence will be clear from the context.) 11

Proof. According to Lemma 11 and Lemma 9, G has a colouration of its edges by at most P p ( ∇ / (p-1)/2 (G)) colours such that every cycle γ gets at least min(p+1, |γ|) colours, that is Arb p (G)

≤ P p ( ∇ / p-1 2 (G)).
By Lemma 12, to prove that for some polynomial P p , Arb p (G)

≤ P p ( ∇ / p-1 2 (G)), it
suffices to prove that one can find a fraternal completion f of an orientation G of G of depth p so that ∆ -( H i ) is bounded by some polynomial function

Q i of ∇ / p-1 2 (G).
The construction of such a fraternal completion f is easy: Let H i be the underlying graph of H i . By definition, H 1 = G and for i = 1, 2, . . . , p -1, H i+1 is uniquely determined by H j for j = 1, 2, . . . , i. For i = 1, 2, . . . , p, we orient the edges of H i to obtain H i so that ∆ -( H i ) = ⌈ ∇ / 0 (H i )⌉. This defines a fraternal completion f of an orientation G of G of depth p. In the following, we shall show that for this fraternal completion f, ∆ -( H i ) is bounded by some polynomial function of ∇ / p-1 2 (G).

For i = 1, 2, . . . , p, let T i be the (i -1)-subdivision of the underlying graph

H i of H i . Hence H i ∈ T i ( i-1 2 ). In particular, H 1 = T 1 = G.
For integer m, let G • m be the multigraph with vertex set V (G) × [m] where {(x, i), (y, j)} is an edge of G • m of multiplicity k if and only if {x, y} is an edge of G of multiplicity k. In the following section, we shall prove the following two lemmas.

Lemma 13. Let G be a multigraph, let m be a positive integer and let r be a positive half-integer. Then

∇ / r (G • m) ≤ (2r(m -1) + 1) ∇ / r (G) + m 2 ∇ / 0 (G) + m -1. (9)
Lemma 14. For every integer p ≥ 2, there is a polynomial

N p such that T p is a subgraph of G • N p ( ∇ / p-2 2 (G)).
From these lemmas will then follow the main result of this paper:

Theorem 15. For each integer p there exists a polynomial P p such that for every multigraph G it holds

∇ / p-1 2 (G) 1/p ≤ Arb p (G) ≤ P p ( ∇ / p-1 2 (G)).
In particular, Arb p and ∇ / p-1

2
are two polynomially equivalent multigraph invariants.

Proof. The inequality ∇ / p-1 2 (G) (G)).

Proofs of Lemmas 13 and 14

Proof of Lemma 13. The vertices of K • m are the pairs (v, i), v a vertex of G and 1 ≤ i ≤ m. The every vertex v of G, we say that (v, i) and (v, j) are twins in G • m and we denote by π the projection of G • m into G which maps (v, i) to v.

Let S be a subgraph of G • m which is (≤ 2r)-subdivision of a multigraph H such that

∇ / r (G • m) = H |H| .
Choose S with the minimal number of vertices.

A path of S corresponding to an edge of H is called a branch. The vertices of S corresponding to vertices of H are called principal vertices. The other vertices of S are subdivision vertices.

Let S 0 be the graph obtained from S by deleting all the branches which are not subdivided and let H 0 be the corresponding subgraph of H (S 0 is a (≤ 2r)-subdivision of H 0 and every branch of S 0 is a path of length at least 2). Then we have

H ≤ H 0 + m 2 G[π(V (H))] hence H |H| ≤ H 0 |H| + m 2 G[π(V (H))] |π(V (H))| . Thus ∇ / r (G • m) ≤ H 0 |H 0 | + m 2 ∇ / 0 (G).
First notice that no branch of S(H) contains two twin vertices, except if the branch is a single edge path linking two twin vertices (otherwise we can shorten the branch without changing H and |H|, see Fig 4). We define the multigraph H 1 and its (≤ 2r)-subdivision S 1 by the following procedure: Start with H 1 = H 0 and S 1 = S 0 . Then, for each subdivision vertex v ∈ S 1 having a twin which is a principal vertex of S 1 , delete the branch of S 1 containing v and the corresponding edge of H 1 . In this way, we delete at most (m -1)|H 0 | edges of H 1 . Thus

H1 |H1| ≥ H0
|H0| -(m -1) and S 1 is such that no subdivision vertex is a twin of a principal vertex.

Given H 1 we construct the conflict graph C of H 1 as follows: the vertex set of C is the edge set of H 1 and the edges of C are the pairs of edges {e 1 , e 2 } such that one of the subdivision vertices of the branch corresponding to e 1 is a twin of one of the subdivision vertex of the branch corresponding to e 2 . Note that graph C has maximum degree at most 2r(m -1) hence it is (2r(m -1) + 1)-colourable. Let H 2 be the subgraph of H 1 induced by a monochromatic set of edges of H 1 of size at least |H2| . Let S 2 be the corresponding subgraph of S 1 . If v is a principal vertex of S 2 , then two edges incident to v cannot have their other endpoints equal or twins (because of the colouration). Let S 3 = π(S 2 ) be the projection of S 2 on G. Because of the above colouration, S 3 is a (≤ 2r) subdivision of H 2 . Hence

∇ / r (G) ≥ H 2 |H 2 | ≥ H 1 (2r(m -1) + 1)|H 1 | ≥ H 0 (2r(m -1) + 1)|H 0 | - m -1 2r(m -1) + 1
and the result follows.

Proof of Lemma 14 Let f = ((E 1 , . . . , E p ), w, κ) be a fraternal completion of G of depth p constructed in such a way that for i = 1, 2, . . . , p, ∆ -(

H i ) = ∇ / 0 (H i ). G H ≤9 1 1 1 1 1 2 4 2 2 3 w(h) = 4 w(g) = 3 w(f ) = 7 9 T 2 e1 e2 e3 e4 e5
Figure 5: Example of graphs defined by a fraternal completions. On the left, the graph G. In the middle, arcs of a fraternal completion of depth 9 form the multigraph H ≤9 ; here, κ(f ) = (g, h); the walk W (h) = (e 1 e 2 e 4 e 5 ) associated to h is simple but the walk W (f ) = (e 3 e 4 e 5 e 5 e 4 e 2 e 1 ) associated to f is not. On the right, the 1-subdivision of the arcs in E 2 define the undirected multigraph T 2 .

In the following, we shall prove that for 2 ≤ a ≤ p there is a polynomial N a such that the graph T a can be injectively embedded into a blowing G

• N a ( ∇ / a-2 2 (G)) of G.
Observe that if this is true for a = 2, . . . , i, then by using Lemma 13, we can conclude that there is a polynomial

P i such that ∇ / 0 (H i ) ≤ P i ( ∇ / i-1 2 (G)).
By definition, for a ≥ 1, T a is obtained from the empty graph on V (G) by adding, for each arc e = xy in E a , an induced path of length a connecting x and y. Each arc e = xy in E a corresponds to a walk W (e) in G of length a from x to y. By sending the induced x-y-path of length a in T a to the corresponding walk in G connecting x and y, we obtain a homomorphism, say f , from T a to G. However, f is not an embedding, as many vertices of T a may have the same image. Indeed, V (T a ) is the union of V (G) and a set of |E(T a )|(a -1) added vertices which are the interior vertices of the walks W (e). If for some integer m, each vertex v of G is contained in at most m -1 of the walks W (e) as an interior vertex, then T a embeds into G • m, as we can assign to each vertex in f

(x) = x+1 2 + 1, T 2 embeds into G • N 2 ( ∇ / 0 (G)).
Assume now that the polynomial N i is defined for i = 2, . . . , a -1 and T i embeds into G • N i ( ∇ / i-2 2 (G)). Each arc e = xy ∈ E a corresponds to two arcs g ∈ E i and g ′ ∈ E j with i + j = a, with g = xz and g ′ = yz for some z. A vertex v is an interior vertex of the walk W (e) if and only if either v = z or v is an interior vertex of W (g) or W (g ′ ). By our definition of the fraternal completion, v has in-degree at most ∆ -( H i ) = ⌈ ∇ / 0 (H i )⌉ in H i . By induction hypothesis and the observation above, ∇ / 0 (H i ) ≤ P i ( ∇ / i-1 2 (G)) for some polynomial P i . This implies that for some polynomial Q, each vertex v has in-degree at most d = Q( ∇ / a-2 2 (G)) in H ≤(a) . So for each vertex v of G, there are at most d 2 pairs of arcs g, g ′ for which there is an edge e = xy in E a with k(e) = (g, g ′ ). For an edge e = xy ∈ E a , we say a vertex v is the transfer vertex of W (e) if k(e) = (g, g ′ ), g = (x, v) and g ′ = (y, v). An interior vertex of W (e) is either a transfer vertex of W (e) or an interior vertex of g for some g ∈ E i where i ≤ a -1.

By induction hypothesis, there is a polynomial Z such that a vertex v appears at most Z( ∇ / a-3 2 (G)) times as an interior vertex of a walk W (g) for g ∈ ∪ a-1 i=1 E i . For each g ∈ E i for some i ≤ a -1, there are at most 2d edges e ∈ E a such that k(e) = (g, g ′ ) or k(e) = (g ′ , g). Therefore, each vertex v appears at most

The Dual Version

The problem addressed in this paper can be considered in the more general context of matroids: Problem 2. Let M be a matroid and let p be an integer. What is the minimum number Arb p (M) needed to colour the elements of M in such a way that each circuit γ gets at least min(|γ|, p + 1) colours?

It would be interesting to find a natural class of matroids for which Arb ⋆ p (M) is uniformly bounded. For graphs this leads to the following problem: Problem 3. Let G be a graph and let p be an integer. What is the minimum integer N = Arb ⋆ p (G) such that the edge set of G may be coloured using N -colours in such a way that each cut ω gets at least min(|ω|, p + 1) colours?

It is maybe interesting that the dual version of our problem may present different aspects. The well known theorem of Erdős [START_REF] Erdős | Graph theory and probability[END_REF] which asserts that there exists a graph of order at least n, girth at least g and chromatic number at least 2N + 1. As the chromatic number of a graph is bounded by χ(G) ≤ 2Arb(G) + 1 we get that there exist graphs with arbitrarily large girth and arboricity (hence arbitrarily large Arb p ). The notion

Figure 1 :

 1 Figure 1: The closure of Y ′ contains a cycle γ of length 2 p-1 , and this cycle gets exactly p -1 colours

Figure 2 :

 2 Figure 2: Illustration of the proof of Lemma 2. Cotree edge e i links va i (or one of its symmetric difference of the γ i 's

)

  Proof. Let c be an edge colouring of G with a set J of Arb p (G) colours such that every cycle C of G gets at least min(|C|, p + 1) colours. Assume that G includes a ≤ (p -1)subdivision S of a multigraph H. Colour each edge e of H by the set X of colours used by the edges of the path of length at most p in G corresponding to e in S. The total number of colours used by edges of H is at most the number of ≤ p-subsets of the J, which is less than (Arb p (G)) p . If (Arb p (G)) p < Arb(H), then H has a monochromatic cycle, each edge being coloured by a set X of at most p colours. Then the corresponding cycle C of G uses at most |X| < p + 1 colours and has length at least 2|X|, contradicting the colouring assumption. Thus (Arb p (G)) p ≥ Arb(H).

Figure 3 :

 3 Figure 3: Illustration for the proof of Lemma 9.

Figure 4 :

 4 Figure 4: If a branch contains twin vertices, we shorten it.

H1

  2r(m-1)+1 . So H1 |H1| ≤ (2r(m -1) + 1) H2

  -1 (v) a distinct vertex of {v} × [m] in G • m as its image. Let us consider the case a = 2. By our construction, G has ∆ -( G) = ⌈ ∇ / 0 (G)⌉ Each arc e = xy in E 2 corresponds to a walk of the form (x, v, y), where (x, v) and (y, v) are arcs of G. Let d = ⌈ ∇ / 0 (G)⌉ = ∆ -( G). Then v is an interior vertex of a walk W (e) for e = xy in E 2 if and only if (x, v) and (y, v) are arcs of G. Hence v is contained in at most d 2 walks W (e) as a an interior vertex. Therefore for N 2

d 2 + 2 ( 2 ( 2 ( 2 ( 2 ( 2 (

 2222222 2d × Z( ∇ / a-2 G)) times as an interior vertex of W (e) for e ∈ E a . As d = Q( ∇ / a-2 G)) and ∇ / a-3 G) ≤ ∇ / a-2 G), with N a (x) = Q(x) 2 + 2Q(x)Z(x), each vertex appears at most N a ( ∇ / a-2 G)) -1 timesas an interior vertex of W (e) for some e ∈ E a . Therefore with m = N a ( ∇ / a-2 G)), T a embeds into G • m. This completes the proof of Lemma 14.

⊆ • • • ⊆ G r ⊆ . . . .

Supported by grant 1M0405 of the Czech Ministry of Education 2 Partially supported by the Academia Sinica

dual to "G has girth at least k" (i.e. every cycle of G has length at least k) is "G is k-edge connected" (i.e. every edge cut of G has size at least k). However, there does not exist graphs with arbitrarily edge-connectivity and Arb ⋆ p . Precisely:

Proposition 16. Let G be a graph and let p be an integer.

, and there exists infinitely many (2p + 1)-edge connected graphs such that Arb ⋆ p (G) ≥ p + 2;

Proof. The first item is a consequence of [START_REF] Kundu | Bounds on the number of disjoint spanning trees[END_REF] where it is proved that a 2n-edge connected graph has at least n pairwise edge-disjoint spanning trees.

The upper bound of the second item is similarly obtained by doubling each edge of G (thus obtaining a (4p+2)-edge connected multigraph) and considering 2p+1 edge-disjoint spanning trees of this new multigraph G ′ , and colouring each edge e of G by the set of (at most two) colours assigned to the two edges of G ′ corresponding to e. The lower bound is obtained by considering non-complete (2p + 1)-regular (2p + 1)-edge connected graphs G: if Arb p (G) = p + 1 would hold then each colour class would include a spanning tree and hence G ≥ (p + 1)(|G| -1) would hold.

The last item follows from the following construction. For integers L, p let C (p)

L be the multigraph obtained from a cycle of length L by replacing each edge by p parallel edges (see Fig. 6). The graph C (p) L is (2p)-edge connected. However, Arb p (C (p) L ) ≥ L 1/p as if each cut gets at least p + 1 colours then no two group of parallel edges can be coloured by the same set of colours.