Keywords: Supply Chain Management, Flexible manufacturing systems, Human aspects. 1

The co-existence of large and small companies in nowadays supply chains may led to misunderstandings which are prejudicial to the supply chain performance. Based on several studies in aeronautical supply chains, we list some of typical problems linked to the relationship between large and small companies, and show how the solutions promoted by large companies may in some cases be inadequate. We suggest to use different frameworks suggested in social sciences for better understanding the origins of these problems and provide some guidelines for defining a framework of cooperation between large and small companies, oriented on a better mutual understanding.

Supply Chain Management motivates a great interest both on industrial and academics sides, but this ever growing area is most of the time considered according to specific points of view (information technologies, management, social aspects ) which can hardly address its multiple interrelated facets. The present study, focusing on the relationships between large and small companies in aeronautical Supply Chains, suggests to consider the SCM problem with the double perspective of production management and social science. Aeronautic supply chains have indeed specificities which make them especially interesting, for instance regarding the complexity of their planning process but also the co-existence in these macro-organizations of very large and rather small companies. After listing these specificities, some daily problems linked to the cooperation between large and small companies will be explored through case studies. The interpretation of these problems according to the dominant partners of the supply chains (OEM -assemblers of aircrafts or of large sub-systems) will be given, together with the solutions they try to implement. The main characteristics of SMEs as they have been identified in social science research programs will then be emphasized and the implications of such characteristics concerning the planning of supply chains which combine large firms and Email addresses: bernard@enit.fr (Bernard Grabot), anne.mayere@iut-tlse3.f (Anne Mayère).

SMEs (Small and Medium Enterprises) will be explored, by referring to the case studies. It will be shown how the solutions suggested by the large companies may be in contradiction with these characteristics.

2 Supply chains in the aeronautic sector: specificity, problems and actions in progress

Specificity

In the food, pharmaceutical, automotive or electronic sectors, complexity mainly comes from the necessity to manage high volumes: the increasing need in diversification, typical from the automotive sector for instance, is addressed through mass customization, thanks to modularization and component standardization [START_REF] Khota | Mass customization: implementing the emerging paradigm for competitive advantage[END_REF]. Mass production allows using a large set of proven methods aiming at simplifying material flow management. Dedicated or flexible manufacturing lines within the companies, or physical proximity of the OEM and its main suppliers are for instance layout changes which have made possible management techniques such as Just-intime, then lean manufacturing [START_REF] Shah | Lean manufacturing: context, practice bundles, and performance[END_REF]. In this case, mass production has allowed changing the problem from "managing complex flows" to "designing a complex supply chain allowing to manage a simpler flow". This mass production context is far from the reality of the aeronautic sector: even in flexible lines are often implemented in large companies, the context in the area is still to manage a very large number of discrete lots, each composed of few parts, in widely spread supply chains. In a distributed management context, where each company manages its customers and suppliers, this is the perfect context for apparition of chaotic phenomena like the Bullwhip effect [START_REF] Lee | The bullwhip effect in Supply Chains[END_REF] which induces uncontrolled flow variations which may destabilize the supply chain.

Problems in aeronautics supply chains

During many years, the progressive increase of demand and relatively low level of competition in the sector has allowed to focus the efforts on quality of parts and products, and on technical innovation. The context is now very different: competition is fierce and other aspects than technological ones have now to be better addressed, the cycle time and cost of a product being the main ones. In times when the value added by the OEM was around 60-70% of the total value of the product, efforts have been made internally by these large companies, resulting for instance in layout reorganisations making possible internal just-in-time and lean manufacturing, implementation of ERP (Enterprise Resource Planning) systems for a better control of activity and cost, or implementation of CRM (Customer Relationship Management) tools for better understanding and managing the customer's demand. In parallel, the large companies began large programs aiming at motivating their suppliers on management and organisational issues. Today, only 40% of the value is added by the final assembler, and this level will still decrease. One of the reasons of this transfer is that in the past, only "operations" were subcontracted to SMEs which were receiving the semi-manufactured parts, performed their operation and sent the parts back. The effort on flow management was on the large companies, and many unnecessary movements of parts were drastically increasing the cycle times. In order to simplify the global flows, elementary parts were then subcontracted to SMEs, the assembly being performed by the large companies and SMEs were to manage the raw material or component suppliers. Today, still for flow simplification purposes, large companies ask their suppliers to deliver assembled components, or at least "kits", i.e. sets of parts to be assembled in the same component. This requires the SMEs to manage a real bill of materials, and to synchronise several suppliers. In this new context, large companies set a high pressure on the SMEs, considered as having high technical skills but poor motivation and competence on the flow management field which is now critical.

Solutions promoted by large companies

Generating a Supply Planning on the base of orders (firm or forecasted) is usually done using the MRPII method (Manufacturing Resource Planning, see for instance [START_REF] Orlicky | Orlicky's Material Requirement Planning[END_REF]. Using this method, a Sales and Operation Planning (SOP) is firstly built at long term (for instance 1-3 years in the aeronautical sector) on the base of firm orders and forecasts, describing requirements for family of products. A Master Production Schedule (MPS) is then deduced by product at lower term. On the base of these requirements, the bills of materials are used for generating on one side a Supply Planning, and on the other a Production Planning (Material Requirement Planning (MRP) step). The adequacy between the load deduced from the Production plan and the capacity of the company is checked (Load Planning), then the production is scheduled (Scheduling). Release and work in progress management can eventually be done using a Kanban technique. This method allows dealing with complex bills of materials when the demand is known through programs, which is the case in the aeronautical industry. Therefore, Supply Chain management is usually considered in this sector as performable through a cascade of MRPII systems, one in each company (see Figure 1), the information flow being created by the final demand on the OEM.

Fig. 1. Cascade of MRPII systems for Supply Chain Management

Controlling the global performance factors of the Supply Chain, like the cycle time, using a sequence of local decision makings is of course a challenge, and a centralized approach (i.e. the main partner performing a planning for the whole Supply Chain using an APS (Advanced Planning System) [START_REF]Supply Chain Management and Advanced Planning[END_REF] could be considered as more consistent. Nevertheless, the goal is here to co-ordinate autonomous companies, each partner being responsible for the quality and delay of the product it delivers, including what is provided by its own suppliers. This prevents from the use of centralized techniques which set into question autonomy and responsibility of each partner. As a consequence of this context, most OEM have launched programs aiming at promoting the use of MRPII by their suppliers, including the use of Production Management software, together with Lean Manufacturing techniques aiming at simplifying the material flow management. We shall see in next sections that the success of these programs is questionable.

Lessons learnt by case studies

Various problems in the application of the solutions listed in previous sections are visible in the SMEs. In different contexts (consulting, audits, interviews and participation to projects launched by large companies in order to improve the competences of their suppliers), the authors have had access to a large panel of real situations showing new practical problems induced by these various solutions (six Original Equipment Manufacturers (OEM) or large companies manufacturing complex sub-systems, around 20 SMEs). Precise descriptions of the analyzed real situations can be found in [START_REF] Marcotte | Cooperation models for Supply Chain Management[END_REF] or [START_REF] Grabot | A socio-technical view on Supply-Chain management problems[END_REF]; we shall here focus on a synthesis of these situations, addressing the efforts done by the large companies for improving the performance of their smallest partners. These efforts -the "bright side" of cooperation are summarised in the white boxes of Figure 2. At long term, large companies promote the idea of privileged partnership, the SMEs accepting to progress according to the suggested rules benefiting from long term contracts. It is indeed necessary to situate such relationship, requiring an important investment for both partners, at middle long term. Large companies may be subject to unexpected variation in their customer's demand, and are conscious that such variations could set in danger their smallest partners. Therefore, they often include by contract in their forecasts the definition of "firm periods" longer than their own visibility. As explained above, production and management systems have to be simplified first for being more efficient. Improvement methods like Lean Manufacturing are usually promoted in the aeronautic sector in that purpose. For instance, a simplification of the management of the priorities between orders is usually considered as a necessary improvement: if the material flow becomes more regular, simple management techniques like FIFO (First In First Out) considerably increase the predictability of the cycle times at each step of the supply chain, therefore increasing global visibility. Once the production and management systems have been simplified, the MRP technique should allow to implement control loops at various time horizons (long term, using S&OP; middle term, using Material Requirement Planning; short term, using the Load Planning). The expected result of this consistent program of cooperation should be a better performance, beneficial to all partners. Reality seems to be often different, for two main reasons: on one hand, large companies often have a "double discourse" which may set into question their credibility, while on the other hand some of their initiatives are interpreted by SMEs in a totally counterproductive manner. These points -the "Dark side" -are represented by the black boxes of Figure 2. Large companies promote partnerships, but at the same time, they try to decrease their costs by choosing new suppliers in low cost countries. In many cases, we noticed that even SMEs having accepted to follow improvement programs saw some of "their" parts sent in eastern Europe of China. The protection provided by the large companies concerning the final customer's demand is often not noticed by SMEs. On the opposite, many of them draw our attention on a paragraph of their contracts specifying that the contract could be immediately cancelled if parts at lower costs could be found from other suppliers. For large companies, such paragraph only aims at pushing the suppliers to constantly decrease their costs, choosing a new supplier being a time and money consuming activity. Correlated with the arrival of new low cost suppliers, it was clearly not interpreted that way by the SMEs.

In a supply chain, the parts should processed by each supplier according to their criticity regarding the global objectives of the Supply Chain. For instance, parts which manufacturing is on the critical path for obtaining the final product should have high priority. Unfortunately, it is not yet possible to provide such information to all the partners of the chain. Improvement methods such as lean manufacturing are in our opinion prescribed as a substitute with the idea that, if the parts cannot be prioritized according to the global objectives of the Supply Chain, a material steady flow would nevertheless be beneficial. Indeed, one important message of Lean Manufacturing transmitted by large companies to the SMEs was to process the parts according to a FIFO logic (First In First Out), allowing to preserve the sequence of processing built by the OEM. This is clearly against the autonomy of the SMEs: in one case for instance, an SME performing thermal treatment shown us that 60% of its production was for the same customer (a large SME). It was so important to give him satisfaction, which was obtained by giving high priority to its urgent parts. Such attitude would not anymore be possible if using the FIFO principle promoted by the OEM. Nevertheless, it is interesting to notice that this important customer was also working for the same OEM... This means that the Supply Chain can locally be in competition with itself... At a more operational level, MRP is suggested by large companies as the only way to efficiently control manufacturing. Nevertheless, SMEs have to address technological constraints, which they usually handle through ad-hoc information processing, often based on Excel® or Access® tools. In that case, it can be seen that the forecasts are introduced in the production management tool present in the SME, that a long term load/capacity balance is sometimes checked... then orders are derived to a specific application allowing for instance to group components in order to decrease set-up times, or optimize the use of raw materials... Since the sequencing performed by these tools is never re-introduced in the MRP systems, it is afterwards not anymore possible to define the control loops allowing to give middle term and short term visibility. The question is of course not to say who is right and who is wrong, but such local optimization is absolutely necessary for being able to meet the drastic decrease of costs through time imposed by the customers. Asking at the same time to process parts in FIFO in small lots and to decrease costs is considered as inconsistent by the SMEs, who privilege the costs, which is the most visible of their performance criteria.

As a conclusion, it can be seen that instead of an increased performance, the result of such cascade of misunderstandings is usually a decreased trust, which can be easily noticed in the SMEs. In next section, we suggest to apply various concepts suggested by social science to the problem of cooperation between large and small companies. These concepts could help us to better understand the origins of the problems, allowing to suggest some research directions for better addressing them.

4

Another view on the relationship between large and small companies in the supply chain context 4.1 A specific entrepreneurship Project: independence as a core value

The projects promoted by large companies in order to improve the relationship with their small suppliers implicitly consider that the methods which have been successfully applied in large companies should be applied in small ones. Research programs in social sciences concerning SMEs have demonstrated that small and medium firms should not be considered as big firms at a smaller scale [START_REF] Julien | bilan et perspectives[END_REF][START_REF] Julien | The state of the art in small business and entrepreneurship[END_REF][START_REF]Gestion de la PME/PMI[END_REF][START_REF] Torrès | [END_REF]. In particular, it has been shown that a majority of SMEs do not grow beyond a certain size because their managers do not want them to develop and lose their SME characteristics [START_REF] Girard | Pourquoi les PME restent-elles PME ?, Gérer et Comprendre[END_REF]. This is a definite, if implicit, strategic decision. These managers place great emphasis on being able to decide the way their firm will develop, and on keeping a relative freedom regarding their environment. In such a context, the control of the planning process appears to go much further than questions regarding either technical issues or human capabilities. As we will see further on, evolutions such as lean manufacturing, with a process organized according to a FIFO rule, imply that no more pilot should be needed at the subcontractor level; such principles seems to be deeply contradictory with SME manager s search for independence.

Organizational independence is officially highly valued. In many respects, the issue of keeping companies relatively independent meets the customer's goals very well: the large companies, in their pursuit of flexibility, ask their suppliers to be economically sustainable under widely varying demand, even to the extent that they may lose their contract. This places pressure on the SME to diversify by being involved in different supply chains, as a risk reduction strategy. This diversification strategy is coherent with the desire of SME to keep independent of particular clients. But it introduces also a contradictory constraint when the main company tries optimizing its supply chain without taking into account the supplier s involvement in different supply chains, or his type of relationship with different partners of the same supply chain, creating a planning disconnect.

Proximity Logic and Magnifying Effect

The relationship between large and small companies is a good example of "proximity logic" and of its consequence, the "magnifying effect" [START_REF] Torrès | Petitesse des entreprises et grossissement des effets de proximité[END_REF]. The proximity logic is related to the propensity of each person or organization to see herself or himself in the centre of her or his world. In such a centric view of the world, the nearer are the persons, the things or the events, the more important they appear. Only adequate information on the external context can balance this phenomenon, under condition that this information is available, understood, trusted and leads to decisions at least partially consistent with local interests. None of these conditions are in our opinion verified in the context describe din previous sections.

Indeed, both large and small companies seem to consider that their own problems are the most important, e.g. local optimization for SMEs vs. global visibility for large companies, etc. It would be an error to consider that large companies would be right and SMEs wrong, the first ones being aware of the real objectives of the supply chain, while the SMEs are myopic. As a matter of fact, the global objectives of the chain (decrease of costs and cycle times, better customer service, etc.) are the own local objectives of the OEM, and large companies do not really see that these objectives have to be balanced with those of the SMEs for allowing better global satisfaction... Research programs have also analyzed the proximity logic that characterizes the way SMEs are dealing with relationships [START_REF] Torrès | Petitesse des entreprises et grossissement des effets de proximité[END_REF]. Proximity according to geographical or social criteria is often mobilized to choose the partners and suppliers. Therefore, the way production planning is designed and carried out has to be consistent with such a way of setting up relationships. The proximity logic deals also with the choice regarding priorities (the nearer the most important) and related decision process. It is clear that the introduction of far partners like those based on low cost countries sets problems for SMEs used to this "proximity logic" even when they do not feel really menaced by those partners. Another important notion is the wall that tends to separate the inner view and its related priorities and constraints, and the outside. Since SMEs only have a limited number of decision makers, the wall effect is mainly at stake between firms but also between different functions in a large firm. In spite of the process view promoted by large companies, the "horizontal" logic present in various departments of a large company, and the "vertical" logic can be in opposition, phenomenon which can hardly be accepted by Small Companies which do not suffer from this. Therefore, any inconsistence in the behaviour of employees of a large company due to the wall effect is easily considered as planned by SMEs. Promoting at the same time partnership and removing parts from partners for sending them in low cost countries is an example of consequence of such "vertical" wall. Concerning the "horizontal" wall, let us relate the case of a supplier receiving its raw materials from its customer: the raw materials were not yet delivered by the customer, but the orders were already late, and requested... In that case, the "wall" effect separates the two concerned departments of the customer, the magnifying effect preventing each of them to set into question its own behaviour even if it sis inconsistent with an efficient work of the other.

Rel ativ e si gni ficance of beings and phenomena distance here and now Disconti nui ty of t he i m port ance of phenomena because of t he w all effect myself myself Fig. 3. Magnifying effect and wall Such an organizational difference between SME and large firms can have a strong impact on their mutual understanding, therefore on their cooperation capabilities, and at the front line on the relationships between their planners and schedulers. The SME planner will possibly search for combining the constraints and priorities of the commercial and the production components of his enterprise, because of the function proximity that helps him being concerned with such issues. Meanwhile, the large firm planner will probably focus on optimizing its own planning, because the walls are fairly high with the other functions in his firm, preventing for instance to assess the consequences on planning of other policies of the company. He may consider that the SME planner is fairly inconsistent in regards to planning methods and criteria.

Personal trust vs. trust in expert systems

Mutual trust is clearly a key point for a successful cooperation, especially in such a disturbed environment than manufacturing. In his theory concerning The Consequence of Modernity (1990Modernity ( -1994)), Anthony Giddens has discussed the role of trust in social relationships. He differentiates two main types of trust. The most traditional one is trust based on personal relations, often initiated through face-to-face communication. Turn-over and constant reorganizations makes large companies quite reluctant to base their performance on personal relationship. As a consequence, contemporary modernity impulses the development of what A. Giddens calls "expert systems" of "technical accomplishment or professional expertise that organizes large areas of the material and social environment in which we live today . These are impersonal, complex, abstract systems, and methods, like lean manufacturing, MRPII or tools like ERP can be considered as "expert systems" in Gidden's sense. In the process of modernity, people have to count on the reliability of these systems, whose innerworking they usually do not know or conceptually understand.

Let us go back to SMEs. Studies have shown that SME managers were relying strongly on inter-personal trust that fits well with proximity logic and magnifying effect [START_REF] Boutary | TIC et PME : des usages aux stratégies[END_REF][START_REF] Boutary | TIC et prestataires de service dans le développement de communications distantes : questions de proximité et de confiance, TIC et relations de services dans une économie globalisée[END_REF]. Planning, with its logics, methods and tools, forms an expert system; another expert system is the set of information and communication technologies that usually support the treatment required and information exchange. SME managers usually have an in-depth knowledge of their firm activity domain, but the planning "expert system" is often far away from their own expertise. When the large companies ask SMEs to implement MRPII or the like, they are in fact very demanding, looking for a deep cultural change. From the SME managers and employees, it means switching from inter-personal trust, based on commonly practiced social judgment, to trust in abstract systems, that has to be set up from nowhere. As noticed in [START_REF] Grabot | A socio-technical view of Supply Chain Planning: towards an understanding of the interactions between large and small businesses -the case of Aeronautical and Automotive Supply Chains[END_REF], in SMEs, formalism and standardization is often seen as a lack of trust, whereas for big companies they are means to work efficiently . The change at stake is a very important one, and information or training is not sufficient to cope with it. The main values and worldviews are fundamentally different, each of the participants, and moreover the main firms, being absolutely sure that there is a one best way , and that it is the one they have chosen.

Components of trust

An additional dimension comes from L. Karpik research program regarding trust in service relationships [START_REF] Karpik | L économie des singularités[END_REF].

According to Karpik, trust relies on a combination of knowledge and believes. Changing from interpersonal trust to trust in expert system possibly means evolving from knowledge based on personal relationships, including previous experience and the related decisions, to new beliefs in the supposed-to-be reliable abstract system. The fact that main firm planners can be very aware of the interest of planning methods and tools does not by itself produce the same believe in SMEs.

Anthony Giddens underlines the role of gatekeepers for expert systems. These gatekeepers are mainly persons who play an important part in the mediation between an expert system and its users. The personal trust in gatekeepers can play its part in the development of trust in this expert system. This dimension raises the question of the individual relationships between main clients and suppliers. Supply chain managers employed in large companies could play this role of gate-keepers, acting as interfaces between the ERP and the suppliers. They do not seem in position to fulfil it, because they only have for mission to transmit and make operational the message from the expert system, and not to adapt it to the reality of the SMEs. Moreover, they do not always manage to create personal relationships with the suppliers, since the contemporary process of rationalization and optimization tends to sustain the principle according to which the substitutability of employees should be possible as soon as standardized procedures are followed. Such logic, giving priority to standardized exchanges rather than to personal contacts, takes aside the personal dimension in relationships that appears to play an important part in trust production.

Plans and Actions: complementary or contradictory?

The relationship between large companies and their subcontractors could also be analyzed according to Suchman s plan and action theory [START_REF] Suchman | Plans and situated actions; the problem of human-machine communication[END_REF] (citation à mettre): indeed, SME planner gives priority to action (supposed to provide reactivity) compared with main firm planner, who tries to keep the planning relevant (in order to increase efficiency). Table 1 aims at pointing some of the misunderstandings between large companies and small ones by summarizing what are the knowledge's and beliefs on which each kind of structure bases its truth.

Table 1 Bases of trust on large companies and SMEs.

Large companies trust in: Small companies trust in:

-institutionalized/standardized relationships -personal/informal relationships -planning systems:

-strong belief in their efficiency have specific knowledge in planning methods and tools -action strong belief in their capacity to efficiently react to unexpected events -know-how and know-whom to solve problems in action For small companies, performance is linked to people whereas a large company want to have the insurance of a good process quality whatever the people involved. As a consequence, small companies mainly trust in personal, often informal, relationships whereas large companies trust in standardized processes supposed to provide quality insurance. Similarly, they will prefer the "guaranteed" quality provided by a validated planning built by their information systems in comparison with actions improvised by people. The consequence is often that SMEs consider their large partners are poorly reactive, whereas the large companies consider their small suppliers are poorly organized, leading to a poor trust in the other's attitude. As emphasized in Table 1, large companies and small ones do not trust in the same behaviours. Therefore, only discussion/negotiation could allow the two types of organization to agree on common behaviours, based on knowledge and beliefs acceptable by both partners. Such discussions allowing to define the bases of cooperation require in our opinion to be open to the partner's expectations, which is not always the case. Figure 45 shows for instance a simple taxonomy of collaborative situations, suggested in [START_REF] Marcotte | Cooperation models for Supply Chain Management[END_REF]. The first axis of this taxonomy expresses the power of the partner on the Supply Chain, while the other shows the power of the partner on the Supply Chain. For simplification purpose, only two degrees are considered here (high or low) defining four main situations:

1rst situation: this is an ideal collaboration situation. The company is important for the SN and the SN is important for the company. There is a mutual interest in collaborating. In that case, the company is a strategic partner in the SN and discussion is a natural thing between partners.

2nd situation: this is a constraining situation for the SN since the company is important for the SN, but the SN cannot really influence the local decisions towards the SN requirements. The company is a constraining partner for the SN, which does not suggest that it will be ready to make efforts for the Supply Chain, represented here by the large company.

3rd situation: this is a situation of dependency of the company regarding the SN. The SN requirements will then have priority in the local coordination process. The company is a dependent partner. A non specialized subcontractor in a competitive market will be in this situation.

Fig. 4. The situations of collaboration

In situation 1, cooperation is in our opinion "natural", whereas it is questionable in the 4th one. In the second situation, the Supply Chain will have to cope with the constraints induced by its partner. All the SMEs that we have met during this study were in the 3rd situation. As dependent partners, they know what is expected from them even if they do not share these values. Since they can hardly influence their large customers, who in turn want to change their way of working, these companies make a clear difference between an apparent behaviour, conform to what is expected by the large company, but not really applied, and a "parallel" one more conform to their own knowledge and belief. A part of the problem lies in our opinion in the disjunction between these two spaces, coming from an absence of real comparison of the expectations (justified or not) of each partner. In next section, we try to exhibit some technical research directions aiming at coping with some of these problems.

Directions of improvement

Technical tools only cannot solve complex relationship problems as those depicted in previous sections. Therefore, the first condition of improvement is of course that each partner understands the reality of the problems, which is made easier by an ad-hoc interpretation framework. A second condition is certainly to avoid to set the problem in a "who is right -who is wrong" perspective. In our opinion, the following steps could be a first step for setting the relationship between large companies and their small suppliers on another base.

Show the links between local (suppliers) problems and global ones, and conversely. It is often considered that in a Supply Chain, the partner's objectives may be in conflict with the global objectives of the Supply Chain. Reality is in our opinion a little bit more complex, but also more favourable: the links between the local objectives of the suppliers and the global objectives of the supply chain (often represented by the large companies/OEM) is unclear. Indeed, most of the behaviours of the small companies which are condemned by large ones aim at addressing locally global problems, like decrease of the costs by local optimization. Therefore, it is important to analyze the consistence between local and global objectives. In that purpose, a solution could be, like in the GRAI method [START_REF] Doumeingts | Production Management and Enterprise Modelling[END_REF] to compare the decompositions of the global objectives into local ones obtained from a top-down approach (performed by large companies) and from a bottom-up approach (performed by the suppliers). Inconsistencies could then be identified and formalized.

Show how each partner's behaviour is consistent with its decision level (local or global). Each partner could then position its behaviour and actions according to the structure of objectives he identifies, so that the large companies can see the consistence of the SME's behaviours with their objectives, and conversely. The aim is here to gain respect from the other by showing the consistence of its attitude, which is a basic condition for trust. Of course, inconsistencies can be identified during these two steps, on both sides. These inconsistencies, once formalized, have to be discussed.

Allow each partner to show how the other's decision have set difficulties from him. After the two first steps, it is possible to show how the decisions and actions performed by its partners may induce difficulties for him. In that purpose, the negative impact of the partner's actions on its own objectives should be identified and assessed.

Have a common agreement of what can be improved and what should be respected. Once the situation is more clear on both sides, it is important to discuss the mutual adjustments which are required for making the relationship more effective. This difficult step should allow:

1) to fix obvious problems, i.e. to identify and modify inappropriate behaviours 2) to compare the benefits and drawbacks of other behaviours, and to try to find other solutions providing a better balance.

3) to identify unsolved problems, i.e. local (resp. global) objectives which are not addressed by global (resp. local) actions.

Find how the necessity for mutual adjustments can be made consistent with existing planning tools (on both sides). On both sides (local and global), actions are organized through planning tools often used according to a top-down logic. In consistence with the previous steps, it must be decided how top-down and bottom-up planning can be made consistent, by defining areas of negotiation within the information systems.

This sequence of actions have only one goal: explain its own behaviour to its partners so that communication lead to recognition, then to trust, authorizing acceptation of mutual adjustment.

Conclusion

In nowadays Supply Chains, and especially Aeronautic Supply Chains, the leading partners, often large companies, usually consider that their efficient internal way to manage production has to be generalized to all their partners. This is especially true when their partners are SMEs, often considered as poorly organized. In that purpose, large companies promote the standardization of methods and processes in the chain, supported by nowadays IT tools providing communication and planning facilities.

We have tried to emphasize that this evolution sets several problems, mainly linked to the different of nature between large and small companies:

-new management methods, like lean manufacturing, are promising for better meeting the global Supply Chain objectives (cycle time, better reaction...), which are also the objectives of the leading partner. Nevertheless, SMEs do not find in these methods their usual means to lead their own policy (e.g. by choosing the priority of the orders) or to optimize their own local objectives (e.g. through order sequencing according to technological constraints).

-since the relationship between supplier and customer is more and more based on numerical exchange of forecasts and planning, their suspicion for these methods is poorly balanced by their trust on persons, based on a stable relationship. Moreover, problems inherent to large companies (separation between departments, conflicting projects...) or to the tools used (complexity of ERP systems) make that this personal trust can hardly be replaced by a trust on the methods and tools allowing to move from personal relationship to IT-based relationship.

Fig. 2 .

 2 Fig. 2. The Bright and Dark sides of OEM/SMEs cooperation

4 . 6

 46 Power as a Disturber of the Trust-based Relationship

  4th situation: it is a situation of mutual indifference regarding coordination between the SN and the company. Without constraints, strategic issues, or mutual interest, there are very few reasons to collaborate or to put energy in coordination. The company is a non strategic partner regarding the SN.

We have suggested to use various concepts (wall effect, magnifying effect, trust in expert systems...) for better understanding these problems. The first conclusion is that instead of standardized communication protocols, SMEs need "negotiation spaces" with their customers [20] which would allow them to better express their problems and try to find solutions addressing both local and global constraints of the Supply Chain. Even if some ideas have been suggested in that purpose, how these negotiation spaces can be set-up in the context of present IT tools, like ERP systems, is a complex problem which will be further investigated in future studies.


Brice Effantin
email: brice.effantin@u-bourgogne.fr

Hamamache Kheddouci
email: kheddouc@u-bourgogne.fr

The b-chromatic number of some power graphs

Keywords: b-chromatic number, coloring, cycle, path, power graphs

Let G be a graph on vertices v 1 , v 2 , . . . , v n . The b-chromatic number of G is defined as the maximum number k of colors that can be used to color the vertices of G, such that we obtain a proper coloring and each color i, with 1 ≤ i ≤ k, has at least one representant x i adjacent to a vertex of every color j, 1 ≤ j = i ≤ k. In this paper, we give the exact value for the b-chromatic number of power graphs of a path and we determine bounds for the b-chromatic number of power graphs of a cycle.

Introduction

We consider graphs without loops or multiple edges. Let G be a graph with a vertex set V and an edge set E. We denote by d(x) the degree of the vertex x in G, and by dist G (x, y) the distance between two vertices x and y in G. The p-th power graph G p is a graph obtained from G by adding an edge between every pair of vertices at distance p or less, with p ≥ 1. It is easy to see that G 1 = G. In the literature, power graphs of several classes have been investigated [START_REF] Ädt | Perfect elimination orderings of chordal powers of graphs[END_REF][START_REF] Dahlhaus | On strongly chordal graphs[END_REF][START_REF] Kheddouci | Packing of two copies of a tree into its fourth power[END_REF]. In this note we study a vertex coloring of power graphs. The power graph of a path and the power graph of a cycle can be also considered as respectively subclasses of distance graphs and circulant graphs. The distance graph G(D) with distance set D = {d 1 , d 2 , . . .} has the set Z of integers as vertex set, with two vertices i, j ∈ Z adjacent if and only if |i -j| ∈ D. The circulant graph can be defined as follows. Let n be a natural number and let S = {k 1 , k 2 , . . . , k r } with k 1 < k 2 < . . . < k r ≤ n/2. Then the vertex set of the circulant graph G(n, S) is {0, 1, . . . , n -1} and the set of neighbors of the vertex i is {(i ± k j )mod n| j = 1, 2 . . . , r}.

The study of distance graphs was initiated by Eggleton and al. [START_REF] Eggleton | Coloring the real line[END_REF]. Recently, the problem of coloring of this class of graphs has attracted considerable attention, see e.g. [START_REF] Ruzsa | Distance Graphs with Finite Chromatic Number[END_REF][START_REF] Zhu | Pattern periodic coloring of distance graphs[END_REF]. Circulant graphs have been extensively studied and have a vast number of applications to multicomputer networks and distributed computation (see [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF][START_REF] Knuth | The Art of Computer Programming[END_REF]). The special cases we consider are the distance graph G(D) with finite distance set D = {1, 2, . . . , p} which is isomorphic to the p-th power graph of a path and the circulant graph G(n, S) with S = {1, 2, . . . , p} which is isomorphic to the p-th power graph of a cycle.

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

A k-coloring of G is defined as a function c on V (G) = {v 1 , v 2 , . . . , v n } into a set of colors C = {1, 2, . . . , k} such that for each vertex v i , with 1 ≤ i ≤ n, we have c v i ∈ C. A proper k-coloring is a kcoloring satisfying the condition c x = c y for each pair of adjacent vertices x, y ∈ V (G). A dominating proper k-coloring is a proper k-coloring satisfying the following property P: for each i, 1 ≤ i ≤ k, there exists a vertex x i of color i such that, for each j, with 1 ≤ j = i ≤ k, there exists a vertex y j of color j adjacent to x i . A set of vertices satisfying the property P is called a dominating system. Each vertex of a dominating system is called a dominating vertex. The b-chromatic number ϕ(G) of a graph G is defined as the maximum k such that G admits a dominating proper k-coloring.

The b-chromatic number was introduced in [START_REF] Irving | The b-chromatic number of a graph[END_REF]. The motivation, similarly as for the previously studied achromatic number (cf. e.g. [START_REF] Harary | The achromatic number of a graph[END_REF][START_REF] Hughes | The achromatic number of graphs: A survey and some new results[END_REF]), comes from algorithmic graph theory. The achromatic number ψ(G) of a graph G is the largest number of colors which can be assigned to the vertices of G such that the coloring is proper and every pair of distinct colors appears on an edge. A proper coloring of a graph G using k > χ(G) colors could be improved if the vertices of two color classes could be recolored by a single color so as to obtain a proper coloring. The largest number of colors for which such a recoloring strategy is not possible is given by the achromatic number. A more versatile form of recoloring strategy would be to allow the vertices of a single color class to be redistributed among the colors of the remaining classes, so as to obtain a proper coloring. The largest number of colors for which such a recoloring strategy is not possible is given by ϕ(G) (these recolorings are discussed in [START_REF] Irving | The b-chromatic number of a graph[END_REF] and [START_REF] Kratochvíl | On the b-chromatic number of graphs[END_REF]). Thus ϕ(G) ≤ ψ(G) (also given in [START_REF] Irving | The b-chromatic number of a graph[END_REF]). From this point of view, both complexity results and tight bounds for the b-chromatic number are interesting. The following bounds of b-chromatic number are already presented in [START_REF] Irving | The b-chromatic number of a graph[END_REF].

Proposition 1 Assume that the vertices x 1 , x 2 , . . . , x n of G are ordered such that d(x 1 ) ≥ d(x 2 ) ≥ . . . ≥ d(x n ). Then ϕ(G) ≤ m(G) ≤ ∆(G) + 1, where m(G) = max{1 ≤ i ≤ n : d(x i ) ≥ i -1} and ∆(G) is the maximum degree of G.
R. W. Irving and D. F. Manlove [START_REF] Irving | The b-chromatic number of a graph[END_REF] proved that finding the b-chromatic number of any graph is a NP-hard problem, and they gave a polynomial-time algorithm for finding the b-chromatic number of trees. Kouider and Mahéo [START_REF] Kouider | Some bounds for the b-chromatic number of a graph[END_REF] gave some lower and upper bounds for the b-chromatic number of the cartesian product of two graphs. They gave, in particular, a lower bound for the b-chromatic number of the cartesian product of two graphs where each one has a stable dominating system. More recently in [START_REF] Kratochvíl | On the b-chromatic number of graphs[END_REF], the authors characterized bipartite graphs for which the lower bound on the b-chromatic number is attained and proved the NP-completeness of the problem to decide whether there is a dominating proper k-coloring even for connected bipartite graphs and k = ∆(G) + 1. They also determine the asymptotic behavior for the b-chromatic number of random graphs.

In this paper, we present several exact values and determine bounds for the b-chromatic number of power graphs of paths and cycles.

Let Diam(G) be the diameter of a graph G, defined as the maximum distance between any pair of vertices of G. Let us begin with the following observation.

Fact 2 For any graph G of order n, if Diam

(G) ≤ p, then ϕ(G p ) = n, with p ≥ 2. Proof. If Diam(G) ≤ p, it is trivial to see that G p is a complete graph. So ϕ(G p ) = n. ✷
Let G be a path or a cycle on vertices x 1 , x 2 , . . . , x n . We fix an orientation of G (left to right if G is a path and clockwise if G is a cycle). For each 1 ≤ i ≤ n, we denote by

x + i (resp. x - i ) the successor (resp. predecessor) of x i in G (if any). For 1 ≤ i = j ≤ n, we define [x i , x j ] G , [x i , x j ) G and (x i , x j )
G as the set of consecutive vertices on G from respectively x i to x j , x i to x - j and x + i to x - j , following the fixed orientation of G. If there is no ambiguity, we denote

[x i , x j ] G , [x i , x j ) G and (x i , x j ) G by respectively [x i , x j ], [x i , x j ) and (x i , x j ).
In all figures, the graph G is represented with solid edges. Edges added in a p-th power graph G p are represented with dashed edges. In some figures, vertices are surrounded and represent a dominating system of the coloring. In any coloring of a graph G, we will say that a vertex x of G is adjacent to a color i if there exists a neighbor of x which is colored by i.

Power Graph of a Path

In this section, we determine the b-chromatic number of a p-th power graph of a path, with p ≥ 1. First we give a lemma used in the proof of Theorem 4. Then the b-chromatic number of a p-th power graph of a path is computed. Lemma 3 For any p ≥ 1, and for any n ≥ p + 1, let P n be the path on vertices x 1 , x 2 , . . . , x n . For each integer k, with p + 1 ≤ k ≤ min(2p + 1, n), there exists a proper k-coloring on P p n . Moreover each vertex x, such that x ∈ {x k-p , x k-p+1 , . . . , x n-k+p+1 }, is adjacent to each color j, with 1 ≤ j = c x ≤ k.

Proof. As k ≥ p + 1, it is easy to see that if we put the set of colors {1, 2, . . . , k} cyclically on V (P n ), then two adjacent vertices will not have the same color. The coloring is thus a proper k-coloring.

Let S = {x k-p , x k-p+1 , . . . , x n-k+p+1 }. First we show that each vertex of S is adjacent to at least k -1 ver- tices. Observe that the vertex x k-p is adjacent to (k -p -1) + p = k -1 vertices. And the vertex x n-k+p+1 is adjacent to p + n -(n -k + p + 1) = k -1 vertices. Since each vertex x i , with k -p + 1 ≤ i ≤ n -k + p, has a degree d(x i ) ≥ d(x k-p )
, then each vertex of S is adjacent to at least k -1 other vertices. Next, we can see by the construction that all the colors {1, 2, . . . , k}\{c x i } appear between the first and the last neighbor of x i . Therefore each vertex x i of S is adjacent to each color j, with 1

≤ j = c x i ≤ k and k -p ≤ i ≤ n -k + p + 1.
✷

The b-chromatic number of a p-th power graph of a path is given by: Theorem 4 Let P n be a path on vertices x 1 , x 2 , . . . , x n . The b-chromatic number of P p n , with p ≥ 1, is given by:

ϕ(P p n ) =      n if n ≤ p + 1, (1)
p + 1 + n-p-1 3 if p + 2 ≤ n ≤ 4p + 1, (2) 2p + 1 if n ≥ 4p + 2 (3)
Proof.

1. If n ≤ p + 1, then Diam(P n ) ≤ p. So, by Fact 2, ϕ(P p n ) = n.
2. We prove first that ϕ(P

p n ) ≥ p + 1 + n-p-1 3 for p + 2 ≤ n ≤ 4p + 1. Let k = p + 1 + n-p-1 3 .
By Lemma 3, we give a proper k-coloring of P p n . For example, Figure 1 shows a dominating proper 5-coloring of P 3 8 . Let S ′ be the set of vertices {x k-p , x k-p+1 , . . . , x 2k-p-1 }. Since 2kp -1 ≤ nk + p + 1, then S ′ ⊆ {x k-p , x k-p+1 , . . . , x n-k+p+1 }. By Lemma 3, S ′ is a dominating system. As the coloring is proper and has a dominating system, we obtain a dominating proper k-coloring. So, ϕ(P

p n ) ≥ p + 1 + n-p-1 3 .
Next we prove that ϕ(P

p n ) ≤ p + 1 + n-p-1 3 for p + 2 ≤ n ≤ 4p + 1.
The proof is by contradiction.

Suppose that there exists a dominating proper k ′ -coloring such that

k ′ > p + 1 + n -p -1 3 . (1)
Let W = {w 1 , w 2 , . . . , w k ′ } be a dominating system of the coloring on P p n (following the orientation of P n , we meet w 1 , w 2 , . . . , w k ′ ). The vertices w 1 and w k ′ are adjacent to, at most, p different colors in [w 1 , w k ′ ]. As w 1 (respectively w k ′ ) is a dominating vertex, it must be adjacent to at least k ′ -1 different colors. Then, there are at least k

′ -p -1 vertices on [x 1 , w 1 ) (respectively (w k ′ , x n ]). Therefore, n -k ′ ≥ n -|[w 1 , w k ′ ]| ≥ 2(k ′ -p -1).
On the other hand by hypothesis k

′ ≥ p + 2 + n-p-1 3 , so that n -k ′ ≤ n -p -2 -n-p-1 3 .
These two results give the following inequality,

2(k ′ -p -1) ≤ n -k ′ ≤ n -p -2 - n -p -1 3 , k ′ ≤ 1 2 (n + p - n -p -1 3 ). (2)
By ( 1) and (2), we obtain,

1 2 (n + p - n -p -1 3 ) ≥ k ′ ≥ p + 2 + n -p -1 3 , n -p -4 ≥ 3 n -p -1 3 ,
which is a contradiction. Hence such a coloring does not exist. Therefore, ϕ(P

p n ) ≤ p + 1 + n-p-1 3
.

We deduce from these two parts that ϕ(P

p n ) = p + 1 + n-p-1 3 .

∆(P

p n ) = 2p, so by Proposition 1, ϕ(P p n ) ≤ 2p + 1. Lemma 3 gives a proper (2p + 1)-coloring and shows that each vertex x of the set {x p+1 , x p+2 , . . . , x 3p+1 } is adjacent to each color j with 1 ≤ j = c x ≤ k. So this set is a dominating system and ϕ(P

p n ) ≥ 2p + 1. Therefore ϕ(P p n ) = 2p + 1.
For example, Figure 2 gives a dominating proper 7-coloring of P 3 15 . In this section, we study the b-chromatic number of a p-th power graph of a cycle, with p ≥ 1. First we give two lemmas used in the proof of Theorem 7. Then we bound the b-chromatic number of a p-th power graph of a cycle.

Lemma 5 Let C

p n be a p-th power graph of a cycle C n , with p ≥ 2. For any 2p

+ 3 ≤ n ≤ 4p, let k ≥ min(n -p -1, p + 1 + n-p-1 3 ). Then n ≤ 2k.
Proof. The proof is by contradiction. Suppose n ≥ 2k + 1. We consider two cases. Firstly,

k ≥ n -p -1. So, n ≥ 2k + 1 ≥ 2(n -p -1) + 1, n ≤ 2p + 1,
which is a contradiction. Secondly, k ≥ p + 1 + n-p-1

3

. So,

n ≥ 2k + 1 ≥ 2(p + 1 + n -p -1 3 ) + 1, n -2p -3 ≥ 2 n -p -1 3 ,
which is a contradiction too. ✷ Lemma 6 For any p ≥ 2, and for any 2p

+ 3 ≤ n ≤ 4p, let C n be the cycle on vertices x 1 , x 2 , . . . , x n . Let k = min(n -p -1, p + 1 + n-p-1 3
). So there exists a proper k-coloring on C p n . Moreover each vertex x, such that x ∈ {x k-p , x k-p+1 , . . . , x 2k-p-1 }, is adjacent to each color j, with 1 ≤ j = c x ≤ k.

Proof. We put the set of colors {1, 2, . . . , k} cyclically on

V (C n ). As k ≤ p + 1 + n-p-1 3
and n ≤ 4p, then k ≤ 2p + 1. Moreover, by Lemma 5 we deduce that 2k ≥ n ≥ 2p + 3 ≥ k + 2. So, the full set of colors {1, 2, . . . , k} appears consecutively at least once, and at most twice, in the cyclic coloring of C p n . As 2k ≥ n ≥ 2p + 3, we have k ≥ p + 1. Furthermore, by definition of k we have nk ≥ p + 1. Thus, as k ≥ p + 1 and nk ≥ p + 1, the coloring is proper.

Let P n be the subpath of C n induced by x 1 , x 2 , . . . , x n . Let S = {x k-p , x k-p+1 , . . . , x k+(k-p-1) }. As p + 1 ≤ k ≤ 2p+1 and 2kp-1 ≤ n-k + p+1, then by Lemma 3 each vertex x i of S, with kp ≤ i ≤ 2kp-1, is adjacent to each color q, with 1 ≤ q = c x i ≤ k, on P p n . Therefore each vertex x i of S is adjacent to each color q, with 1 ≤ q = c x i ≤ k, on C

ϕ(C p n ) =                n if n ≤ 2p + 1, (1) p + 1 if n = 2p + 2, ( 2
) (≥) min(n -p -1, p + 1 + n-p-1 3 ) if 2p + 3 ≤ n ≤ 3p (3) p + 1 + n-p-1 3 if 3p + 1 ≤ n ≤ 4p (4) 2p + 1 if n ≥ 4p + 1 (5)
Proof.

1. If n ≤ 2p + 1, then Diam(C n ) ≤ p. So, by Fact 2, ϕ(C p n ) = n.
2. To color the graph, we put the set of colors {1, 2, . . . , p + 1} cyclically twice. One can easily see that this coloring is a proper (p + 1)-coloring. Let S be the set of vertices {x 1 , x 2 , . . . ,

x p+1 }. Each vertex x i , with 1 ≤ i ≤ p + 1, is adjacent to n -2 vertices. Since n -2 ≥ p + 1, then each vertex x i (1 ≤ i ≤ p + 1)
of S is adjacent to all colors other than c x i . So the set S is a dominating system. We now show that, in any dominating proper coloring, vertices x i and x i+p+1 must have the same color. For the subgraph induced by vertices x 1 , x 2 , . . . , x p+1 , we have a clique and we can assume without loss of generality that these vertices are colored by 1, 2, . . . , p + 1 respectively. If there exists a dominating vertex of color j, for some j > p + 1, then this vertex is x p+1+i for some i (1 ≤ i ≤ p + 1). Vertex x p+1+i is not adjacent to x i , but every other vertex is adjacent to x i , so that x p+1+i cannot be a dominating vertex, a contradiction. Therefore ϕ(C

p n ) = p + 1 for n = 2p + 2. 3. Let k = min(n -p -1, p + 1 + n-p-1 3
).

By Lemma 6 there exists a dominating proper k-coloring for 2p

+ 3 ≤ n ≤ 3p. Therefore ϕ(C p n ) ≥ min(n -p -1, p + 1 + n-p-1 3
). For example, in Figure 3, we give a dominating proper 6-coloring of C 4 11 .

Let k

= p + 1 + n-p-1 3 .
For 3p + 1 ≤ n ≤ 4p, Lemma 6 gives a dominating proper k-coloring. This proves that ϕ(C

p n ) ≥ min(n -p -1, p + 1 + n-p-1 3
). For example, Figure 4 shows a dominating proper 6-coloring of

C 3 11 . Next, we prove that ϕ(C p n ) ≤ k. Suppose there exists a dominating proper k ′ -coloring for C p n , with k ′ ≥ p + 2 + n-p-1 3
, for the sake of contradiction. Let W = {w 1 , w 2 , . . . , w k ′ } be a set of dominating vertices on C n (following the orientation of C n , we meet w 1 , w 2 , . . . , w k ′ ). We distinguish two cases.

≤ i ≤ k ′ , |(w i , w i+1 )| ≤ p -1. As k ′ ≥ p + 2 + n-p-1
|(w k ′ , w 1 )| ≤ p -1, where |(w k ′ , w 1 )| = n -|[w 1 , x)| -|[x, w k ′ )| -1.
Therefore, we have

n -|[w 1 , x)| -|[x, w k ′ )| -1 ≤ p -1, n -2p -1 ≤ p -1, n ≤ 3p,
which is a contradiction.

Case 2: There exists r, with 1 ≤ r ≤ k ′ and r is taken modulo k ′ , such that |(w r , w r+1 )| ≥ p. Let X be the set of vertices of [w r+1 , w r ] (see Figure 5). Let X C be the set of colors appearing in X. Let Γ X (x i ) be the set of neighbors of x i in X and Γ c X (x i ) the set of colors appearing in Γ X (x i ),

with 1 ≤ i ≤ n. Let A = X C \(Γ c X (w r ) ∪ {c w r }). Let B = X C \(Γ c X (w r+1 ) ∪ {c w r+1 }).
We discuss two subcases.

≥ k ′ . Then, |(w r , w r+1 )| ≤ n -k ′ and |X c | = k ′ . As the vertices of Γ X (w r ) form a clique, then |Γ c X (w r )| = |Γ X (w r )| = p. So we have |A| = |X C | -|Γ c X (w r )| -1 = k ′ -p -1.
In the same way, we deduce that

|B| = k ′ -p -1. As |X| ≤ 2p + 2, we have X ⊆ (Γ X (w r ) ∪ Γ X (w r+1 ) ∪ {w r , w r+1 }) (see Figure 6.a). So, A ⊆ (Γ c X (w r+1 ) ∪ {c w r+1 }) and B ⊆ (Γ c X (w r ) ∪ {c w r }). Let q ∈ {1, 2, . . . , k ′ }. If q ∈ A (resp. q ∈ B) then q / ∈ (Γ c X (w r ) ∪ {c w r }) (resp. q / ∈ (Γ c X (w r+1 ) ∪ {c w r+1 })
) and so q / ∈ B (resp. q / ∈ A). Therefore, A ∩ B = / 0. As w r (resp. w r+1 ) is a dominating vertex and |(w r , w r+1 )| ≥ p, the colors of A (resp. B) must be repeated in (w r , w r+1 ). Therefore,

|A| + |B| ≤ |(w r , w r+1 )|, 2(k ′ -p -1) ≤ n -k ′ , 3k ′ ≤ n + 2p + 2, 3 n -p -1 3 ≤ n -p -4, which is a contradiction. Subcase 2: |X| ≥ 2p + 3. As in Subcase 1, we have |A| = k ′ -p -1 and |B| = k ′ -p -1. Let X ′ = X\(Γ X (w r ) ∪ Γ X (w r+1 ) ∪ {w r , w r+1 }) (see Figure 6.b). So |X ′ | ≥ |A ∩ B|. Since w r (resp. w r+1
) is a dominating vertex and |(w r , w r+1 )| ≥ p, the colors of A (resp. B) must be repeated in (w r , w r+1 ). Then,

|A| + |B| -|A ∩ B| ≤ |(w r , w r+1 )| ≤ n -2p -2 -|X ′ |, 2(k ′ -p -1) -|A ∩ B| ≤ n -2p -2 -|A ∩ B|, 2(p + 2 + n -p -1 3 ) ≤ n,
which is a contradiction. Therefore there does not exist a dominating proper k ′ -coloring, with k ′ ≥ p + 2 + n-p-1

3

.

This completes the proof of ϕ(C We then give a proper (2p + 1)-coloring. It is constructed in two steps. First, we put (2p + 1) different colors on the (2p + 1) first vertices (c x i := i for 1 ≤ i ≤ 2p + 1). In the second step, we have two cases. If n = 4p + 1, we color the remaining vertices as follows: c x i := c x i-2p-1 for 2p + 2 ≤ i ≤ n. If n ≥ 4p + 2, then the remaining vertices are colored as follows: c x i := c x i-2p-1 for 2p + 2 ≤ i ≤ 4p + 2, and c x i := c x i-p-1 for 4p + 3 ≤ i ≤ n. Then the distance between two vertices colored by the same color c is at least p + 1. So the coloring is proper. By an analogue proof of Lemma 3, one can prove that each vertex x i , with p + 1 ≤ i ≤ 3p + 1, is a dominating vertex. So this coloring is a dominating proper (2p + 1)-coloring. This construction shows that ϕ(C p n ) ≥ 2p + 1. Therefore we have proved that ϕ(C p n ) = 2p + 1. For example, Figure 7 gives a dominating proper 7-coloring C 3 16 . ✷

Open Problem

In section 3, we have obtained the exact values of ϕ(C p n ), except in case 2p + 3 ≤ n ≤ 3p where we give a lower bound. We believe that min(np -1, p + 1 + n-p-1

3

) is the exact value of ϕ(C p n ) for 2p + 3 ≤ n ≤ 3p.

Fig. 1 :

 1 Fig. 1: Coloring of P 3 8

Fig. 2 : 3 15 3

 233 Fig. 2: Coloring of P 3 15

Theorem 7

 7 Let C n be a cycle on vertices x 1 , x 2 , . . . , x n . The b-chromatic number of C p n , with p ≥ 1, is

Fig. 3 : 3 = 7 Fig. 4 : 11 Case 1 :

 3374111 Fig. 3: Coloring of C 4 11 (np -1 = 6, p + 1 + n-p-1 3

3 ,

 3 by a straightforward modification of the proof of Lemma 5, we have n < 2k ′ . So, there exists at least one color c not repeated in C p n (i.e. there are not two distinct vertices with the same color c). Without loss of generality, suppose that c appears on the vertex x, with x ∈ V (C n ). Therefore x is a dominating vertex and each other dominating vertex is adjacent to x. Then, |[w 1 , x)| ≤ p and |[x, w k ′ )| ≤ p. As for each i, with 1 ≤ i ≤ k ′ , we have |(w i , w i+1 )| ≤ p -1 and since on the cycle the next dominating vertex from w k ′ is w 1 , then

Fig. 5 :

 5 Fig. 5: A dominating system on C p n and the set X

Fig. 6 :

 6 Fig. 6: Neighborhoods of w r and w r+1 on X when a) |X| ≤ 2p + 2 and b) |X| ≥ 2p + 3

Fig. 7 :

 7 Fig. 7: Coloring of C 3

Acknowledgments

The authors thank the referees for useful suggestions that led to this improved version.


Vida Dujmović

David R Wood
email: davidw@scs.carleton.ca

On Linear Layouts of Graphs †

Keywords: graph layout, graph drawing, stack layout, queue layout, arch layout, book embedding, queue-number, stack-number, page-number, book-thickness. Mathematics Subject Classification: 05C62 (graph representations)

In a total order of the vertices of a graph, two edges with no endpoint in common can be crossing, nested, or disjoint. A k-stack (respectively, k-queue, k-arch) layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (respectively, non-nested, non-disjoint) edges. Motivated by numerous applications, stack layouts (also called book embeddings) and queue layouts are widely studied in the literature, while this is the first paper to investigate arch layouts.

Our main result is a characterisation of k-arch graphs as the almost (k + 1)-colourable graphs; that is, the graphs G with a set S of at most k vertices, such that G \ S is (k + 1)-colourable. In addition, we survey the following fundamental questions regarding each type of layout, and in the case of queue layouts, provide simple proofs of a number of existing results. How does one partition the edges given a fixed ordering of the vertices? What is the maximum number of edges in each type of layout? What is the maximum chromatic number of a graph admitting each type of layout? What is the computational complexity of recognising the graphs that admit each type of layout?

A comprehensive bibliography of all known references on these topics is included.

Introduction

We consider undirected, finite, simple graphs G with vertex set V (G) and edge set E (G) A vertex ordering of an n-vertex graph G is a bijection σ : V (G) → {1, 2, . . . , n}. We write v < σ w to mean that σ(v) < σ(w). Thus < σ is a total order on V (G). We say G (or V (G)) is ordered by < σ . At times, it will be convenient to express σ by the list (v 1 , v 2 , . . . , v n ), where σ(v i ) = i. These notions extend † Research supported by NSERC and FCAR.

1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France to subsets of vertices in the natural way. Suppose that V 1 ,V 2 , . . . ,V k are disjoint sets of vertices, such that each V i is ordered by < i . Then (V 1 ,V 2 , . . . ,V k ) denotes the vertex ordering σ such that v < σ w whenever v ∈ V i and w ∈ V j with i < j, or v ∈ V i , w ∈ V i , and v < i w. We write

V 1 < σ V 2 < σ • • • < σ V k .
In a vertex ordering σ of a graph G, let L(e) and R(e) denote the endpoints of each edge e ∈ E(G) such that L(e) < σ R(e). Consider two edges e, f ∈ E(G) with no common endpoint. There are the following three possibilities for the relative positions of the endpoints of e and f in σ. Without loss of generality L(e) < σ L( f ).

• e and f cross: L(e) < σ L( f ) < σ R(e) < σ R( f ).

• e and f nest and f is nested inside e: L(e) < σ L( f

) < σ R( f ) < σ R(e)
• e and f are disjoint: L(e) < σ R(e) < σ L( f

) < σ R( f )
Edges with a common endpoint do not cross, do not nest, and are not disjoint. A stack (respectively, queue, arch) in σ is a set of edges F ⊆ E(G) such that no two edges in F are crossing (respectively, nested, disjoint) in σ. Observe that when traversing σ, edges in a stack appear in LIFO order, and edges in a queue appear in FIFO order -hence the names.

A linear layout of a graph G is a pair (σ, {E 1 , E 2 , . . . , E k }) where σ is a vertex ordering of G, and {E 1 , E 2 , . . . , E k } is a partition of E(G). A k-stack (respectively, queue, arch) layout of G is a linear layout (σ, {E 1 , E 2 , . . . , E k }) such that each E ℓ is a stack (respectively, queue, arch) in σ. At times we write stack(e) = ℓ (or queue(e) = ℓ, arch(e) = ℓ) if e ∈ E ℓ . Layouts of K 6 of each type are illustrated in Figure 1. A graph admitting a k-stack (respectively, queue, arch) layout is called a k-stack (respectively, queue, arch) graph. The stack-number (respectively, queue-number, arch-number) of a graph G, denoted by sn(G) (respectively, qn(G), an(G)), is the minimum k such that G is a k-stack (respectively, k-queue, k-arch) graph.

Stack and queue layouts were respectively introduced by Ollmann [START_REF] Ollmann | On the book thicknesses of various graphs[END_REF] and Heath et al. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF][START_REF] Heath | Laying out graphs using queues[END_REF]. As far as we are aware, arch layouts have not previously been studied, although Dan Archdeacon ‡ suggests doing so.

Stack layouts are more commonly called book embeddings, and stack-number has been called bookthickness, fixed outer-thickness, and page-number. Applications of stack layouts include sorting permutations [START_REF] Even | Queues, stacks, and graphs[END_REF][START_REF] Harju | Forbidden subsequences and permutations sortable on two parallel stacks[END_REF][START_REF] Ordman | Permutations using stacks and queues[END_REF][START_REF] Pratt | Computing permutations with double-ended queues. Parallel stacks and parallel queues[END_REF][START_REF] Tarjan | Sorting using networks of queues and stacks[END_REF], fault tolerant VLSI design [START_REF] Chung | Embedding graphs in books: a layout problem with applications to VLSI design[END_REF][START_REF] Rosenberg | The DIOGENES approach to testable fault-tolerant arrays of processors[END_REF][START_REF] Rosenberg | Book embeddings and wafer-scale integration[END_REF][START_REF] Rosenberg | DIOGENES, circa[END_REF], complexity theory [START_REF] Galil | On 3-pushdown graphs with large separators[END_REF][START_REF] Galil | On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines[END_REF][START_REF] Kannan | Unraveling k-page graphs[END_REF], compact graph encodings [START_REF] Jacobson | Space-efficient static trees and graphs[END_REF][START_REF] Munro | Succinct representation of balanced parentheses and static trees[END_REF], compact routing tables [START_REF] Gavoille | Compact routing tables for graphs of bounded genus[END_REF], and graph drawing [START_REF] Biedl | Bounds for orthogonal 3-D graph drawing[END_REF][START_REF] Giacomo | Drawing planar graphs on a curve[END_REF][START_REF] Wood | Bounded degree book embeddings and three-dimensional orthogonal graph drawing[END_REF][START_REF] Wood | Degree constrained book embeddings[END_REF]. Numerous other aspects of stack layouts have been studied in the literature [START_REF] Bilski | Embedding graphs in books with prespecified order of vertices[END_REF][START_REF] Bilski | Optimum embedding of complete graphs in books[END_REF][START_REF] Blankenship | Drawing subdivisions of complete and complete bipartite graphs on books[END_REF][START_REF] Blankenship | Book embeddings of graphs and minor-closed classes[END_REF][START_REF] Buss | On the pagenumber of planar graphs[END_REF][START_REF] Buss | Vertex types in book-embeddings[END_REF][START_REF] Chen | A study of typenumber in book-embedding[END_REF][START_REF] Cottafava And O. D'antona | Book-thickness and book-coarseness of graphs[END_REF], ‡ http://www.emba.uvm.edu/˜archdeac/problems/stackq.htm [START_REF] Damiani | An upper bound to the crossing number of the complete graph drawn on the pages of a book[END_REF][START_REF] Dean | Relations among embedding parameters for graphs[END_REF][START_REF] Endo | The pagenumber of toroidal graphs is at most seven[END_REF][START_REF] Enomoto | On the pagenumber of complete bipartite graphs[END_REF][START_REF] Eppstein | Separating geometric thickness from book thickness[END_REF][START_REF] Sun | The typenumber of trees[END_REF][START_REF] Games | Optimal book embeddings of the FFT, Benes, and barrel shifter networks[END_REF][START_REF] Heath | The pagenumber of k-trees is O(k)[END_REF][START_REF] Hasunuma | Embedding de Bruijn, Kautz and shuffle-exchange networks in books[END_REF][START_REF] Heath | Embedding planar graphs in seven pages[END_REF][START_REF] Heath | Embedding outerplanar graphs in small books[END_REF][START_REF] Heath | The pagenumber of genus g graphs is O(g)[END_REF][START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF][START_REF] Heath | Laying out graphs using queues[END_REF][START_REF] Hochberg | Optimal one-page tree embeddings in linear time[END_REF][START_REF] Ishiwata | Book presentation of the complete n-partite graphs[END_REF][START_REF] Kainen | The book thickness of a graph. II[END_REF][START_REF] Kainen | Book embeddings of graphs and a theorem of Whitney[END_REF][START_REF] Kapoor | A genetic algorithm for finding the pagenumber of interconnection networks[END_REF][START_REF] Keys | Graphs critical for maximal bookthickness[END_REF][START_REF] Kobayashi | Book presentation and local unknottedness of spatial graphs[END_REF][START_REF] Lin | Cutwidth and related parameters of graphs[END_REF][START_REF] Malitz | Genus g graphs have pagenumber O( √ g)[END_REF][START_REF] Malitz | Graphs with E edges have pagenumber O( √ E)[END_REF][START_REF] Masuyama | Deciding whether graph G has page number one is in NC[END_REF][START_REF] Moran | One-page book embedding under vertex-neighborhood constraints[END_REF][START_REF] Moran | Two-page book embedding of trees under vertex-neighborhood constraints[END_REF][START_REF] Muder | Pagenumber of complete bipartite graphs[END_REF][START_REF] Obreni Ć | Embedding de Bruijn and shuffle-exchange graphs in five pages[END_REF][START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF][START_REF] Madhavan | Stack and queue number of 2-trees[END_REF][START_REF] Shahrokhi | On crossing sets, disjoint sets, and pagenumber[END_REF][START_REF] Shahrokhi | The book crossing number of a graph[END_REF][START_REF] St Öhr | A trade-off between page number and page width of book embeddings of graphs[END_REF][START_REF] St Öhr | Optimal book embeddings in depth-k K n -cylinders[END_REF][START_REF] St Öhr | The pagewidth of trivalent planar graphs[END_REF][START_REF] Swaminathan | The pagenumber of the class of bandwidth-k graphs is k -1[END_REF][START_REF] Togasaki | Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs[END_REF][START_REF] Wang | Some results on embedding grid graphs in books[END_REF][START_REF] Yannakakis | Embedding planar graphs in four pages[END_REF]. Stack layouts of directed graphs [START_REF] Giacomo | Book embeddings and point-set embeddings of series-parallel digraphs[END_REF][START_REF] Hasunuma | Embedding iterated line digraphs in books[END_REF][START_REF] Heath | Stack and queue layouts of directed acyclic graphs[END_REF][START_REF] Heath | Stack and queue layouts of directed acyclic graphs[END_REF] and posets [START_REF] Rival | Series-parallel planar ordered sets have pagenumber two[END_REF][START_REF] Alzohairi | The pagenumber of spherical lattices is unbounded[END_REF][START_REF] Heath | Stack and queue layouts of posets[END_REF][START_REF] Le Tu | A planar poset which requires four pages[END_REF][START_REF] Nowakowski | Ordered sets, pagenumbers and planarity[END_REF][START_REF] Sysło | Bounds to the page number of partially ordered sets[END_REF] have also been investigated.

Applications of queue layouts include sorting permutations [START_REF] Even | Queues, stacks, and graphs[END_REF][START_REF] Imamiya | Generating and sorting permutations using restricted-deques[END_REF][START_REF] Ordman | Permutations using stacks and queues[END_REF][START_REF] Pratt | Computing permutations with double-ended queues. Parallel stacks and parallel queues[END_REF][START_REF] Tarjan | Sorting using networks of queues and stacks[END_REF], parallel process scheduling [START_REF] Bhatt | Scheduling tree-dags using FIFO queues: A control-memory trade-off[END_REF], matrix computations [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF], and graph drawing [START_REF] Giacomo | Track drawings of graphs with constant queue number[END_REF][START_REF] Dujmovi Ć | Layout of graphs with bounded tree-width[END_REF][START_REF] Wood | Queue layouts, tree-width, and three-dimensional graph drawing[END_REF]. Other aspects of queue layouts have been studied in the literature [START_REF] Wood | Stacks, queues and tracks: Layouts of graph subdivisions[END_REF][START_REF] Wood | Track layouts of graphs[END_REF][START_REF] Ganley | Stack and queue layouts of Halin graphs[END_REF][START_REF] Madhavan | Stack and queue number of 2-trees[END_REF][START_REF] Shahrokhi | On crossing sets, disjoint sets, and pagenumber[END_REF]. Queue layouts of directed graphs [START_REF] Heath | Stack and queue layouts of directed acyclic graphs[END_REF][START_REF] Heath | Stack and queue layouts of directed acyclic graphs[END_REF] and posets [START_REF] Heath | Stack and queue layouts of posets[END_REF] have also been investigated.

Table 1 summarises some of the known bounds on the stack-number and queue-number of various classes of graphs. A blank entry indicates that a more general result provides the best known bound. Consider a vertex ordering σ = (v 1 , v 2 , . . . , v n ) of a graph G. For each edge v i v j ∈ E(G), let the width of v i v j in σ be |i -j|, and let the midpoint of v i v j be 1 2 (i + j). The band-width of σ is the maximum width of an edge of G in σ. The band-width of G, denoted by bw(G), is the minimum band-width over all vertex orderings of G. Consider the two fundamental observations:

Observation 1 ([59]

). Edges whose widths differ by at most one are not nested.

Observation 2. Distinct edges with the same midpoint are nested.

Observation 1 was made by Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF]. Remarkably, Observation 2 seems to have gone unnoticed in the literature on queue layouts.

Our main result is a characterisation of k-arch graphs, given in Section 3. We also survey various fundamental questions regarding each type of layout, and in the case of queue layouts, provide new and simple proofs (based on Observation 2) of a number of existing results. In Section 2 we consider how to partition the edges given a fixed vertex ordering. In Section 4 we analyse the computational complexity of recognising the graphs that admit each type of layout. In Section 5 we consider the extremal questions: what is the maximum number of edges in each type of layout, and what is the maximum chromatic number of a graph admitting each type of layout? Section 6 considers how to produce a queue layout of a graph G given queue layouts of the biconnected components of G. In Section 7 we give a simple proof of the known result that queue-number is in O( √ m).

Fixed Vertex Orderings

Consider the problem of assigning the edges of a graph G to the minimum number of stacks given a fixed vertex ordering σ of G. This problem is equivalent to colouring a circle graph with the minimum number of colours. (A circle graph is the intersection graph of a set of chords of a circle.) As illustrated in Figure 2(a), a twist in σ is a matching

{v i w i ∈ E(G) : 1 ≤ i ≤ k} such that v 1 < σ v 2 < σ • • • < σ v k < σ w 1 < σ w 2 < σ • • • < σ w k .
A vertex ordering with a k-edge twist needs at least k stacks, since each edge of a twist must be in a distinct stack. However, the converse is not true. There exist vertex orderings with no (k + 1)-edge twist that require Ω(k log k) stacks [START_REF] Kostochka | Covering and coloring polygon-circle graphs[END_REF]. Moreover, it is N P -complete to test if a fixed vertex ordering of a graph admits a k-stack layout [43] § . On the other hand, Kostochka [START_REF] Kostochka | Upper bounds on the chromatic number of graphs[END_REF] proved that a vertex ordering with no 3-edge twist admits a 5-stack layout, and Ageev [START_REF] Ageev | A triangle-free circle graph with chromatic number 5[END_REF] proved that 5-stacks are sometimes necessary in this case. In general, Kostochka and Kratochvíl [START_REF] Kostochka | Covering and coloring polygon-circle graphs[END_REF] proved that a vertex ordering with no (k + 1)-edge twist admits a 2 k+6 -stack layout ¶ , thus improving on previous bounds by Gyárfás [START_REF] Gy | On the chromatic number of multiple interval graphs and overlap graphs[END_REF][START_REF] Gy | On the chromatic number of multiple interval graphs and overlap graphs[END_REF]. Hence the stack-number of a graph G is bounded by the minimum, taken over all vertex orderings σ of G, of the maximum number of edges in a twist in σ. Now consider the analogous problem for queue layouts: assign the edges of a graph G to the minimum number of queues given a fixed vertex ordering σ of G. As illustrated in Figure 2

v 1 v 2 v 3 v 4 v 5 w 5 w 4 w 3 w 2 w 1 (a) v 1 v 2 v 3 v 4 v 5 w 1 w 2 w 3 w 4 w 5 (b) v 1 v 2 v 3 v 4 v 5 w 5 w 4 w 3 w 2 w 1 (c)
(b), a rainbow in σ is a matching {v i w i ∈ E(G) : 1 ≤ i ≤ k} such that v 1 < σ v 2 < σ • • • < σ v k < σ w k < σ w k-1 < σ • • • < σ w 1 .
The rainbow {v i w i : 2 ≤ i ≤ k} is said to be inside v 1 w 1 . We now give a simple proof of a result by Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF]. § Unger [START_REF] Unger | On the k-colouring of circle-graphs[END_REF][START_REF] Unger | The complexity of colouring circle graphs[END_REF] claimed that it is N P -complete to determine whether a given vertex ordering of a graph G admits a 4-stack layout, and that there is a O(n log n) time algorithm in the case of 3-stack layouts. Crucial details are missing from these papers. ¶ Unger [START_REF] Unger | On the k-colouring of circle-graphs[END_REF] claimed without proof that a vertex ordering with no (k + 1)-edge twist admits a 2k-stack layout. This claim is refuted by Ageev [START_REF] Ageev | A triangle-free circle graph with chromatic number 5[END_REF] in the case of k = 2.

Lemma 1 ([59]). A vertex ordering of a graph G admits a k-queue layout of G if and only if it has no

(k + 1)-edge rainbow.

Proof. A k-queue layout has no (k + 1)-edge rainbow since each edge of a rainbow must be in a distinct queue. Conversely, suppose we have a vertex ordering with no (k + 1)-edge rainbow. For every edge vw ∈ E(G), let queue(vw) be the maximum number of edges in a rainbow inside vw plus one. If vw is nested inside xy then queue(vw) < queue(xy). Hence we have a valid queue assignment. The number of queues is at most k.

Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] presented a O(m log log n) time algorithm that, given a fixed vertex ordering of a graph G with no (k + 1)-edge rainbow, assigns the edges of G to k queues. Lemma 1 implies that the queue-number of G is the minimum, taken over all vertex orderings σ of G, of the maximum number of edges in a rainbow in σ. Hence determining the queue-number of a graph is no more than the question of finding the right vertex ordering. Now consider the problem of assigning the edges of a graph G to the minimum number of arches given a fixed vertex ordering σ of G. As illustrated in Figure 2 Lemma 2 implies that the arch-number of a graph G is the minimum, taken over all vertex orderings σ of G, of the maximum number of edges in a necklace in σ. For example, an(K n ) = ⌊ n 2 ⌋. Now consider the following algorithm.

(c), a necklace in σ is a matching {v i w i : 1 ≤ i ≤ k} such that v 1 < σ w 1 < σ v 2 < σ w 2 < σ • • • < σ v k < σ w k . The necklace {v i w i : 1 ≤ i ≤ k -1} is said to precede the edge v k w k . Lemma 2. A vertex
Algorithm ASSIGNARCHES(G, σ) 1. let k 0 = 0 2. let (v 1 , v 2 , . . . , v n ) = σ 3. for i = 1, 2, . . . , n do 4.
for each edge

v i v j ∈ E(G) with i < j, let arch(v i v j ) = 1 + k i-1 5. let k i = k i-1 6. for each edge v i v j ∈ E(G) with j < i, let k i = max{k i , 1 + k j-1 } Lemma 3.
Given a vertex ordering σ of an n-vertex m-edge graph G, the algorithm ASSIGNARCHES(G, σ) assigns the edges of G to the minimum number of arches with respect to σ in O(n + m) time.

Proof. It is easily verified that the algorithm maintains the invariant that k i is the maximum number of edges in a necklace in the vertex ordering (v 1 , v 2 , . . . , v i ). Hence, for every edge vw ∈ E(G), arch(vw) is the maximum number of edges in a necklace that precedes vw plus one. Thus, as in Lemma 2, we have an assignment of the edges to the minimum number of arches.

The proofs of Lemmata 1 and 2 hide an application of the easy half of Dilworth's Theorem [START_REF] Dilworth | A decomposition theorem for partially ordered sets[END_REF] for partitioning a poset into k antichains, where k is the maximum size of a chain. In Lemma 1, e ≺ f if e is nested inside f , and in Lemma 2, e ≺ f if R(e) < σ L( f ). The problem of assigning edges to queues in a fixed vertex ordering is equivalent to colouring a permutation graph [START_REF] Miller | Partially ordered sets[END_REF]. Assigning edges to arches corresponds to partitioning an interval graph into cliques.

Arch Layout Characterisation

A graph G is almost k-colourable if there is a set S ⊆ V (G) of at most k -1 vertices such that G \ S is k-colourable. Theorem 1. A graph G has arch-number an(G) ≤ k if and only if G is almost (k + 1)-colourable. Proof. (⇐=) First suppose that G is almost (k + 1)-colourable. Then there is a set of vertices S = {x 1 , x 2 , . . . , x k } ⊆ V (G) such that G \ S is (k + 1)-colourable. Let V 1 ,V 2 , .
. . ,V k+1 be the colour classes in such a colouring. Let σ be a vertex ordering such that

V 1 < σ x 1 < σ V 2 < σ x 2 < σ • • • < σ V k < σ x k < σ V k+1 .
Clearly every necklace in σ has at most k edges. By Lemma 2, σ admits a k-arch layout of G.

(=⇒) The proof is by induction on k. For k = 0, the result is trivial. Suppose that an(G) ≤ k -1 implies G is almost k-colourable. Let G be a k-arch graph with vertex ordering σ = (v 1 , v 2 , . . . , v n ).

Let V ≤p = (v 1 , v 2 , . . . , v p ) and V >p = (v p+1 , v p+2 , . . . , v n ). It is simple to verify that the maximum number of edges in a necklace in V ≤p is equal to, or one less than, the maximum number of edges in a necklace in V ≤p+1 , for all 1 ≤ p ≤ n -1. Consequently, there is maximum number i such that V ≤i admits a (k -1)-arch layout. By the maximality of i, V ≤i+1 contains a k-edge necklace. Therefore V >i+1 is an independent set of G, otherwise an edge of G[V >i+1 ] together with the k-edge necklace of V ≤i+1 would comprise a (k + 1)-edge necklace. Therefore, G[V >i ] is a forest, at most one component of which is a star centred at v i+1 , and the remaining components are isolated vertices.

By the induction hypothesis there is a set

S k-1 of k -1 vertices such that G[V ≤i \ S k-1 ] is k-colourable. Since G[V >i ] is a star centred at v i+1 with some isolated vertices, it follows that for S k = S k-1 ∪ {v i+1 }, the induced subgraph G[V \ S k ] is (k + 1)-colourable. Therefore, G is almost (k + 1)-colourable.
Arch-number and chromatic number are tied in the following strong sense.

Theorem 2. The arch-number of every graph G satisfies:

an(G) + 1 ≤ χ(G) ≤ 2 an(G) + 1.
Proof. By Theorem 1, G is almost (an(G) + 1)-colourable. Thus it is (2 an(G) + 1)-colourable. Conversely, G is almost χ(G)-colourable, and an(G) ≤ χ(G) -1 by Theorem 1.

Theorem 2 implies that any graph family that has bounded chromatic-number also has bounded archnumber. Examples include graphs with bounded maximum degree, graphs with bounded tree-width, and graphs with an excluded clique minor, and so on. Proof. The Four Colour Theorem and Theorem 1 imply that all planar graphs have arch-number at most three. Any planar graph G containing three vertex-disjoint K 4 subgraphs is not almost 3-colourable. By Theorem 1, an(G) = 3.

Computational Complexity

The 1-stack graphs are precisely the outerplanar graphs [START_REF] Bernhart | The book thickness of a graph[END_REF], and thus can be recognised in O(n) time [START_REF] Mitchell | Linear algorithms to recognize outerplanar and maximal outerplanar graphs[END_REF]. 2-stack graphs are characterised as the subgraphs of planar Hamiltonian graphs [START_REF] Bernhart | The book thickness of a graph[END_REF], which implies that it is N P -complete to test if sn(G) ≤ 2 [START_REF] Wigderson | The complexity of the Hamiltonian circuit problem for maximal planar graphs[END_REF]. Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] characterised 1-queue graphs as the 'arched levelled' planar graphs, and proved that it is N P -complete to recognise such graphs.

Lemma 5. There is a O(n(n + m)) time algorithm to determine if a given n-vertex m-edge graph G has arch-number an(G) ≤ 1.

Proof. By Theorem 1, an(G) ≤ 1 if and only if there is a vertex v such that G \ v is bipartite. The result follows since bipartiteness can be tested in O(n + m) time by breadth-first search.

Note that almost bipartite graphs have been studied by Prömel et al. [START_REF] Pr Ömel | A note on triangle-free and bipartite graphs[END_REF].

Open Problem 1. Is there a sub-quadratic time algorithm for determining whether an(G) ≤ 1?

Theorem 3. Given a graph G and an integer k ≥ 2, it is N P -complete to determine if G has arch-number

an(G) ≤ k.
Proof. The problem is clearly in N P . The remainder of the proof is a reduction from the graph kcolourability problem: given a graph G and an integer k, is χ(G) ≤ k? Let G ′ be the graph comprised of k components each isomorphic to G. We claim that χ(G) ≤ k if and only if G ′ is almost k-colourable. The result will follow from Theorem 1 and since graph k-colourability is N P -complete [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

If G is k-colourable then so is G ′ , and thus G ′ is almost k-colourable. Conversely, if G ′ is almost k- colourable then there is a set S of at most k -1 vertices such that χ(G ′ \ S) ≤ k. Since |S| ≤ k -1, G ′ \ S contains a component isomorphic to G, and thus G is k-colourable.
The next result follows from the reduction in Theorem 3 and since it is N P -complete to determine if a 4-regular planar graph is 3-colourable [START_REF] Dailey | Uniqueness of colorability and colorability of planar 4-regular graphs are NPcomplete[END_REF][START_REF] Garey | Some simplified NP-complete graph problems[END_REF].

Corollary 1. It is N P -complete to determine if a given 4-regular planar graph G has arch-number

an(G) ≤ 2.

Extremal Questions

In this section we consider the extremal questions:

• what is the maximum number of edges in a particular type of layout?

• what is the maximum chromatic number of a graph admitting a particular type of layout?

The answer to the first question for stack layouts has been observed by many authors.

Lemma 6 ([4, 18, 69]). Every s-stack n-vertex graph has at most (s + 1)n -3s edges, and this bound is tight for all even n ≥ 4 and all

1 ≤ s ≤ n 2 .
Proof. It will be beneficial to view the vertex ordering (v 0 , v 1 , . . . , v n-1 ) as circular. Each edge v i v (i+1) mod n is said to be a boundary edge. Each stack has at most 2n -3 edges, since a 1-stack graph is outerplanar. Every boundary edge can be assigned to any stack. Thus there are at most n -3 non-boundary edges in each stack, and at most n boundary edges, giving a total of at most s(n -3) + n = (s + 1)n -3s edges. Now for the lower bound. As illustrated in Figure 3(a), for each 0 ≤ i ≤ s -1, let

E i = {v j v k : ⌈ 1 2 ( j + k)⌉ ≡ i (mod n 2 )} .
Then E 0 , E 1 , . . . , E s-1 are edge-disjoint paths, each of which is a stack of n -3 non-boundary edges.

Adding the boundary edges to any stack, we obtain an s-stack graph with the desired number of edges. Note that with s = n 2 , we obtain an n 2 -stack layout of K n . As observed by Bernhart and Kainen [START_REF] Bernhart | The book thickness of a graph[END_REF], Lemma 6 implies that (every induced subgraph of) an s-stack graph has a vertex of degree less than 2s + 2, and is therefore vertex (2s + 2)-colourable by the minimumdegree-greedy algorithm. This result can be improved for small s. 1-stack graphs are outerplanar, which are 3-colourable, and 2-stack graphs are planar, which are 4-colourable.

v 11 v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 (a) (b) v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10
Open Problem 2. What is the maximum chromatic number χ of the s-stack graphs? In general, χ ∈ {2s, 2s + 1, 2s + 2} since χ(K n ) = 2 sn(K n ) for even n. Now consider the maximum number of edges in a k-queue graph. The answer for k = 1 was given by Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] and Pemmaraju [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF]. We now give a simple proof for this case. The proof by Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] is based on the characterisation of 1-queue graphs as the arched levelled planar graphs. The proof by Pemmaraju [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF] is based on a relationship between queue layouts and 'staircase covers of matrices'. The observant reader will notice parallels between the following proof and that of the lower bound on the volume of three-dimensional drawings due to Bose et al. [START_REF] Bose | The maximum number of edges in a three-dimensional grid-drawing[END_REF].

Lemma 7.

A queue in a graph with n vertices has at most 2n -3 edges.

Proof. By Observation 2, distinct edges with the same midpoint are nested. Since every midpoint is in

{ 3 2 , 2, 2 1 2 , . . . , n -1 2 }
, there are at most 2n -3 midpoints. The result follows since no two edges in a queue are nested.

An immediate generalisation of Lemma 7 is that every k-queue graph has at most k(2n -3) edges [START_REF] Heath | Laying out graphs using queues[END_REF]. The following improved upper bound was first discovered by Pemmaraju [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF] with a longer proof. That this bound is tight for all values of n and k is new. Lemma 8. Every n-vertex graph with queue-number k has at most 2knk(2k + 1) edges. For every k and n ≥ 2k, there exists an n-vertex graph with queue-number k and 2knk(2k + 1) edges Proof. First we prove the upper bound. Note that n ≥ 2k, since by Lemma 1, the corresponding vertex ordering has a k-edge rainbow. By Observation 2, distinct edges with the same midpoint are nested. Since at most k edges are pairwise nested in a k-queue layout, at most k edges have the same midpoint. Moreover, for all integers 1 ≤ i ≤ k, at most i -1 edges have a midpoint of i, and at most i -1 edges have a midpoint of i -1 2 . At the other end of the vertex ordering, for all integers 1 ≤ i ≤ k -1, at most i edges have a midpoint of ni, and at most i edges have a midpoint of ni + 1 2 . Since n ≥ 2k we are not double counting here. It follows that the number of edges is at most

2 k ∑ i=1 (i -1) + (2n -4k + 1)k + 2 k-1 ∑ i=1 i = 2kn -k(2k + 1) .
We now prove the lower bound. As illustrated in Figure 3(b), let P s n denote the s th power of the n-vertex path P n . That is, P s n has V (P s n ) = {v 1 , v 2 , . . . , v n } and E(P s n ) = {v i v j : |i-j| ≤ s}. Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] proved that qn(P 2k n ) = k for n ≥ 2k, where for each 1 ≤ ℓ ≤ k, the set of edges {v i v j : 2ℓ -1 ≤ |i -j| ≤ 2ℓ} is a queue in the vertex ordering (v 1 , v 2 , . . . , v n ). (This is Observation 1.) Swaminathan et al. [START_REF] Swaminathan | The pagenumber of the class of bandwidth-k graphs is k -1[END_REF] proved that P 2k n has 2knk(2k + 1) edges. (P s n appears in [START_REF] Heath | Laying out graphs using queues[END_REF][START_REF] Swaminathan | The pagenumber of the class of bandwidth-k graphs is k -1[END_REF] with regard to the relationship between band-width and queue-and stack-number, respectively.) Lemma 8 implies that (every induced subgraph of) a k-queue graph has a vertex of degree less than 4k, and is therefore 4k-colourable by the minimum-degree-greedy algorithm.

Open Problem 3. What is the maximum chromatic number χ of a k-queue graph? We know that χ ∈ {2k + 1, 2k + 2, . . . , 4k} since χ(K n ) = 2 qn(K n ) + 1 for odd n (by Lemma 1). Note that the extremal example P 2k n in Lemma 8 also has chromatic number 2k + 1. We now prove that the lower bound in Open Problem 3 is attainable in the case of k = 1. Lemma 9. Every 1-queue graph G is 3-colourable.

Proof. Let σ be the vertex ordering in a 1-queue layout of a graph G. Partition the vertices into independent sets V 1 ,V 2 , . . . ,V k such that σ = (V 1 ,V 2 , . . . ,V k ), and for all 1 ≤ i ≤ k -1, there exists an edge in G[V i ∪ V i+1 ]. Such a partition can be computed by starting with each vertex in its own set, and repeatedly merging consecutive sets that have no edge between them. For all s ≥ 3, there is no edge in any G[V i ∪ V i+s ], as otherwise it would be nested with an edge in G[V i+1 ∪ V i+2 ]. Thus for each 0 ≤ j ≤ 2, W j = S {V i : i ≡ j (mod 3)} is an independent set, and {W 0 ,W 1 ,W 2 } is a 3-colouring of G.

The next lemma shows that, in terms of the maximum number of edges, arch layouts behave very differently from stack and queue layouts. Even 1-arch layouts may have a quadratic number of edges.

Lemma 10. The maximum number of edges in a k-arch layout with n vertices is at most

kn(n + 2) -k(2k + 1) 2(k + 1) , (1)
which is attainable whenever k + 1 divides nk.

Proof. Let G be a k-arch graph with n vertices and the maximum number of edges. By Theorem 1, G is almost (k + 1)-colourable. That is, there is a set S ⊆ V (G) of at most k vertices such that G \ S is (k + 1)colourable. Each vertex v ∈ S is adjacent to every other vertex in G, as otherwise G is not edge-maximal. The (k + 1)-colourable graph with the maximum number of edges is the complete (k + 1)-partite graph with partitions whose sizes are as equal as possible. Thus G \ S is this graph. When the partitions have the same size we obtain the most edges. Here, G \ S is obtained from K n-k by removing k + 1 vertex-disjoint copies of the complete graph on (nk)/(k + 1) vertices. Thus the number of edges is

n 2 -(k + 1) (n -k)/(k + 1) 2 ,
which is easily seen to reduce to (1).

Biconnected Components

Clearly the stack-number (respectively, queue-number) of a graph is at most the maximum stack-number (queue-number) of its connected components. Bernhart and Kainen [START_REF] Bernhart | The book thickness of a graph[END_REF] proved that the stack-number of a graph is at most the maximum stack-number of its maximal biconnected components (blocks). We now prove an analogous result for queue layouts.

Lemma 11. Every graph G has queue-number

qn(G) ≤ 1 + max{qn(B) : B is a block of G}.
Proof. Clearly we can assume that G is connected. Let T be the block-cut-tree of G. That is, there is a node in T for each block and for each cut-vertex of G. Two nodes of T are adjacent if and only if one corresponds to a block B, and the other corresponds to a cut-vertex v, and v ∈ V (B). T is a tree, as otherwise a cycle in T would correspond to a single block in G. Root T at a node r corresponding to an arbitrary block R of G. Consider a cut-vertex v of G. The block containing v that corresponds to the parent node of v in T is called the parent block of v. The other blocks containing v are called child blocks of v.

There are no nested edges in any breadth-first vertex ordering of T [START_REF] Chung | Embedding graphs in books: a layout problem with applications to VLSI design[END_REF]. Let σ be a breadth-first vertex ordering of T starting at R, such that cut-nodes of T with a common parent block B are ordered in σ according to their order in the given queue layout of B. Now create a vertex ordering π of G from σ, as illustrated in Figure 4. Specifically, delete from σ all the nodes corresponding to cut vertices of G; replace r by the given queue layout of R; and for each block B = R whose parent node in T corresponds to a cut vertex v of G, replace the node in σ that corresponds to B by the given queue layout of B \ v.

An edge of G that is incident to a cut-vertex v and is contained in a child block of v is called a jump edge. According to the above algorithm, a cut-vertex of G is positioned within its parent block in π. Thus, if two non-jump edges are nested, then they are in the same block B, and are nested in the given queue layout of B. Since the blocks are separated, non-jump edges can inherit their queue assignment from the queue layout of their block.

Since the edges of T are not nested, and by the choice of ordering for cut-nodes of T with a common parent block, jump edges are not nested, and thus can form one new queue. Thus the total number of queues is as claimed.

A Bound on the Queue-Number

Malitz [START_REF] Malitz | Graphs with E edges have pagenumber O( √ E)[END_REF] proved that the stack-number of an m-edge graph is O( √ m). The exact bound is in fact 72 √ m. Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] (see also Shahrokhi and Shi [95]) observed that an analogous method proves that queue-number is O( √ m). We now establish this result using a simplified version of the argument of Malitz [START_REF] Malitz | Graphs with E edges have pagenumber O( √ E)[END_REF] and with an improved constant. (1)

• n 2k

(2)

• 2 k k!(n -2k)! n! (3)
, where:

(1) is an upper bound on the number of k-edge matchings M,

(2) is the number of vertex positions in σ for M, and

(3) is the probability that M with fixed vertex positions is a rainbow.

Thus

P{A k } ≤ m k k! • n! (2k)!(n -2k)! • 2 k k!(n -2k)! n! = ( 2m

  The number of vertices and edges of G are respectively denoted by n = |V (G)| and m = |E(G)|. The subgraph of G induced by a set of vertices S⊆ V (G) is denoted by G[S]. G \ S denotes G[V (G) \ S], and G \ v denotes G \ {v} for each vertex v ∈ V (G).

Fig. 1 :

 1 Fig. 1: Layouts of K 6 : (a) 3-stack, (b) 3-queue, (c) 3-arch.

Fig. 2 :

 2 Fig. 2: (a) 5-edge twist, (b) 5-edge rainbow, (c) 5-edge necklace.

Lemma 4 .

 4 Planar graphs have arch-number at most three and this bound is tight.

Fig. 3 :

 3 Fig. 3: Edge-maximal layouts: (a) 2-stack, (b) 2-queue.

Fig. 4 :

 4 Fig. 4: Constructing a queue layout of G from queue layouts of the biconnected components of G.

Theorem 4 .

 4 Every graph G with m edges has queue-number qn(G) < e √ m, where e is the base of the natural logarithm. Proof. Let n = |V (G)|. Let σ be a random vertex ordering of G. For all positive integers k, let A k be the event that there exists a k-edge rainbow in σ. Then the probability Pr{A k } ≤ m k

e 2 m 2k 2 k.

 2 ) k (2k)! . By Stirling's formula, P{A k } < Let k 0 = ⌈e √ m⌉. Thus, P{A k 0 } > 1 -1 2 ⌈e √ m⌉ > 0. That is,with positive probability a random vertex ordering has no k 0 -edge rainbow. Hence there exists a vertex ordering with no k 0 -edge rainbow. By Lemma 1, G has a queue layout with k 0 -1 < e √ m queues.