Fanny Coulomb
email: fanny.coulomb@upmf-grenoble.fr

Jacques Fontanel
email: jacques.fontanel@upmf-grenoble.fr

F. Coulomb & J. Fontanel -The economic side of French military expenditures

de défense et l'industrie française d'armement', in Debezies

The observation of French military expenditures since the 1990s may give rise to several questions. While the French policy remains characterized, according to the words of the President Jacques Chirac 3 , by the " will to assume (our) responsibilities on the international scene where (our) country is both awaited and respected", numerous criticisms are expressed against the insufficient means of the French defence or the increasing military "technological gap" between Europe and United States. An economic study of the evolution and structure of French military expenditures may contribute to explain this paradox; this will be the main subject of our paper.

There has been many changes in France's defence policy since 1945. Beside official speeches, the French "policy of grandeur" is no more relevant today. The history of French military expenditures is linked to the one of domestic arms production. The defence policy had been since long characterized by a search for "grandeur" 4 , with a great development of national arms industries during the Napoleon era, until the end of World War II. Afterwards, the Fifth Republic has increased the importance given to arms production and de Gaulle has opened the way to a new policy based on national independence thanks to nuclear weapons and the new concept of "proportional deterrence", and with the refusal of arms imports. Since 1966 and France's withdrawal from the integrated military command of NATO, the French defence has been specific, giving priority to the strategic autonomy and the territory inviolability, while other European countries had chosen the dependence with regard to United States. The control of the nuclear weapon after 1960 based a strategy of deterrence essentially oriented towards the East European socialist countries, while the conventional forces were prepared for a possible major confrontation. The arms production therefore became central in the industrial and technological development. The French arms industry was then highly competitive on international markets, in spite of some unefficiencies in the functioning of the "military-industrial complex", made of close relations between the engineers of the "Délégation Générale de l'Armement", the firms managers, and military staff. Arms exports were vital for the sector, as the size of production was not sufficient to realize economies of scale. They have been promoted even sometimes without any established economic or commercial logic. 5 The new strategic context of the post-Cold war and the disappearance of the risk of direct military conflicts have led France to redefine its defence policy. The "White Book on Defence" of 1994 thus presented the necessity of adapting the military strategy to the new risks linked to the development of regional conflicts, of nuclear proliferation, and of chemical and bacteriological weapons. The scenarios of foreign interventions in the framework of "bilateral agreements of defence" or of "operations in favour of peace and international law" were also mentioned. In this context, conventional weapons seemed essential, and there was an inversion of the immediate priorities between nuclear and conventional weapons 6 . The new strategy of action focused on the management of zones of crisis and on the European and international cooperation. Indeed, the French leaders had clearly advocated for an increased European cooperation and for the construction of an European defence. In this context, France has always reasserted its military and strategic ambitions, as shown for example by the recent discourse of the chief of staff General Bentégeat 7 . Having insisted on the active role of France in the implementation of an Europe of defence, role which did not aspire to the leadership (what, according to her, "would be opposite to the philosophy of the European construction") but rather to a "co-piloting", the text outlines the bases of the French defence. However, "Since 1996, France has made the choice, which is inviolable and fundamental, to be a complete military power, by retaining a capacity of nuclear deterrence, by developing a capacity of intervention in all fields, as well as a capacity of command of a multinational operation." 8 But beyond the declared objectives, one may think that the end of the cold war and the crisis of arms markets have led to the end of an independent military strategy. The defence budgets have indeed been dramatically reduced, in France like in other western countries, and the importance of military expenditures in the GNP has drastically decreased, as shown in table 1. The defence spending per capita in France decreased from 546 to 453 euro (constant 2003) from 1992 till 2003 and the defence budget of Initial Finance Law decreased by 4,46 % in volume between 1992 and 2002. The reduction of the French defence budget is even more marked at the level of the budgetary execution 10 . At the same time as this reduction of military expenditures during decade 1990, the share of the defence sector in the domestic economy is declining. The part of the defence industry sales in the GDP did not stop decreasing since the mid-1980s, from 2,4 % to 0,8 % between 1987 and 2000. Also, the arms exports represent no more than 0,21 % of the GDP in 2001, as against 0,58 % in 1990 11 . During the 1990's, the activity of defence underwent profound changes in France, with the opening to competition of arsenals, the privatizations of the arms firms and the rise in the number of partnerships between public sector and private sector.

In this context, does France still have the means of its ambitions? According to François Géré 12 , the current French foreign policy is limited by the lack of military means; so in 2001, the decision not to send the aircraft carrier Charles de Gaulle to Afghanistan would have ensued from the technical impossibility to do so. But the political leaders as well as the military are reluctant to publicly recognize these inadequacies (mainly on equipments), notably resulting from bad strategic choices (like the continuation of the program of heavy tank Leclerc after 1991 for example). On the contrary, France multiplies the foreign operations, in Bosnia, Kosovo, Macedonia or Africa. Although France's foreign policy remains characterized by the ambition to remain the leader country on European defence, the analysis of defence budgets reveals that the means have not always followed the declared objectives. One may then wonder about the determinants of French military expenditures. What is the place of economic determinants? Does France keep developing a coherent and distinctive defence policy? The analysis of statistical data on French military expenditures since 1990 turns out to be full of information on the determinants of military expenditures. Two arguments will be developed:

-While until the 1990s, French military expenditures have been considered as a national economic development force, now they more represent an economic shadow burden. -The independent policy of security has been clearly replaced by a real dependency on armaments and strategies.

I -French military expenditures, from an economic development force to an economic "shadow" burden

Though in the past France has derived much advantages from the development of the military sector, now the situation is reversed. The changes in defence expenditures show some inertia effects and the difficulties to make the defence policy evolve. Military expenditures now seem to be more an economic burden than a driving force. The study of the defence budget compared with the general State budget shows that military expenditures are often used as variables of economic adjustment.

I.1. The importance of inertia effects

The influence on French military expenditures of external factors is difficult to estimate, in the lack of any avowed State enemy. The security function would be almost impossible to define in a model of military expenditures. Indeed, because of the variety of the instruments of foreign policy (diplomatic operations, interventions in regional conflicts, economic and military assistance, membership in an alliance), the taking into account of the action-reaction process in military expenditures is insufficient. As France's status in the NATO is particular, its strategy varies according to interests which are more European than Atlantic, more French than European. In this context, France strategies evolve according to the available instruments (diplomatic, military, political, notably). The French government uses all its trump cards in a very pragmatic way, exploiting alternately its membership in the Atlantic Pact and in the European Union while reminding its membership in the United Nations Security Council and its own nuclear force.

1) A belated reduction compared with other NATO countries

The French military expenditures have not been immediately affected by the end of the Cold War and the new geopolitical context. It is later that France begins a reduction of its defence budget, with regard to other NATO countries. It may be explained by the relative lateness of the defence policy reform and also by a political will to preserve the national independence on defence, and though to maintain a high level of military expenditures, in spite of the geopolitical changes.

So, between 1990 and 1994, the French military expenditures decreased only 0,7 % a year on average, whereas this number was 6,3 % for Germany, 4,2 % for United Kingdom and 5,3 % for United States, according to NATO data 13 . Also, between1995 and1999, the decline was of 1,2 % on annual average in France, against 1,7 % in United Kingdom and 2,6 % in United States.

The study of NATO statistics shows that French military expenditures did not follow a trend similar to NATO's ones (cf. From NATO data 14 . United States have much more fluctuating defence spending, with peaks attributable to their geostrategic situation. European countries know much more regular changes, what shows that the political and strategic determinants of their defence budgets of defence are not similar. The idea of the "leadership" and the execution of the threat explain the erratic progress of the American military 14 NATO (2004), op.cit. 15 NATO (2004), op.cit. expenditures, while Europe, in spite of the "Yugoslavian" affair which revealed large dissensions, has always felt rather in safety, without particular military ambition.

Nevertheless, the differences are high between France and the other NATO European countries. So, if these ones have reduced their defence expenditures of 15,8 % defence between 1990 and 1995, France reduces them only of 7,4 %. The differences between the NATO European countries' choices on defence may partially explain this 16 . So, the conscription was suppressed as soon as 1991 in Germany, and only in 1996 in France. Germany has chosen an army with a reduced size since the disappearance of the Soviet threat, what allowed it to considerably decrease its military expenditures (Table 3). The French choice of the professional army ensued from the reduction of the risk of invasion and from the necessity of adapting the forces to foreign missions within the framework of international organizations, notably of the NATO, UNO or EPSD. It has induced a lesser reduction of the military expenditures than in other countries. It is to note that the United Kingdom or the United States, which had experienced since long professional soldiers, have known an equivalent decline of their military expenditures between 1992 and 2001 (Table 3). The graph 2 puts in evidence a constant increase of the share of French military expenditures with regard to those the other NATO countries over the period 1992-1997. This trend is the consequence a decrease of defence spending more belated in France than in the other NATO countries, as well as its lesser intensity at the general level. Even if the share of France begins a decline from 1997, it remains in 2003 higher than in 1984, what shows that the decrease of military expenditures was less important in France than in the other alliance's members. In this country, the political leaders have delayed doing the necessary reforms after the end of the Cold War, because of their will to preserve an independent defence policy. 1 9 8 4 1 9 8 6 1 9 8 8 1 9 9 0 1 9 9 2 1 9 9 4 1 9 9 6 1 9 9 8 2 0 0 0 2 0 0 2 % World military expenditures, in particular those of most NATO countries, began an increase from 2000. The reduction of defence budgets during the 1990s was not due to a deep demilitarization of the concerned countries but rather to an alternation of upward and downward cycles, which punctuate the world military expenditures since the 1950s. After 1991, it seemed necessary to establish new strategies, in a more and more competitive economic environment, notably ruled by the World Trade Organization. Countries stayed on the alert, while making a "break" after the cold war 18 .

2) Defence budget and bureaucratic effects

The ratio of military expenditures to total public spending, concerning the voted amounts in the Initial Law of Finance, is quite stable (between 17 and 19 %) from 1972 till 1993, then it regularly decreases from 1994 till 2002, followed by a light increase in 2003 and 2004 (cf. Table 4). These figures show the weak variation of the share of military in global public spending and the importance of internal factors in the determination of the defence budget. The weight of defence industries and of the military sector in the national employment and in the GDP, but also the constraints inherent to the maintenance and renewal of armed forces, leave not enough scope for reducing military expenditures. On the other hand, even during the episodes of increased international tensions, for example at the beginning of the 1980s with the freeze of US-USSR relations, military expenditures have never exceeded 19 % of State total expenditures, showing their weak upward elasticity. As well as the hypothesis of an influence of the external factors on the level of defence spending is debatable, is the one of an influence of internal political factors 20 . The political changes seem to influence only very weakly the level of military expenditures, the great trends of which are drawn by the long-term programs, apart from the electoral cycles. Since the acceptance by two main French political parties of the principle of nuclear deterrence, then of the abolition of conscription, military expenditures do not represent a subject of debate anymore. Finally, one may speak of a relative consensus afterwards. As the United States strengthen their military defence, the French citizen does not worry much about his foreign security, as if the nuclear power, the membership in a pacified Europe and the more than two-hundred years old "friendship" with the United States (in spite of quarrels which can be only temporary, considering the common interests) has ensured a kind of invulnerability towards current threats. This attitude is specific of France, which always intends to be a major political and economic power, by offering in guarantee only its "cultural influence", though declining, and its active role in the European construction.

I.2. French defence budget: a variable of economic adjustment

As regards the economic variables, French military expenditures rather depend on internal considerations. With the reappraisal of the DGA, the power of the engineers of armament has been gradually reduced. In this context, military expenditures could become "a variable of adjustment". In situation of economic tension, they would be the first ones concerned by a reduction of financial allocations.

1) The gap between the Initial Law of Finance and the budgetary execution for military expenditures

The Graph 3 below show the difference between the defence budget adopted every year by the Parliament with the Initial Law of Finance and the credits effectively released for the military sector each year, recorded by the Rectified Law of Finance. The executed military expenditures appear to be systematically lower than those who had been planed (graph 3), unlike what happens at the level of the general budget (graph 4). While the executed total public expenditures are systematically and widely superior to those who had been adopted in the Initial Law of Finance, the military sector never succeeds in obtaining the totality of the voted credits. It is obviously explained by the use of military credits as variables of budgetary adjustment. But this also raises the issue of the democratic control of public spending, the successive governments making adopt cancellations of military credits to limit the increase of the public deficit, so modifying the orientations voted by the Parliament.

Graph 3 :

19 Lelièvre, V. (1996), 'Dépenses militaires et contraintes économiques (1971-1995)

2) Military expenditures faced with budget cuts

In a study of 1996, V. Lelièvre 21 showed that economic constraints strongly affected the level of French military expenditures. From a model comparing the difference between the growth rates of forecasted State receipts and expenses with the growth rate of the GDP, the author tried to put in evidence the neutral, restrictive or expansionist nature of the budgetary impulse. Her study on the period 1970-1994 showed that in France between 1971 and 1995, the defence budget had never been used to reflate the economic activity and that, on the contrary, the defence was one of the first items to bear the brunt of budgetary restriction. As for the budgetary neutrality, it has generally been obtained at the price of a slowing down of military credits, in favour of civil public spending. g: growth rate of the public spending -t: growth rate of public revenue it: economic growth rate If ( g-t ) > it, the budget is expansionist (E); If ( g-t ) < it, the budget is restrictive (R); If 0 < (g-t) < it, the budget is neutral (N).

Two budgetary impulses may then be calculated:

-The wished budgetary impulse (from the voted budgets); -The real budgetary impulse (from the executed budgets).

In the table 5, we have continued the comparison of the voted and executed expenditures depending on the nature of the budgetary impulse for the period 1995-2003 22 . In our model, (g-t) is given by the variation rate of the State general budget, B. The economic growth rate is the variation rate of the Gross Domestic Product, G.

We use the following variables:

-MEv: variation rate of the voted defence budget (except pensions), Initial Law of Finance (ILF) (%); -MEe: variation rate of executed military expenditures (ordinary and capital expenditures, except pensions), (%); -PSv: variaton rate of voted total public spending, ILF (%); -PSe: variation of the voted total public spending (%); -Bv: variation rate of the balance of the voted State general budget, ILF(%); -Be: variation rate of the balance of the executed State general budget (%); -G: variation rate of the Gross domestic product (economic growth) (%); -Iv: nature of the budgetary impulse for the voted budget, with : -E: expansionist, -R: restrictive, -N: neutral; -Ie: nature of the budgetary impulse for the executed budget. The study of the period 1993-2004 shows a continuity in the use of military expenditures as variables of budgetary adjustment and in their non-use as an instrument of economic stimulation. So, five years are characterized by an expansionist budgetary impulse, at the level of the Initial Law of Finance: 1993, 1994, 2002, 2003 and 2004. In 1993, 2003 and 2004, the increase in voted military expenditures is superior to the one in total public spending. However in the budgetary execution, the increase in defence spending remains widely lower than that of total public spending. For example, in 2003, while the rise in the passed defence budget was of 5,57 %, it has been transformed into a decline of 4,29 % in the executed expenditures, showing that the military expenditures serve as variables of budgetary adjustment.

The year 1995 has been marked by budgetary neutrality, which seems to be obtained thanks to a budgetary effort to the detriment of defence. The decline of voted military expenditures is of 1,42 % while total public spending increase is of 1,79 %. At the level of the executed expenditures, the decline of military was of 7,90 %.

From 1996 till 2001, the general budget adopted by the Parliament has been restrictive. Military expenditures have been particularly affected by budgetary cuts, their decline has been superior to that of all the other public outlays (except in 1997, probably because of the specific political context, with the dissolution of the National Assembly), either they were in decline while the other public spending were increasing. Only 1999 shows an increase of 2,28 % of the defence budget, lower than the increase of the general budget (4,19 %), however. In 1997, the decline of the voted military expenditures was worse at the level of the budgetary execution and in 1999, the foreseen rise was transformed into a decline. However at the level of the budgetary execution, the rates show a tendency to reduce the cuts in defence budgets, in 1996, 1998, 2000 and 2001: the reduction of military expenditures was less important than forecasted, and has sometimes been transformed into slight increases. It is therefore very important to differentiate the voted budget and the executed budget. The increases in military expenditures planed through the military programming of 2003-2008 will so not necessarily become a reality. The fact remains that in 2000, 2002 and 2004, the executed military expenditures were superior to the voted ones, what only rarely happened since the beginning of the 1970s, showing the current will of political authorities to increase the defence effort. This study shows however that in spite of official speeches on the necessity to maintain and increase the French defence potential, invoking strategic and political reasons, the defence budget remains highly subject to economic restrictions and that the discourses are not always followed by the facts.

However, the reminiscences of "Gaullism" and the will of some "left-wing" persons to refuse the model of the pacifists limit the reduction of defence budget. It is as if reducing military expenditures remained synonymic with giving up the national independence, in spite of the European perspectives that gradually limit the importance of this approach. Moreover, the importance of the defence sector in the national economy (notably employment) limits the potential of disarmament.

To summarize our comments, it may be said that today, military expenditures depend on several qualitative factors, such as the European integration, the meaning of the nuclear weapon in the world and in France, the weight of customs and of inertia effects, the political speeches in process of change, but also of the domestic economic growth, the military expenditures of the previous period and the importance granted to jobs in arms firms. But the French defence policy is no more independent and it suffers from many problems.

II-From an independent policy of security to a policy of real dependency

For a country like France which produces armaments, the internal economic factors therefore seem a priori more determining than the external ones to explain the level of the defence spending. France, which is an average power, has given up its idea of a "policy of grandeur" 23 . Today, it has to limit its will of independence and take into account budgetary constraints (for example the respect for the criteria of Maastricht) and economic difficulties. If De Gaulle has once asserted that "the backup would follow", the facts have belied him since long.

II.1. The "potemkinism" 24 of French defence policy

Before the 1990's, the French policy of military independence was notably based on a strong military research and development (R&D). Many critics have been developed against the too sophisticated technologies obtained in the defence sphere, without any spin-offs in the civil industry, against the capital-intensiveness, without regard to production costs and the excessive secretiveness. But today the economic analysis of the role of military R&D on the global industrial development has changed. A debatable issue is on the will of French political leaders to lead a real policy of economic power notably based on the military sector, as it has been the case till the 1980's.

1) The weakness of French military research and development (R&D): from views to reality

In Europe as in the United States, the armament companies now realize an important part of their sales in the civil sector, what allows them to limit the risks associated to budget cuts in defence. We may think that this new situation facilitates transfers between the military and civil sectors, at the level of human and physical resources, technologies or products. Precisely, the issue of the impact of the military research and development (R&D) on the growth of the industrial productivity remains polemical. Indeed, the technologies originally developed for defence, as computers and satellite communications, seem to have played an important role in the American growth during the 1990s and to have given them the control of numerous high technologies 25 . However, only few econometric studies developed these last years have put in evidence a link between the growth of the American industrial productivity and the development of these new technologies. For example, the analysis of D. Saal 26 shows that sophisticated econometric methods may succeed in showing the positive effect of R&D federal expenditures on the global industrial productivity, since the 1970s. The issue of the impact of the military R&D on the economic growth has always been very controversial 27 . If it is true that in the short run the patents stemming from the military R&D seem few, most of the modern technologies have nevertheless been at first developed in the military sector. Also, the increasing use of intelligences for economic purposes may have an impact on the level of military expenditures, especially in the United States where the structures of economic intelligence are particularly developed.

Beyond the statistical debate, this represents an essential stake for the understanding of national economic dynamics, in particular for industrial nations, which devote an important part of their public R&D to the military sector. France spent in 2003 and 2004 about 2 billions euros on military R&D, what is less than United Kingdom, with 3 billions. This year marks a new increase of these outlays in France, after an almost continuous decline since 1996, when they had reached a peak at 4,19 billion euros that is more than 30 % of the national spending of R&D. But this ratio is much lower than the American one: in 2002, 54,4 % of the national R&D spending was concentrated on the 23 Fontanel, J., Hébert, J.P. (1997) 'The French policy of "Grandeur"', Defence and Peace Economics, Vol. 8, pp. 37-55. 24 The "potemkinism" is to hide from the sovereign or the citizen, what goes not well, to show only the forces. 25 Alesina, A., Giavazzi, F. ( 2004), 'Inégalité de l'Europe en matière d'investissement de défense', Project Syndicate, http://www.projectsyndicate.org/article_print_text?mid=842&lang=4. 26 military R&D in United States, and only 24,2 % in France [START_REF] Perrier | Que pèse le militaire dans la recherche française ?[END_REF] . The use of military expenditures for "industrial policy" purposes may be considered as one explanatory factor of their level in United States.

2) A difficult industrial adaptation to the new security and economic environment

The French arms production has been until the mid-1990s characterized by an "administrated regulation", with the supervision of the D.G.A. (General Delegation of Armament). The role of this organization is minimized in the "White Book" of 1994, while it had been until then placed in the heart of the industrial policy of armament [START_REF] Hébert | La réforme de la politique de défense et l'industrie française d'armement[END_REF] . The text recommends new relations between the State and the arms firms, with a decrease of the supervision and of the "mentality of arsenal". The organization of armament production in France has actually undergone profound changes, the DGA not being the interface between military staffs and industries anymore. The markets have been opened to competition, so as to limit the drift of programs costs. The operations of restructuring and integration, notably through mergers with other European firms, have reinforced this trend. According to J.P. Hébert, this reform marked "the end of the French administered regulation and the beginning of the economic calculation ». In spite of these changes, the French and European arms industry has been penalized after 1990 by too narrow markets structured on a national basis. Moreover, it has suffered from the industrial dependency on public orders, in the context of European public funds restrictions. And yet the costs of research, development and production of military materials were rising. Data show a decrease in French arms exports since the 1990s, as well as a reduction of the turnover and of the employments of the arms industry (graphs 4, 5 & 6).

Graph 5

Turnover of the arms industry (Billion current Euros) In this context of decreasing means and efficiency, France has tried to set up an European system of defence, allowing to compensate for the shortcomings of national systems, notably for heavy materials, like transport planes or ships, or aircraft carriers (France proposed at the end of 1998 the creation of an European air and sea group gathering all national aircraft carriers), and for "transmission and intelligence" (France had a leading role in the programs Hélios 1 and Hélios 2). However, European cooperation have remained limited, because of the reluctance of some allied governments attached to the transatlantic link and of their preference for cooperation on American programs, as shown by the Joint Strike Fighter project. The ambition of France with regard to the European defence policy has therefore not immediately led to concrete realizations, the other "natural" allies not being ready for the implementation of a common defence outside NATO. The setting up of an independent European defence within NATO (EUO) also seems delicate, as shown by the non-intervention of the EUO in 1991 in former Yugoslavia.

Unlike in Germany or United Kingdom, the French state has much delayed his withdrawal from the main companies in aerospace and defence electronic (like in Italy and Spain), though it seemed necessary after 1991 to open up the national arms markets and to create a defence industry at the European scale, so as to remain technologically competitive in front of the United States. The first wave of privatization and integration has led to three main European groups: BAE systems, Thales, EADS. However, many overcapacities remain in the land and naval sectors, to the benefit of American industries. The size of European companies remain insufficient in front of US ones, and their product range are not large enough to be competitive on many market segments. Moreover, the benefits should be limited, in the lack of a real integrated European industrial and budgetary policy. The reticence of the main European states about the opening to international competition of public invitations to tender should limit the reforms. European states, and notably France, remain concerned about the maintaining of the domestic industrial basis, and therefore of a national source of supply. The creation of European integrated companies progressively modifies this, as they have a larger access to the national markets of their components. However, today, the United Kingdom is the single country to organize an international competition for its national programs of equipment, with some restrictions.

Beyond the industrial base issue, one may think more generally that France model of economic power remains weak. It is notably shown by the inadequacy of the French policy on "economic intelligence", a field were industrial and public interests are closely linked. Admittedly, the existence of a system of communication interception, ironically nicknamed the "Frenchelon" by US officials, may explain the weak criticism of the American system by French political leaders. But beyond, French resources of economic intelligence seems much limited. A new report34 published on this issue in 1994 and 2003 have warned against the lack of a national system of economic structures of economic intelligence and, more largely, of economic security. It is much significant that the concept of economic security remains defined by the "Ordonnance" of 1959, which limits its use to issues of economic or industrial espionage from enemy countries. Many affairs have alerted the leaders on the risks for long-term economic growth of an insufficient protection of key-enterprises.

Though, the control taken by American assets of the French firm Gemplus, inventor of the chip card, has led to a change in the French legislation. But a policy of economic intelligence may not be limited to defensive systems, it must also allow the economic offensive. Today, the advances of France in this field remain few, in comparison with other countries, such as the United States, Japan or Germany 35 . Many links between the military sector and the civil sector remain unexploited at this level.

II.2. France's defence model in difficulty: the meaning of the military expenditures' structure

The current changes in military sector show that France does not lead a clear and ambition defence policy anymore. Beyond the promises, data reveal a transformation of the structure of military expenditures, significant of the country's difficulties to redefine the role of military sector in a context of increased competition. The nuclear issue is revealing of the difficulties of the French defence model.

1) A declining share of capital expenditures in the defence budget

The White Book on the National defence, published in 1994, shows an intention of continuity in the defence policy, insisting on the strengthening of conventional armaments and nuclear deterrence. The implementation of the European Policy of Security and Defence seems to justify the preservation of the defence budget at previous levels 36 . But in reality a cut in the initial military budgets adopted by the Parliament has been operated, through a cut in the credits of equipment (cf. table 8). Actually, equipment expenditures are very elastic in global military expenditures. When there is an effort to reduce the military budget, functioning expenditures undergo strong inertia effects which lead the government to suppress or delay the renovation of arms heavy materials. These changes in the structure of military expenditures may notably be explained by the transition to a professional army from 1996 37 . The delay of the professionalization with regard to other countries as the United Kingdom moreover partially explains the delay in military expenditures reduction. So, with more than 60 % of its military expenditures devoted to personnel expenditures, France suffers a gap with regard to the Anglo-Saxon countries having chosen much earlier the professional army, their rate of personnel expenditures being lower than 40 % (cf. Tables 9 and10). The efficiency of military expenditures depends on the distribution among the various budget items. So, the European countries having military expenditures 60% of which are of personnel, what is the case of France, have "less effective" expenditures than those of the Anglo-Saxon countries, the rate of which is much lower. Besides, the European industries of defence can be considered as remaining too much divided to effectively compete with the American ones. On the evolution of the defence policy at the European level will also depend the future of the military production in France and thus, more widely, of the military sector and expenditures, the economic aspect being a factor of these expenditures.

2) A decreasing investment in the nuclear field

Giving up its strategy of non-participation in nuclear disarmament agreements, in 1996 the government has decided the end of ground to ground systems as well as of nuclear tests (after an ultimate simulation in Mururoa), but also plants closure and the reduction of submarine capacities. However, the nuclear deterrence however remains central in the French defence strategy, as reasserted by Jacques Chirac in 2004: "The nuclear deterrence is at the heart of the means which allow France to assert the principle of strategic autonomy, from which our defence policy ensues. It is today, thanks to the efforts granted in a continuous way since the General de Gaulle, an essential foundation of our security and it will remain so, in my opinion, still during long years in the new strategic context where it keeps all its sense and all its efficiency. The nuclear deterrence is at first an important factor of the international stability (...)" 41 The nuclear deterrence is presented as an essential answer to the threats 38 Ministère de la Défense (2002, 2003), op.cit., chapter V. 39 NATO (2004), Defence expenditures of NATO countries, www.nato.int/docu/pr/2003/p03-146e.htm 40 op.cit. 41 Speech of Jacques Chirac, president of the Republic in front of the IHEDN (Institute of High Studies on National Defence), June 8 th , 2001. "La dissuasion nucléaire est au Coeur des moyens qui permettent à la France d'affirmer le principe d'autonomie stratégique, dont découle notre politique de défense. Elle est aujourd'hui, grâce aux efforts consentis de manière continue depuis le général de Gaulle, un fondement essentiel de notre sécurit é et elle le restera, à mon sens, pendant de longues années encore dans le nouveau contexte stratégique où elle garde represented by some regional powers, in the context of the development of weapons of mass destruction (ballistic proliferation, new nuclear, biologic or chemical weapons, etc. However, the credits opened for nuclear deterrence have been much reduced since 1990 and reached their lowest level in 2001. In constant 2003 euros, the funds of payment for nuclear amounted 5,94 billion euros in 1990 and 2,96 in 2003, what means they have been divided in real terms by a factor twofold. The decrease of the importance of nuclear deterrence in Titre V (equipment and infrastructure expenditures), 21,7% in 2003, should continue at least until 2008 (when it should represent 17%). According to the Ministry of Defence, French nuclear forces are now designed to be "strictly sufficient".

Conclusion

It appears that the situation of the military sector has much evolved since the mid-1980s. The French model of a protected arms production and exports has given place to a competitive environment, with higher budgetary constraints in the context of the European Union. In 2005, France is far from its past "policy of grandeur". Now, the national military strategies remain vague, still impeded by inertia effects, bureaucracy and electoral aims. Our study has shown that French military expenditures are mostly dependent on internal factor, and notably on economic considerations, what is explained by two facts:

-The reform of the French defence policy has taken a long time. Indeed, it became effective only in 1996, what accounts for the belated reaction to the end of the Cold War of French military expenditures, with regard to other NATO countries. -Besides, our study on the period 1995-2003 shows that military expenditures are often subject to budgetary restrictions, more than other public spending, what contrast with the official speeches reasserting the importance of defence in French foreign policy. The defence sector has therefore become more an economic burden than a driving force. The structure of military expenditures indicates the weaknesses of the French defence model, with the reduction of the share of equipment expenditures, as well as of the one of the nuclear budget. The insufficiencies concerning military R&D and economic intelligence in comparison with other NATO countries must also be evoked. Moreover, the restructuring of the arms industry has been more delayed in France than in United States or United Kingdom. The policy of security is not independent anymore; it is now characterized by a real dependency on armaments and strategies. It may then be considered that French military expenditures have no other logic than that of "potemkinism" (notably on the nuclear issue), with a short-term perspective and of the electioneering. The long-term perspectives are little evoked in spite of the military programming, so little respected. It is not sure that such an attitude is a correct basis for France's military policy.

  , V. (1996), 'Dépenses militaires et contraintes économiques (1971-1995)', Revue Française d'Economie, printemps, 65-86.

  Saal, D. (2001), 'The impact of procurement-driven technological change on U.S. manufacturing productivity growth', Defence and Peace Economics,12(6), pp. 537-568. 27 Fontanel, J. (1997), 'Eléments de réflexion sur la conversion des technologies militaires, Structures industrielles et mondialisation', Innovations, 5,1. Fontanel, J. et Karlik, A. (2005), 'L'industrie d'armement de la Russie. Effondrement ou renouveau ?', Innovation, 20, 81-108.

  Source for graphs 5, 6 and 7. From data of the Ministry of Defence, Annuaire Statistique de la Défense, Editions 2002 & 2003. The armament industry (BA95) includes three industries: shipbuilding; aircraft and space manufacturing; weapons and ammunitions manufacturing. It therefore include both civil and military activities 33 .

  tout son sens et toute son efficacité. La dissuasion nucléaire est d'abord un facteur important de la stabilité internationale. (…)" www.ladocfrancaise.gouv.fr/dossier_international/nucleaire/debats/dissuasion.shtml

Tableau 1 : Share of defence expenditures in GNP (constant currency), (%)

	%	France	U.K.	Germany	Italy	United States
	Average 1990-94 3.4	3.9	2.1	2.1	4.7
	2003	2.6	2.4	1.4	1.5	3.45

Source : Ministère de la Défense, and NATO data

9

1 : Annual variation rate of France and NATO military expenditures (%)

  Table 2 and Graph 1).

	-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 Graph -9 %	1985	1986	1987	1988	1989	1990	1991	1992	1993	1994	1995	1996	1997 Annual variation rate of NATO military 1998 1999 2000 2001 expenditures (except France) Annual variation rate of France military expenditures (NATO structure)	2002	2003

Table 2 : Defence spending, France, United States, NATO And their variation from the previous period (constant 1995 currency) 1975 1980 1985 1990 1995 1999 2000 2001 2002 2003

 2

	France	Euros	27860 33670	37361	39265	36346	35010	34856	34701	35448	36137
		(Million)		+20,8%	+10,9%	+5,10%	-7,4%	-3,7%	-0,4%	-0,4%	+2,2%	+1,9%
	NATO-	Dollars US	--	198329 216088	218980	184352	188797	190653	189812	191620
	Europe	(Million)			+8.9%	+1.3%	-16.0%	+2.4%	+1,0%	-0.4%	+0.9%	-0.3%
	United	US Dollars	247628 260487	349729	354956	278856	257824	269617	271491	306302
	States	(Million)		+10.5%	+34.2%	+1.5%	-21.4%	-7.5%	+4.6%	+0.7%	+13.0%	+5.6%
	NATO -	US Dollars	--	466393 575825	584681	472284	455270	468564	470095	506737
	Total	(Million)			+23,5%	+1.5%	-19.2%	-3.6%	+2.9%	+0.3%	+7.8%	+3.3%
	Source : From NATO data 15

Table 3 : Defence spending (billions of constant 2001 euros)

 3

		France	Germany	United-Kingdom United States
	1992	30	32.3	41.4	352.3
	2001	24.9	23.8	34.1	291.9
	Variation rate	-17.0%	-26.3%	-17.6%	-17.14%

Source : Ministère de la défense from NATO data

17

Table 4 : Share of military expenditures in total public spending in the Initial Law of Finance Voted military expenditures (including pensions) / Total voted public expenditures, % 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 16

 4 .59 19.09 18.38 17.45 17.93 18.1 18.12 17.53 17.33 17.42 17.36 16.10 15.66 17.79 17.87 15,03 18,75

18 Fontanel, J. (

2004

), Géoéconomie de la globalisation, Collection Côté cours, UPMF, Grenoble.

1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 18

  .45 18.84 18.01 18.42 17.98 17.52 16.7 15,98 15,55 15,57 14.97 14.60 14.61 14.38 14.15 14.66 14.67 Source: Lelièvre V. and Annuaire statistique de la défense 2003 19

Expenditures of the general budget, Million 1995 euros

  ', Revue Française d'Economie, printemps, 65-86. and Ministère de la Défense (2002, 2003), op.cit., chapter II.

			French military expenditures, Millions 1995 euros
	40
	38
	36
	34
	32
	30
	28
	26
												Voted military
	24											expenditures (except pensions)
	22											Executed military
												expenditures (except
	20											pensions)
	1	2	3	4	5	6	7	8	9	10	11	12
	From data of French Ministry of Defence
	Graph 4 :
	265
	260
	255
	250
	245
	240
	235											Executed general expenditures Voted general expenditures
	230
	225
	220
	215
	210
	205
	1993	1994	1995	1996	1997	1998	1999	2000	2001	2002	2003	2004
	From data of French Ministry of Defence

20

Foucault, Martial, Le Blanc, Gilles (2004), A political economy approach of defence spending in France : an empirical analysis, presentation at the 7 th conference on Economics and Security, Bristol, 26-28 june 2004.

Table 5

 5

	Année PSv	PSe	MEv	MEe	Bv	Be (%) G (%) Iv	Ie
		(%)	(%)	(%)	(%)
	1993 1,82	3,03	6,78	-2,66	4,82	6,25	-0,89	E	E
	1994 1,36	1,49	-3,68	-0,03	10,64	-2,44	2,07	E	R
	1995 1,79	1,19	-1,42	-7,90	0,76	1,62	1,67	N	N
	1996 0,47	1,42	-3,79	1,58	-3,24	-1,26	1,10	R	R
	1997 -0,64	-0,57	-0,58	-2,97	-0,39	-2,19	1,90	R	R
	1998 0,90	-1,10	-4,15	-2,98	-2,48	-1,17	3,40	R	R
	1999 4,19	3,020	2,28	-0,61	-2,51	-3,21	3,21	R	R
	2000 -1,28	-1,48	-2,01	0,64	-1,41	-1,49	3,79	R	R
	2001 0,61	0,77	-1,22	-0,96	-2,31	0,66	2,10	R	N
	2002 0,73	2,51	-1,44	3,02	1,39	7,14	1,21	E	E
	2003 0,65	1,70	5,57	-4,29	4,77	2,33	0,57	E	E
	2004 2,81		3,15	3,25	3,98		3,39	E

Table 6 : Compared expenditures of military research, except nuclear, in billion euros

 6 According to the law of military programming for2003-2008, this increase of the military R&D budget should continue at least until 2005. It is moreover necessary to take into account the fact that 1,9 billion euros of the public R&D budget have been allocated to the military sector in 200330 . Indeed, "one tier of the companies financed by the defence programs are also financed by the great technological programs", according to a report in 2001 of the Ministry of Research[START_REF]Résultats 2000, estimations 2001 et objectifs socioéconomiques du BCRD 2002[END_REF] , what shows that the French industrial policy through great programs is still relevant today, although more and more concentrated on defence, as it is already the case for the United States. But today France remains behind Anglo-Saxon countries on military R&D. This problem is not only national but also European. Indeed, a report of the Observatoire Economique de la Défense in 2002 uses the concept of "technological disarmament" in Europe, beyond a mere "technological gap" with the United States. If the military expenditures of European countries represented 40% of American expenditures, the rate was only of 25% for R&D spending and 12,5% for R&T spending. Moreover, American enterprises have an advantage coming from a strong support of their State on R&D, notably in aerospace.

		1999	2000	2001	2002	2003
	France	2.15	2.03	2.11	1.85	1.99
	United Kingdom 3.51	3.81	3.91	3.35	2.95
	Germany	1.19	1.22	1.15	0.85	1.08
	Source: National Assembly, Report on the Project of Law of Finance for 2004 29 .

Table 7 :

 7 The French defence industrial base in 2002

	Firm	Turnover	Workforce	Main activities
		in 2002
		(million €)
	Dassault-Aviation	3437	12000	35% : military aircraft
	Group			65% : civil aircraft
	DCN	2200	14200	45% : new manufacturing
				25% : combat systems and equipments
				30% : maintenance in operational condition
	GIAT Industries	777	6200	81,3% : amoured systems
	Group			14,7% : arms, ammunitions
				3% : R&D
				1% : other
	SAGEM Group	2763	12097	64% : communication
				36% : defence and security
	SNECMA Group	6504	38986	64,2% : aerospace propulsion
				37,8% : aeronautic equipments

33

Ministère de la défense (2002), op.cit., p. 9.

Table 8 Variation rate of defence budget and capital expenditures, Initial Law of Finance, from data in constant euros

 8

	Year	Defence	Capital
		budget (%)	expenditures
			(%)
	1993	-0,13	-2,27
	1994	-2,88	-9,39
	1995	-1,28	-1,58
	1996	-2,24	-7,60
	1997	-0,49	-1,63
	1998	-3,00	-9,47

35

Bensahel, L.

(2005)

, Intelligence économique, Fragments de cours, UPMF, Grenoble.

36

Conan, Matthieu (2002), 'Budget de la défense et réduction des dépenses publiques', Revue Française de Finances Publiques, n°79, 87-110, p. 90.

37

During the 1980's, the expenditures of functioning were lower than expenditures of equipment, infrastructure and research-development. It was the price to pay for the French strategy of deterrence "du faible au fort", characterized by a strong independence of choices and very high investments, given the weak economies of scale. However, this situation was possible thanks to the excellent ratio quality/price of conscription.

Table 9 : Total defence expenditures devoted to personnel expenditures (%)

 9

		Average	Average	Average	Average	1999	2000	2001	2002	2003
		1980-4	1985-9	1990-4	1994-9
	France	--	--	--	58,2	60,3	60,4	60,5	60,7	58,8
	Germany	46,6	48,9	57,4	61,5	59,8	60,7	60,3	59,4	60,4
	Italy	59,1	57,8	63,6	71,8	74,0	71,4	72,3	74,0	73,7
	U.K.	37,4	38,6	42,2	39,4	37,9	38,2	38,7	40,0	39,7
	U.S.A.	41,9	37,0	39,3	39,0	38,1	37,7	36,2	36,1	35,3
	Source : From NATO data 39

Table 10 : Total defence expenditures devoted to equipment expenditures (%)

 10

		Average	Average	Average	Average	1999	2000	2001	2002	2003
		1980-4	1985-9	1990-4	1994-9
	France	--	--	--.	21,3	19,4	18,9	19,4	19,1	20,6
	Germany 20,0	19,6	13,5	11,8	13,2	13,5	14,0	14,1	14,0
	Italy	17,4	19,7	16,3	12,9	11,7	14,3	10,3	12,4	12,7
	U.K.	26,2	24,8	21,0	24,8	26,9	25,7	24,2	23,6	23,5
	U.S.A.	21,9	25,6	25,1	26,2	24,9	21,9	25,7	27,4	27,6
	Source : From NATO data 40

NATO (2004), Defence expenditures of NATO countries, www.nato.int/docu/pr/2003/p03-146e.htm

Conan, Matthieu (2002), 'Budget de la défense et réduction des dépenses publiques', Revue Française de Finances Publiques, n°79, 87-110, p. 92.

17 Ministère de la Défense (2002, 2003), Annuaire statistique de la défense, Editions 2002 et 2003, chapter V.

The variation rates have been calculated with data in constant 1995 euros, from the Annuaire Statistique de la Défense, Edition 2002 et édition 2003, Ministère de la Défense.

Carayon, B. (2003), Intelligence économique, compétitivité et cohésion sociale, Rapport au Premier Ministre, La Documentation Française, Paris.


Anne Berry
email: anne.berry@uca.fr

Annegret K Wagler
email: annegret.wagler@uca.fr

The Normal Graph Conjecture for two classes of sparse graphs

Keywords: Normal Graph Conjecture, 1-trees, cacti

Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover Q and a stable set cover S s.t. every clique in Q intersects every stable set in S. Normal graphs can be considered as closure of perfect graphs by means of co-normal products and graph entropy. Perfect graphs have been characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). Körner and de Simone observed that C 5 , C 7 , and C 7 are minimal not normal and conjectured, in analogy to the Strong Perfect Graph Theorem, that every (C 5 , C 7 , C 7 )-free graph is normal (Normal Graph Conjecture, Körner and de Simone 1999). Recently, this conjecture has been disproved by Harutyunyan, Pastor and Thomassé. However, in this paper we verify it for two classes of sparse graphs, 1-trees and cacti. In addition, we provide both linear time recognition algorithms and characterizations for the normal graphs within these two classes.

Introduction

Normal graphs come up in a natural way in an information theoretic context by studying co-normal products [START_REF] Körner | Two-step encoding of finite memoryless sources[END_REF] or graph entropies [START_REF] Cziszár | Entropy splitting for antiblocking corners and perfect graphs[END_REF]. A graph G is normal if G admits cross-intersecting clique and stable set covers, called a valid pair (Q, S): a clique cover Q and a stable set cover S s.t. every clique in Q intersects every stable set in S. (A set is a clique (resp. stable set) if its nodes are mutually adjacent (resp. non-adjacent).) Figure 1 presents three normal graphs and their valid pairs. The class of normal graphs includes the well-studied perfect graphs, and the interest in normal graphs is caused by the fact that they form, in different ways, a weaker variant of perfect graphs.

Berge introduced the latter class in 1960, motivated from Shannon's information-theoretic problem of finding the zero-error capacity of a discrete memoryless channel [START_REF] Shannon | The zero-error capacity of a noisy channel[END_REF]. Shannon's problem has a graph-theoretic formulation, regarding the asymptotic growth of the maximum cliques in the co-normal product G n of G = (V, E), where G 2 has V × V as node set and {(a 1 , b 1 ), (a 2 , b 2 ) : (a 1 , a 2 ) ∈ E or (b 1 , b 2 ) ∈ E} as edge set.

Berge [START_REF] Berge | Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind[END_REF] introduced perfect graphs as those graphs G, where the clique number ω(G ′ ) equals the chromatic number χ(G ′ ) for each induced subgraph G ′ ⊆ G (ω(G) denotes the size of a maximum clique in G, χ(G) the least number of stable sets covering all nodes of G).

Berge observed that chordless odd cycles C 2k+1 with k ≥ 2, the odd holes, and their complements, the odd antiholes C 2k+1 with k ≥ 2, are graphs G with ω(G) < χ(G), see Figure 2. (The complement G has the same node set as G but two nodes are adjacent in G iff they are non-adjacent in G.) This motivated Berge's Strong Perfect Graph Conjecture: a graph G is perfect if and only if G is odd hole-and odd antihole-free. In a sequence of remarkable results, Chudnovsky et al. [START_REF] Chudnovsky | The Strong Perfect Graph Theorem[END_REF] finally turned the above conjecture into the Strong Perfect Graph Theorem.

Normal graphs are a closure of perfect graphs in terms of graph entropy [START_REF] Cziszár | Entropy splitting for antiblocking corners and perfect graphs[END_REF][START_REF] Körner | Graphs that split entropies[END_REF][START_REF] Simonyi | Perfect Graphs and Graph Entropy: An Updated Survey[END_REF] and taking co-normal products: Körner and Longo [START_REF] Körner | Two-step encoding of finite memoryless sources[END_REF] showed that all co-normal products of a graph G are perfect only if G is the union of disjoint cliques. However, all co-normal products of normal (and, therefore, of perfect) graphs are normal by [START_REF] Körner | An Extension of the Class of Perfect Graphs[END_REF]. This motivated Körner and de Simone [START_REF] Körner | On the Odd Cycles of Normal Graphs[END_REF] to ask for a similarity of the two classes in terms of forbidden subgraphs. Körner [START_REF] Körner | An Extension of the Class of Perfect Graphs[END_REF] showed that an odd hole C 2k+1 is normal if and only if k ≥ 4. By the invariance of normality under taking complements, an odd antihole C 2k+1 is also normal if and only if k ≥ 4. C 5 , C 7 and C 7 are minimally not normal since all of their proper induced subgraphs are perfect and, hence, normal. Körner and de Simone conjectured that there are no other minimally not normal graphs:

Conjecture 1 (Normal Graph Conjecture [START_REF] Körner | On the Odd Cycles of Normal Graphs[END_REF]) All graphs without a C 5 , C 7 , and C 7 as induced subgraph are normal.

Note that the non-existence of C 5 , C 7 , and C 7 in a graph is not necessary to be normal (see the first two graphs in Figure 1), and a characterization of normal graphs by forbidden subgraphs is not possible (see [START_REF] Wagler | Constructions for Normal Graphs and Some Consequences[END_REF]). So far, the Normal Graph Conjecture has been verified for webs [START_REF] Wagler | The Normal Graph Conjecture is true for circulants[END_REF] and line graphs [START_REF] Schülzke | The Normal Graph Conjecture for line graphs[END_REF].

In order to treat the Strong Perfect Graph Conjecture from a probabilistic point of view, Prömel and Steger [START_REF] Prömel | Almost all Berge graphs are perfect[END_REF] asked for the relation of perfect and odd hole, odd antihole-free graphs with the same number of nodes. For that, they proved that almost all C 5 -free graphs are perfect. Since every (C 5 , C 7 , C 7 )free graph is C 5 -free, also almost all (C 5 , C 7 , C 7 )-free graphs are perfect and, therefore, normal.

However, the Normal Graph Conjecture has been recently disproved by Harutyunyan, Pastor and Thomassé [START_REF] Harutyunyan | Disproving the Normal Graph Conjecture[END_REF]. Their proof is based on probabilistic arguments, showing the existence of a not normal graph with girth at least 8, i.e., without holes C k of length k ≤ 7 (which also excludes C 7 since it contains C 3 and C 4 ), but without presenting an explicit counterexample.

Both results together imply that there are only few counterexamples and that they should be sparse (due to the large girth ≥ 8). This motivates our study of two classes of sparse graphs w.r.t. normality.

We start with a class of graphs having as many edges as nodes: A 1-tree is a connected graph G = (V, E) with |V | = |E| (obtained from a tree by adding one edge since trees are precisely the connected graphs with |V | -1 = |E|). Hence, G contains exactly one cycle C (due to this property, 1-trees are also called unicyclic graphs). In other words, G can be obtained from the cycle C and certain trees by a sequence of node-identifications.

In Section 3, we characterize the normal 1-trees with the help of two results: a connected triangle-free graph is normal if and only if it has a so-called nice edge cover [START_REF] Körner | On the Odd Cycles of Normal Graphs[END_REF] and the identification of two normal graphs in one node yields a normal graph again. The latter is a consequence from results on clique identification and normality in [START_REF] Wagler | Constructions for Normal Graphs and Some Consequences[END_REF], see Section 2. We obtain that the only not normal 1-trees are either equal to a C 7 or contain a C 5 . This verifies the Normal Graph Conjecture for the class of 1-trees (note: no C 7 can occur in a 1-tree, so it suffices to show that (C 5 , C 7 )-free 1-trees are normal) and leads to a linear time recognition algorithm for normal 1-trees.

We then use these results to treat the larger class of cacti in Section 4. A cactus is a connected graph whose cycles are all edge-disjoint. Thus, a cactus G = (V, E) with k cycles can be considered as a graph obtained from a tree by adding k edges in a certain way (thus cacti admit |V | -1 + k edges) or, alternatively, as a graph obtained from k 1-trees by a sequence of nodeidentifications.

We can, therefore, apply the characterization of normal 1-trees from Section 3 in order to decide whether or not a cactus is normal: As the class of normal graphs is closed under node identification (see Section 2), a cactus is normal if it can be obtained by identifying normal 1-trees in nodes; this verifies the Normal Graph Conjecture for cacti, as in particular all (C 5 , C 7 )-free cacti are normal.

Moereover, there also exist normal cacti containing a C 5 or a C 7 , so our further goal is to recognize normal cacti. As one can obtain a normal graph by identifying certain not normal graphs in one node, see Section 2 again, we examine in detail when a graph constructed by identifying two 1-trees in a node can be normal. This enables us to design an algorithm that decides for a cactus, given a decomposition into 1-trees, in linear time whether or not it is normal. In addition, we achieve a characterization of normal cacti.

We close with some concluding remarks and discuss consequences and some future lines of research.

Parts of the here presented results appeared without proofs in [START_REF] Berry | The Normal Graph Conjecture for classes of sparse graphs[END_REF].

Clique identification and normal graphs

A graph G arises by identification of two disjoint graphs G 1 and G 2 in a clique if there are cliques

Q 1 ⊆ G 1 and Q 2 ⊆ G 2 with |Q 1 | = |Q 2 | and a bijection φ : Q 1 → Q 2 identifying every node v ∈ Q 1 with φ(v) ∈ Q 2 , see Figure 3.
In this section, we discuss how normal graphs can be obtained by clique identification. The first two graphs in Figure 1 are examples of normal graphs, constructed by identifying a non-normal C 5 and C 7 with two edges and one edge, respectively. Figure 3 shows another normal graph obtained by identifying two non-normal graphs in an edge.

However, the non-normal building blocks in these examples are not too far from being normal which shows in particular that it obviously suffices if the nodes in the common clique are covered in one of the two building blocks. This suggests to relax the condition of normality for the building blocks as follows. Let G be a graph such that G has a stable set cover S, G -Q ′ has a clique cover Q Q ′ , for some clique Q ′ , and S and Q Q ′ are cross-intersecting. We call such a graph G nearly normal, (Q Q ′ , S) a nearly valid pair of G, and Q ′ an unnormal clique of G. Figure 4 shows examples of nearly normal graphs together with their nearly valid pairs and unnormal cliques. It was shown in [START_REF] Wagler | Constructions for Normal Graphs and Some Consequences[END_REF] that this weaker form of normality suffices for constructing a normal graph by clique identification, provided the involved stable set covers are suitable.

Lemma 1 [START_REF] Wagler | Constructions for Normal Graphs and Some Consequences[END_REF] Construct G by identifying two nearly normal graphs G 1 and

G 2 in a clique Q * and let Q 1 , Q 2 ⊆ Q * be disjoint unnormal cliques. The resulting graph G is normal if there exist nearly valid pairs (Q Qi (G i ), S(G i ))
for i = 1, 2 satisfying at least one of the following conditions.

(1) S(G i ) contains a stable set S with S ∩ Q * = ∅ for i = 1, 2;

(2) S(G i ) contains no stable set S with S ∩ Q * = ∅ for i = 1, 2;

(3) S(G 1 ) contains a stable set S with S ∩ Q * = ∅ but S(G 2 ) does not, and Q 1 is non-empty (or vice versa).

Lemma 1 provides sufficient conditions to obtain a normal graph via clique identification, but it is not yet clear whether these conditions are also necessary. However, condition (1) of Lemma 1 is certainly satisfied if Q * is a non-maximal clique in G i for i = 1, 2: In order to cover a common neighbor v of all nodes in Q * , S(G i ) has to contain a stable set S with v ∈ S and, thus,

S ∩ Q * = ∅.

Corollary 1 The class of normal graphs is closed under identification in nonmaximal cliques.

In particular, this is the case if Q * consists in a single (but not isolated) node only. Thus, the class of normal graphs is closed under node-identification.

As we have seen that we can construct normal graphs by identifying two unnormal ones in a clique (as in Figure 3), a natural question is whether there exist further ways to construct normal graphs by clique identification. The next lemma from [START_REF] Wagler | Constructions for Normal Graphs and Some Consequences[END_REF] gives an answer showing that the normality or nearnormality of the building blocks is required if the resulting graph is supposed to be normal.

Lemma 2 [START_REF] Wagler | Constructions for Normal Graphs and Some Consequences[END_REF] Let G be a normal graph obtained by identifying two graphs G 1 and G 2 in a clique Q * .

(1) If G admits a valid pair (Q, S) such that S contains no stable set avoiding

Q * , then G 1 and G 2 are normal; (2) If G admits a valid pair (Q, S) such that S contains a stable set avoiding Q * , then G 1 and G 2 are nearly normal with unnormal cliques Q * 1 and Q * 2 such that Q * i ⊆ Q * and Q * 1 ∩ Q * 2 = ∅.
Note that in case (2) of the lemma, Q * 1 and Q * 2 may be empty (such that G 1 and G 2 become normal), but that the weaker condition that G 1 and G 2 are nearly normal already suffices, provided Q * 1 and Q * 2 are disjoint. However, we cannot obtain normal graphs by identifying two non-normal graphs in a node (as the unnormal cliques

Q * 1 , Q * 2 ⊆ Q * cannot be disjoint if |Q * | = 1)
. We call a nearly normal graph almost normal if its unnormal clique consists in one node only. Except the C 5 (whose only possible unnormal clique has size two), all the graphs in Figure 4 are examples of almost normal graphs. We finally obtain the following result which is crucial for our purpose as an immediate consequence of Lemma 2:

Theorem 1 Construct a graph G by identifying two graphs G 1 and G 2 in a node q * , G is normal if

and only if one of the following conditions holds:

(1) G 1 and G 2 are normal;

(2) G 1 is normal and G 2 almost normal with unnormal node q * , or vice versa.

Indeed, condition (1) of the theorem is satisfied if in Lemma 2 either case (1) occurs or case (2) with Q * 1 and Q * 2 empty; condition (2) of the theorem is satisfied if case (2) of Lemma 2 occurs where one of G 1 and G 2 is normal, the other is almost normal with unnormal clique {q * } = Q * .

The Normal 1-Trees

In this section we characterize the normal 1-trees, verify the Normal Graph Conjecture for such graphs, and provide a linear time recognition algorithm for normal 1-trees.

Recall that a 1-tree G is a connected graph containing exactly one cycle C, i.e., G can be obtained from the cycle C and certain trees by a sequence of node-identifications. In order to characterize the normal 1-trees we use Theorem 1 and the result that a connected triangle-free graph is normal if and only if it has a so-called nice edge cover [START_REF] Körner | On the Odd Cycles of Normal Graphs[END_REF], as defined below.

Let G = (V, E) be a graph and F be a minimal edge cover of G, i.e., an inclusion-wise minimal set F ⊆ E s.t. every node in V is the endnode of some edge in F (note that a minimal edge cover is the union of node-disjoint stars). Consider a (not necessarily chordless) odd cycle C in G and the distribution of the edges of F alongside the cycle C. We say that a node v of C is even w.r.t. F if v is the endnode of either none or two edges in F ∩ E(C). Since C is an odd cycle, C has an odd number of even nodes. An edge cover of a graph G is called nice if it is minimal and every odd cycle in G has at least three even nodes.

For example, the bold edges of all three graphs in Figure 1 form nice edge covers, whereas the graphs in Figure 4 do not admit any nice edge cover.

Körner and de Simone showed in [START_REF] Körner | On the Odd Cycles of Normal Graphs[END_REF] that the occurrence of nice edge covers is sufficient for a graph to be normal. In particular, they characterized the triangle-free normal graphs as follows:

Theorem 2 [9] A connected triangle-free graph is normal if and only if it has a nice edge cover.

Let G 1 + v G 2 denote the graph obtained from G 1 and G 2 by identification in the node v. For instance, the second graph in Figure 4 equals C 5 + v K 2 , obtained from a C 5 and a K 2 by node identification; the third graph in Figure 4

equals (C 5 + v K 2 ) + v ′ K 2 , obtained from C 5 + v K 2 and K 2 by identification in another node of the C 5 .
We characterize the normal 1-trees with the help of Theorem 1 and Theorem 2 as follows.

Theorem 3 A 1-tree G is not normal if and only if one of the following conditions holds. Proof A 1-tree G is obtained from a tree by adding one edge. Hence, G contains exactly one chordless cycle C and G -C is a (possibly empty) forest. Thus, G can be obtained from C and certain trees by a sequence of node-identifications. We prove, dependent on the length of C, whether G is normal or not.

Claim If C = C 5 , C 7 then G is normal.
Every hole C = C 5 , C 7 is normal. Hence G can be obtained from normal graphs by a sequence of node-identifications and is, thus, normal by Theorem 1(1). 3

It remains to consider the cases C = C 5 and C = C 7 . Let G 5 denote the first graph depicted in Figure 1.

Claim If C = C 5 then G is normal if and only if G contains the graph G 5 as subgraph.
G is triangle-free in both cases, hence G is normal if and only if it admits a nice edge cover by Theorem 2. Every minimal edge cover F of G uses at most three edges of the C 5 . All possible types of F ∩C 5 are shown in Figure 5 (edges in F ∩ C 5 are drawn with bold lines, even nodes w.r.t. F are black-filled).

F is nice if and only if two consecutive nodes v, v ′ of the C 5 are not covered by the edges in F ∩ C 5 (the types (c), (d), and (e)). In order to cover the nodes v, v ′ by F, there must exist non-empty trees T, T ′ identified with the C 5 in v resp. v ′ . Thus, F is nice if and only if G contains the graph G 5 as subgraph.

(Note that G = C 5 is not normal. If G = C 5 + v T or G = (C 5 + v T ) + v ′ T ′
where v, v ′ are two non-consecutive nodes of the C 5 , then F has to be of type (a) or (b) and is, therefore, not nice.) 3 As there are obviously normal 1-trees admitting a cycle of length 5 or 7, we next address the question of recognizing normal 1-trees.

(a) (b) (c) (d) (e)
To find the cycle in a 1-tree G = (V, E) as first step, we will use Algorithm LexBFS [START_REF] Rose | Algorithmic aspects of vertex elimination on graphs[END_REF] 1 . LexBFS is a specialized Breadth-First Search, which numbers the nodes from n = |V | to 1; each node x obtains a label, denoted by lex(x), which is the decreasing list of the neighbors of x with a higher number than that of x. At each step, a node of lexicographically largest label is chosen to be numbered. A node will be referred to by its number, and when a node x has a label of size 1, f ather(x) will refer to the node in the label.

When the input graph has only one cycle, all the nodes obtain a label of size 1, except the node which 'closes' a cycle, whose label is of size 2. To find the corresponding cycle C, we can use the double label, which yields the next 2 nodes on C; we then go on to take the lowest numbered node between these two: its label yields the next node on C, and so on, until we find a node already in C, which will be the 'root' of C in the tree induced by the LexBFS numbering. The algorithm can stop as soon as more than 7 nodes of the cycle have been found, as the graph is certain to be normal.

Theorem 4 Given a 1-tree G = (V, E), Algorithm 1 decides in O(|V |) whether or not G is normal.
Proof Since G is a 1-tree (i.e., G is connected and has one cycle), Algorithm 1 finds at some point an already labeled neighbor x of the current node y and assigns a double label lex(x) = (y, z) (this can be done in O(|V |) since at most |V | = |E| edges have to be tested). The edge xy closes a cycle C, and it remains to test whether C has length 5 or 7 and the conditions of Theorem 3 are satisfied or not. For that, it suffices to go from y and z 5 steps backwards along the unique paths towards the root node r (always passing from a node to its father), looking for a common node of the paths: if C has length 5 or 7, it has been found that way, and the conditions of Theorem 3 decide about normality (which can be tested in constant time). In all other cases (i.e., if C has length 3, 4, 6, 8 or no cycle has been found yet), G is normal. 2 Remark 1 Algorithm 1 can be turned into a robust algorithm that in addition decides, still in linear time, whether the input graph G = (V, E) is a 1-tree. For that, the graph has to satisfy |V | = |E| and has to be connected. This can be tested by running BFS until no further nodes can be reached (then G is a 1-tree if and only if T contains all nodes from V and exactly one edge xy is not included).

The Normal Cacti

In this section we study cacti, i.e., graphs with edge-disjoint cycles. Since a cactus G with k cycles can be considered as a graph obtained from a tree by adding k edges, we can alternatively obtain G from k 1-trees by a sequence of node-identifications.

As we have characterizations of both normal graphs obtained by nodeidentification (Theorem 1) and normal 1-trees (Theorem 3) from the previous sections, it is natural to decompose a cactus G accordingly: we have to choose a set of articulation points in G s.t. each building block contains exactly one cycle (and is, thus, a 1-tree). We denote the building block of cycle C by B(C).

If all these blocks B(C) of G are normal, then G is clearly normal due to Theorem 1. This holds particularly if none of the cycles C in G has length 5 or 7 by Theorem 3; hence we have:

Corollary 3 The Normal Graph Conjecture is true for cacti.

As there are obviously normal cacti admitting a cycle of length 5 or 7, our further goal is to find a way to decide whether or not a cactus is normal.

For that, we introduce the block-tree of a cactus as follows. For a cactus G = (V, E) with k cycles, we call a set A ⊆ V of articulation points valid if A can be used to decompose G so that the resulting building blocks B(C) contain exactly one cycle C each.

Hence, using a valid set of articulation points decomposes a cactus in as many 1-trees as it has cycles. We obtain the block-tree T (G, A) = (A ∪ B, L) of G by taking as nodes a valid set A of articulation points and the set B of the resulting building blocks B(C) of G and joining two nodes of T (G, A) if and only if one corresponds to an articulation point q ∈ A and the other one to a block B(C) with q ∈ B(C).

By construction, T (G, A) is a tree as it is bipartite and has no cycle. We call a leaf of T (G, A) an endblock of G and say that two blocks of G are adjacent if they share an articulation point in A. Figure 6 shows a cactus G and a block-tree T (G, A) (the black nodes of G are used as articulation points). 6 A cactus and a block-tree

C' C C" q q' B(C") q' B(C) B(C') q Fig.
The main idea is to design an algorithm that, given a cactus G, -finds a valid set A ⊆ V and constructs the block-tree T (G, A), -decides the normality status of each block B(C), -shrinks T (G, A) iteratively by deleting an endblock B(C) and deciding how normal the remaining graph is.

We next explain in detail a procedure to construct A and the block-tree T (G, A), how to decide the normality status of each block B(C), and of the remaining graph after deleting an endblock.

Constructing a block-tree

To construct a block tree, we will again use algorithm LexBFS. A node will be referred to by its number. Each node will be assigned 2 labels: its LexBFS label lex(x), and its block label block(x) which is the list of block numbers which x belongs to. At the end, block(x) has size at least 2 if x is in the set A of valid articulation points. When a node x has a label of size 1, f ather(x) will refer to the node in the label.

In order to test for normality, we will also, while defining a cycle C, collect the set C of nodes of C and the subset D of nodes of C whose degree in G is 3 or more. These information will be added to the block, as well as its status of 'normal' when it can be determined during the construction of the block tree. A Boolean f irstcycle will avoid starting a new block when the very first cycle is encountered.

Theorem 5 Given a cactus G = (V, E), Algorithm 2 constructs a block-tree of G in O(|V |).
Proof LexBFS, like any BFS, induces a spanning tree T of the input graph G. When G is a tree, T is the same as G and all the nodes have a label of size 0 or 1. When G is a cactus, the only edges of G which are not in T are those which close a cycle; clearly, these nodes will obtain a label of size 2. Let us consider such a cycle C; the node x with a double label is chosen to be numbered when all the nodes of C have been numbered, thus x is the lowest-numbered node of C; the highest-numbered node y of C is its root in T , and unless y = n, y will be a valid articulation point, separating any neighbor v of y with v > y from C \ {y}. (Note that n may also be an articulation point, separating the nodes of two cycles).

When the label is not double, the newly numbered node is added to the highest-numbered block which its father belongs to. Algorithm 2 starts a new building block B t each time a cycle C is closed and defined; the highestnumbered node is added to the block tree and to the set A of valid articulation points, with the possible exception of node n; the block labels of the nodes of C are updated: t is added to the block label of the root of C; for the other nodes of C, if the node belongs to only 1 block, its block number is changed to the new block number t; if a node v of C belongs to more than 1 block, then its first block entry is changed to t (by construction, the other block entries correspond to other blocks which t is the root of).

The normality tests define as normal any block whose cycle is not of length 5 or 7. The graph is found to be not normal when either the graph is a C 5 or a C 7 , or when the current block contains a C 5 with only 1 neighbor.

LexBFS runs in linear time [START_REF] Rose | Algorithmic aspects of vertex elimination on graphs[END_REF]; a cactus has O(|V |) edges; defining the cycles costs at most |V | as the cycle edges are traversed only once; thus Algorithm 2 runs in linear O(|V |) time. 2Deciding the normality status of blocks Since each block B(C) is a 1-tree by construction, Theorem 3 characterizes whether it is normal or not. In view of Theorem 1, we have to distinguish the different not normal blocks: it is important to determine whether a not normal block B(C) is almost normal and to specify its unnormal nodes.

For that, we denote the set of possible unnormal nodes of an almost normal block B(C) by U (C) and notice that all of them lie on C: Any valid minimal clique cover of a cactus G uses edges and triangles only, maintaining the notion of even nodes for odd cycles C with length ≥ 5. An unnormal node q of B(C) is not covered by the clique cover Q q of a nearly valid pair (Q q , S) of B(C), but it has to be covered by a clique outside B(C) to become an even node of the cycle C.

As an immediate consequence of Theorem 3 and the possible nearly valid pairs of unnormal 1-trees in Figure 4, we obtain the following proposition.

Proposition 1 A block B(C) with cycle C is (1) not (almost) normal if B(C) = C 5 ; (2) almost normal with U (C) = N (v) ∩ C if C = C 5 and B(C) = C 5 + v T
where T is a tree; Hence, (1)-( 4) are exactly the cases when B(C) is not normal (an if B(C) is almost normal, the possible unnormal nodes are identified). In all other cases (i.e., if Consider a cactus G and a block-tree T (G, A). For an endblock B(C) of T (G, A) and (one of) its adjacent block(s) B(C ′ ) with common node q ∈ A, we denote by G -B(C) (resp. G -B(C) + e) the graph obtained by removing B(C) maintaining q (resp. by replacing B(C) by an edge e attached to q).

(3) almost normal with U (C) = C \ {v, v ′ } if C = C 5 and B(C) = (C 5 + v T ) + v ′ T ′
C = C 5 and B(C) contains G 5 , if C = C 7 but B(C) = C 7 , or if C = C 5 , C 7 ) B(C) is normal, which proves (5).

Shrinking a cactus by removing endblocks

As an immediate consequence of Theorem 1 combined with Proposition 1, we infer the normality of G after removing B(C):

Corollary 4 Let G be a cactus with block-tree T (G, A), B(C) an endblock and B(C ′ ) an adjacent block with common node q ∈ A.

G -B(C) is normal. (2) If B(C) is normal and B(C ′ ) not, then G is normal if and only if G - B(C) + e is normal. (3) If B(C) is almost normal and q ∈ U (C), then G is normal if and only if G -B(C) is normal. (4) If B(C) is almost normal and q ∈ U (C) or if B(C) = C 5 , then G is not normal.
While conditions (1), ( 3) and ( 4) are immediate consequences of Theorem 1 and Proposition 1, we note the following to justify condition [START_REF] Berry | The Normal Graph Conjecture for classes of sparse graphs[END_REF]

: If B(C) is normal but B(C ′ ) not, then G = B(C) + q (G -B(C)) is normal by Theorem 1 if and only if G -B(C) is normal or almost normal with unnormal node q (in B(C ′ ))
. This is the case if and only if K 2 + q (G -B(C)) = G -B(C) + e is normal (which also follows from Theorem 1 since K 2 is normal so that the same conditions for G -B(C) apply in both cases).

The above corollary enables us to shrink a cactus starting from endblocks, keeping normality of the input graph or deciding that G is not normal. Thereby, the cases (1) and (3) allow us to simply remove B(C), (4) provides sufficient conditions that G is not normal, and (2) allows us to maintain or change the normality status of the remaining block B(C ′ ) + e = K 2 + q B(C ′ ) as follows:

Lemma 3 Let G be a cactus with block-tree T (G, A), B(C) a normal endblock and B(C ′ ) an adjacent block with common node q ∈ A.

(1) If B(C ′ ) is almost normal and q ∈ U (C ′ ), then B(C ′ ) + e is normal in G -B(C) + e. (2) If B(C ′ ) is almost normal and q ∈ U (C ′ ), then B(C ′ ) + e remains almost normal with U (C ′ ) in G -B(C) + e. (3) If B(C ′ ) = C 5 , then B(C ′ ) + e is almost normal with U (C ′ ) = N (q) ∩ C ′ in G -B(C) + e.
For the algorithmic process, however, it suffices to shrink the block-tree of a cactus by removing an endblock B(C) and, if necessary, updating the normality status of B(C ′ ) according to Lemma 3.

Example 1 Reconsider the cactus G and its block-tree T (G, A) depicted in Figure 6. Initially, we have the following normality status for its blocks:

-B(C) is almost normal with q ∈ U (C) (Proposition 1(2)), -B(C ′ ) = C 5 is not normal (Proposition 1(1)), -B(C ′′ ) is normal (Proposition 1(5)).
We apply Algorithm 3 and notice that none of the sufficient conditions for G being (not) normal is satisfied. Hence, we proceed with step "shrink" and select one of the two endblocks B(C) and B(C ′′ ) of T (G, A).

If B(C) is selected, then B(C ′ ) is its only adjacent block with common node q ∈ A. None of the two conditions to update the normality status of B(C ′ ) is satisfied, so we only remove B(C) and q from T (G, A). The subsequent test for sufficient conditions reveals that B(C ′ ) = C 5 is now an endblock, hence the decision is "not normal" according to Corollary 4 (4).

On the other hand, if B(C ′′ ) is selected, then B(C ′ ) is its only adjacent block with common node q ′ ∈ A. The second condition is satisfied, hence B(C ′ ) is updated as almost normal with U (C ′ ) = N (q ′ ) ∩ C ′ ; B(C ′′ ) and q ′ are removed from T (G, A). The subsequent test for sufficient conditions reveals that now all blocks are not normal, hence the decision is "not normal" due to Theorem 1.

In both cases, the algorithm finds the correct answer "not normal".

Theorem 6 Given a cactus G = (V, E), Algorithm 3 decides in O(|V |) whether or not G is normal.
To efficiently perform the tests and the selection of an endblock, counters for the number of normal and not normal blocks are used. Then, step "shrink" defines an endblock and an adjacent block, performs two easy tests and updates the normality status of B(C ′ ), if necessary. The tests for condition (4) of Corollary 4 has to be redone only for the new endblock. All this can be clearly done in linear time. 2 Finally, to obtain a characterization when a cactus G is normal, recall that a triangle-free graph is normal if and only if it has a nice edge cover [START_REF] Körner | On the Odd Cycles of Normal Graphs[END_REF] and notice that triangles occur in a cactus only as or in normal blocks. This motivates the construction of a triangle-free graph G ∆ obtained from a cactus G which is normal if and only if G is:

Theorem 7 Let G be a cactus and G ∆ be a graph obtained from G by contracting exactly two nodes from each triangle of G. Then G is normal if and only if G ∆ is normal if and only if G ∆ has a nice edge cover.

Proof Consider a cactus G and a graph G ∆ constructed as above.

Claim 1. G ∆ is a triangle-free cactus.

In G ∆ , none of the triangles of G remains by construction. Since all cycles of G are edge-disjoint, the construction does neither create new triangles, nor cycles sharing an edge. 3

By Claim 1, we can apply Algorithm 2 and 3 also to G ∆ . In order to show that Algorithm 3 applied to G and G ∆ returns the same output, we next consider the normality status of a block B(C) with adjacent triangle ∆ in G and after the contruction in G ∆ . We have: Claim 2. Let B(C) be a block and ∆ be a triangle sharing a node q with B(C) in G and e be the edge in G ∆ obtained by contracting ∆. Then B(C) + q ∆ is as normal as B(C) + e and the sets of unnormal nodes are equal.

This can be easily seen by simple case analysis for all possible normality status of B(C) according to Proposition 1 and observations as in Corollary 4 and Lemma 3. 3 Now, apply Algorithm 3 to G and G ∆ . Notice that the obtained blocktrees can be equal only if G is triangle-free; otherwise T (G ∆ , A ∆ ) contains less blocks than T (G, A).

For the test of sufficient conditions, we have: On the one hand, -if all blocks of G are normal, then all blocks of G ∆ are normal; -if all blocks of G ∆ are normal, but not all of G, then for each not normal block B(C) of G, there is an attached triangle ∆ such that combining B(C) and ∆ yields a normal block.

In both cases, the output is "normal" for G and G ∆ . On the other hand,

if all blocks of G are not normal, then G is triangle-free and G = G ∆ ; -if all blocks of G ∆ are not normal, but not all of G, then each triangle ∆ of G is attached to a not normal block B(C) such that combining B(C) and ∆ in yields a not normal block; -if an endblock of T (G, A) satisfies Corollary 4.( 4), so does a corresponding endblock of T (G ∆ , A ∆ ).

In all cases, the output is "not normal" for G and G ∆ . Finally, contracting two nodes of a triangle can be seen as shrinking T (G, A) and Claim 2 guarantees that the outcome is the same. This proves that G is normal if and only if G ∆ is, and the remaining assertion follows from [START_REF] Körner | On the Odd Cycles of Normal Graphs[END_REF] since G ∆ is triangle-free. 2

Remark 2 For a given cactus G, the triangle-free cactus G ∆ is not unique as there are three choices for the contruction of two nodes per triangle ∆ in G. Similarly, during the process of Algorithm 3, neither the construction of the block-tree T (G, A) of G is unique (due to multiple choices for A), nor the shrinking order (due to multiple choices for end-blocks and their adjacent blocks).

However, for each T (G, A) and shrinking order of G, there is a corresponding graph G ∆ , obtained by contracting the two nodes in the selected triangle ∆ at hand which are not in common with the other selected block. Then, contracting these two nodes of ∆ to obtain G ∆ clearly equals a shrinking step for T (G, A), and the outcome of both proceedures is clearly the same.

Concluding Remarks

In this work, we verify the Normal Graph Conjecture for two classes of sparse graphs, 1-trees and cacti. This shows that no counterexample to the Normal Graph Conjecture can be found in any of these classes (i.e. no cactus with girth at least 8 can be such a counterexample). Moreover, we solve the problem of deciding whether a 1-tree or a cactus is normal even when it does contain a C 5 or a C 7 .

Finally, it would be interesting to generalize our techniques and results to larger graph classes. Canonical candidates are superclasses of cacti, e.g., chordless graphs (whose cycles are all chordless) or outerplanar graphs (who admit an embedding into the plane such that no edges cross and all nodes lie on the outer face). The question is to find suitable decompositions for such graphs into blocks such that the normality status of both the blocks and the recomposed graphs can be determined.

In this context, our future line of research will be to decompose an outerplanar graph into 1-trees with the help of clique separators of size 1 and 2, to characterize normal graphs obtained by identifying two graphs in a clique of size 2 (in analogy to Theorem 1), and to deduce results similar to Corollary 4 and Lemma 3 for deciding the normality status of the graph obtained from

Fig. 1

 1 Fig. 1 Three normal graphs and their valid pairs: bold edges indicate the clique covers, labels the cross-intersecting stable set covers

5 Fig. 2

 52 Fig. 2 Small odd holes and odd antiholes

Fig. 3

 3 Fig. 3 Identifying two non-normal graphs in an edge: bold edges indicate the clique cover, labels the cross-intersecting stable set cover of the resulting normal graph

Fig. 4

 4 Fig. 4 Nearly normal graphs: the gray-shaded nodes induce the unnormal cliques Q ′ , bold edges indicate the clique covers Q Q ′ , labels the cross-intersecting stable set covers

( 1 )

 1 G = C 5 . (2) G = C 5 + v T where T is a tree. (3) G = (C 5 + v T ) + v ′ T ′ where T, T ′ are trees and v, v ′ two non-consecutive nodes of the C 5 . (4) G = C 7 .

Fig. 5 5 Claim

 55 Fig. 5 Possible types of F ∩ C 5

  where T, T ′ are trees and v, v ′ are two non-consecutive nodes of the C 5 ; (4) almost normal with U (C) = C if B(C) = C 7 ; (5) normal otherwise. Proof As any block B(C) is, by construction, a 1-tree, we distinguish according to Theorem 3 the following cases. 1. C = C 5 : Then B(C) is normal if and only if B(C) contains the graph G 5 as subgraph (due to the second claim in the proof of Theorem 3). We consider as subcases the three cases of Theorem 3 where B(C) is not normal and check whether B(C) is almost normal: 1.1 B(C) = C 5 : Then B(C) is not almost normal (since the only possible unnormal clique of C 5 has size two, see Figure 4), which proves (1). 1.2 B(C) = C 5 + v T where T is a tree: Then B(C) is almost normal and the two neighbors of v are the possible unnormal nodes (see Figure 4), which proves (2). 1.3 B(C) = (C 5 + v T ) + v ′ T ′ where T, T ′ are trees and v, v ′ are two nonconsecutive nodes of the C 5 : Then B(C) is almost normal and any neighbor of v or v ′ is a possible unnormal node (see Figure 4), which proves (3). 2. C = C 7 : Then B(C) is normal if and only if B(C) = C 7 by Theorem 3. If B(C) = C 7 , then B(C) is not normal, but almost normal and all its nodes are possible unnormal nodes (see again Figure 4), which proves (4). 3. C = C 5 , C 7 : Then B(C) is normal by Theorem 3 (as all not normal 1-trees contain C 5 or C 7 ).

( 1 )

 1 If B(C) and B(C ′ ) are normal, then G is normal if and only if

  To iteratively shrink (the block-tree of) a cactus G by removing an endblock B(C), we use the following idea based on Theorem 1: If B(C) does not satisfy any of the theorem's conditions, then G is not normal. Otherwise, G is normal if and only if the graph that results from G by either removing B(C) or collapsing a normal endblock B(C) into a K 2 (i.e., into a smaller normal graph) is normal.

Although a simple DFS with a 'father' function could be used with the same time complexity, LexBFS provides us an elegant way to directly determine the studied cycle as well as its nodes.

Algorithm 1 (1-tree normality) input : A 1-tree G = (V, E).

output: An answer to the question: 'Is G normal?'. Initialize all node labels lex() as empty, for all nodes the LexBFS order α() as empty; for i = n downto 1 do Choose a node x with maximum label; α(x) ← i; foreach unnumbered neighbor of x do Append i to lex(x); if |lex(x)| = 2 then Let j 1 and j 2 be the nodes of lex(x), with j 1 > j 2 ; C ← {i, j 1 , j 2 }; c ← 3;

output: 'G fails to be normal' or: a block tree T (G, A) = (A ∪ B, L) of G, with information in each block, a set A of valid articulation points of G, a numbering σ of V , the function block() on V containing the numbers of the blocks each node belongs to. Initialize all node labels as empty;

Choose a node x with maximum lex label; σ(x) ← i; Add t to block(x); foreach unnumbered neighbor y of x do Add i to lex(y);

Algorithm Block Status

input Proof For a given cactus G, Algorithm 2 constructs in linear time a valid set A of articulation points and the corresponding block-tree T (G, A) = (B ∪ A, L). By construction, every block B(C) ∈ B is a 1-tree, so the (easy to test) conditions of Proposition 1 determine its normality status (equals C 5 and is not normal, is almost normal with U (C), is normal); Theorem 3 guarantees that all possible cases are considered. These tests can be performed at no extra cost while creating the blocks of G.

//shrink; Remove B(C) from B and edge B(C)q from L; if q has degree 1 then remove q from A;

Next, if all blocks are normal (resp. not normal), then Theorem 1 guarantees that the whole graph is normal (resp. not normal). If one endblock B(C) satisfies condition (4) of Corollary 4 (i.e., if B(C) is almost normal and

If none of these sufficient conditions applies, it is necessary to choose an endblock B(C); this is done by choosing the remaining block which was defined last by Algorithm 2, which is an endblock by construction as a depth-first search on a tree ends on a leaf; an adjacent block B(C ′ ) is then chosen. Corollary 4 guarantees that the graph obtained by removing the endblock B(C) is normal if and only if G is normal. In the two tested cases, the normality status of the adjacent block B(C ′ ) can be augmented according to Lemma 3. Eventually, B(C ′ ) becomes an endblock after removing B(C).

At the end of step "shrink", we have the same situation as after the initial step and have to repeat both the tests for sufficient conditions and, if they fail, again step "shrink" for the next block.

The block-tree shrinks in each iteration, so that at latest after |B| -1 iterations a decision can be made (as only one block is left). Corollary 4 and Lemma 3 guarantee that the current normality status of the remaining block corresponds to that of G.

removing endblocks of such a decomposition. This would enable us to verify or falsify the Normal Graph Conjecture for outerplanar graphs and to recognize normal outerplanar graphs in a similar way as normal cacti.

Reply to the referee

We would like to thank the referee for the careful reading of the paper and the suggestions made concerning corrections of the algorithms and the clarity of the presentation.

We have handled the comments as follows (all changes made are highlighted in blue within the file "BW rev-highlighted.pdf").

1. we removed the case of tringle-free graphs here 2. this result was obtained in a master thesis -we don't know what could help to reference or access it 3. we added "C 3 and" (note that C 4 is indeed a subgraph of C 7 ) 4. done 5. indeed, Q * 1 or Q * 2 can be empty (s.t. G 1 or G 2 becomes normal); we added an explanation after Lemma 2 6. the theorem is indeed an immediate consequence of Lemma 2 (in the special case when Q * is a single node q * ); we did not add a formal proof, but an explanation how Lemma 2 is applied in this special case 7. done 8. done 9. done (the first if/else block is replaced by a single if condition) 10. done 11. done 12. this fact directly follows from Theorem 1 (an explanation is added how) 13. done 14. the meaning of the sentence is: the (easy to test) conditions of Proposition 1 determine its normality status 15. done 16. done 17. done