A Catapano
email: anita.catapano@ipb.fr

M Montemurro
email: marco.montemurro@ensam.eu

OPTIMAL DESIGN OF SANDWICH PLATES WITH HONEYCOMB CORE

Keywords: Honeycomb, homogenisation, optimisation, sandwich panels, genetic algorithm

This work deals with the problem of the optimum design of a sandwich structure composed of two laminated skins and a honeycomb core. The goal is to propose a numerical optimisation procedure that does not make any simplifying hypothesis in order to obtain a true global optimal solution for the considered problem. In order to face the design of the sandwich structure at both meso and macro scales, we use a two-level optimisation strategy. At the first level, we determine the optimum geometry of the unit cell together with the material and geometric parameters of the laminated skins, while at the second level we determine the optimal skins lay-up giving the geometrical and material parameters issued from the first level. We will illustrate the application of our strategy to the least-weight design of a sandwich plate submitted to several constraints: on the first buckling load, on the positivedefiniteness of the stiffness tensor of the core, on the ratio between skins and core thickness and on the admissible moduli for the laminated skins.

1-Introduction

One of the most important challenges for automotive, naval and aerospace industries is the reduction of the weight of structures. Due to their high stiffness-to-weight ratio, sandwich structures are widely used in several fields: aviation, automotive, naval, construction, industry, and so on. Their application, in fact, ranges from the most performing structures such as aircraft wings, helicopters rotor blades, racing yachts keels to home furnishings.

The main characteristic of a sandwich structure concerns the presence of a low-density cellular solid, i.e. the core, between two stiffer thin plates, that increases the geometric moment of inertia of the plate with a few increment of weight. We can identify, in addition, several types of sandwich structures according to the geometry and shape of the core: honeycomb, solid, foam, corrugated, truss, web cores, and so on. The most important feature of the core is the relative density (ratio between the density of the cellular material and that of the material from which the cells walls are made) that can generally vary from 0.001 to 0.4, see [START_REF] Gibson | Cellular solids -Structure and properties[END_REF]. Almost any material can be used to build a cellular solid: polymers, metals, ceramics, composites and so on. Sandwich panels, in aircraft applications, are composed by glass or carbon-fibre composite skins separated by aluminium or resin honeycombs, or by polymer foams. In particular, the honeycomb cell size can be chosen to provide cores with different stiffness and density properties. The result is a panel with very high bending stiffness-to-weight and strength-toweight ratios. A review on sandwich structures and their applications can be found in [START_REF] Gibson | Cellular solids -Structure and properties[END_REF][START_REF] Vautrin | Mechanics of sandwich structures[END_REF][START_REF] Vinson | The behavior of sandwich srtuctures of isotropic and composite materials[END_REF].

The optimal design of sandwich structures is much more cumbersome than that of a classical monolithic structure. The difficulties increase when the sandwich structure is made of composite skins and a honeycomb core. In this case, we have to face, into the same design process, both the difficulty of designing a laminated plate (concerning the skins) and the difficulty of designing a complex 3D cellular continuum such as the honeycomb core. Therefore, the engineers always use some simplifying assumptions or rules to obtain, in an easier and faster way, a solution. For example, in [A1, HA1] the optimal design of a sandwich plate is addressed determining exclusively the optimum thickness of both the core and the skins, keeping constant the rest of geometric and material parameters describing their behaviour.

The problem of designing a sandwich panel can be formulated as an optimisation problem. However, unlike what is usually done in literature, our objective is twofold: on one hand, we want to formulate and solve such a problem on different scales and on the other hand, we want to include within the design process all the possible parameters defining the structure (at each scale) as optimisation variables. Therefore, in the framework of the design of a sandwich panel with honeycomb core and composite skins, we will consider, as optimisation variables, both their geometric and material constitutive parameters at each scale.

To this purpose, we propose a very general design strategy that consists in a numerical optimisation procedure that we set free from any simplifying hypothesis to obtain a true optimal configuration of the system. The design process that we propose is not submitted to restrictions: any parameter characterising our structure is an optimisation variable (thickness of the core, number of plies of skins, plies orientations, geometry of the unit cell).

In order to deal with the design problem of the sandwich plate at both meso and macro scales, we used a two-level optimisation strategy. At the first level we determine the optimum geometry of the unit cell (core meso-scale) together with the material and geometric parameters of the laminated skins (at this level the laminate representing each skin is modelled as an equivalent homogeneous anisotropic plate whose behaviour at the macro-scale is described in terms of the laminate polar parameters, see [V4]). At the second level of the strategy, we determine the optimal skins lay-up (the skin mesoscale) that satisfies the optimal combination of material and geometrical parameters issued from the first level of the strategy. The whole strategy is based on the use of the polar formalism [V1, V2, V4] and on the Genetic Algorithm (GA) BIANCA [START_REF] Montemurro | Optimal Design of Advanced Engineering Modular Systems through a New Genetic Approach[END_REF][START_REF] Montemurro | A twolevel procedure for the global optimum design of composite modular structures -application to the design of an aircraft wing. Part 1: theoretical formulation[END_REF][START_REF] Montemurro | A twolevel procedure for the global optimum design of composite modular structures -application to the design of an aircraft wing. Part 2: numerical aspects and examples[END_REF] and it can be easily generalised to other problems.

The paper is organised as follows: the mechanical problem considered in the study as well as the two-level strategy are introduced in Section 2. The mathematical formulation of the first-level problem is detailed in Section 3 and the problem of determining a suitable laminate is formulated in Section 4. A concise description of the Finite Element (FE) model of the sandwich structure at both meso and macro scales is given in Section 5, while in Section 6 we show some numerical results to prove the effectiveness of the optimisation strategy. Finally, Section 7 ends the paper with some concluding remarks and perspectives.

2-Optimum design of sandwich panels with honeycomb core

-Problem description

The optimisation procedure presented in this work is applied to a sandwich plate composed by two laminated skins and a honeycomb core with hexagonal cells, see Fig. 1.

The skins are made of carbon-epoxy unidirectional orthotropic plies, while the honeycomb core is obtained from aluminium alloy foils whose material properties are listed in Table 1.

Concerning the honeycomb core, the basic classical assumptions used to evaluate its elastic response and, hence, to determine its effective material properties (at the macroscale) are:  linear, elastic behaviour for the material of the cell walls;

 perfect bonding for the wall-to-wall contact;

 buckling of the cell walls disregarded.

Concerning the mechanical behaviour (at the macro-scale) of the two laminated skins they are modelled as quasihomogeneous, fully orthotropic laminates, see Section 3. In addition, no simplifying hypotheses are made on the geometric and mechanical parameters of both the skins and the core, i.e. any parameter characterising our structure is an optimisation variable: geometry of the unit cell as well as number and orientation of the plies for the skins. Only avoiding the use of a priori assumptions one can hope to obtain the true global optimum for a given problem: this is a key-point in our approach.

Material properties of the aluminium

E [MPa]   [Kg/

-Description of the two-level strategy

The goal of our problem is the minimisation of the weight of the sandwich plate subject to mechanical constraints on the first buckling load, on the positive-definiteness of the stiffness tensor of the core and on the admissible moduli for the laminated skins together with geometrical constraints on the ratio between skins and core thickness. The optimisation strategy is articulated into two distinct problems as described here below.

First-level problem. The aim of this phase is the determination of the optimal geometry of the unit cell together with the material and geometric parameters of the laminated skins in order to minimise the weight of the entire structure. At this level the laminate representing each skin is modelled as an equivalent homogeneous anisotropic plate whose behaviour at the macro-scale is described in terms of the laminate polar parameters, see [START_REF] Vannucci | Plane anisotropy by the polar method[END_REF][START_REF] Montemurro | Optimal Design of Advanced Engineering Modular Systems through a New Genetic Approach[END_REF][START_REF] Montemurro | A twolevel procedure for the global optimum design of composite modular structures -application to the design of an aircraft wing. Part 1: theoretical formulation[END_REF], by means of the classical stiffness tensors A, B and D. It is worth noting that, concerning the model of the core, the first level of the strategy involves two different scales:

-the meso-scale wherein the core is modelled via the single unit cell characterised by its geometric variables;

-the macro-scale where the core is modelled as an homogeneous orthotropic solid whose mechanical response is described through the full set of elastic moduli that depend on the geometric parameters of the unit cell.

Therefore, the link between these two scales is represented by the homogenisation phase of the honeycomb core that leads us to represent the core, at the macro-scale level, as a homogeneous continuum characterised by its equivalent material properties, namely

, G , E , E , E c 12 c 3 c 2 c 1 c 23 c 13 c 12 c 23 c 13 , , , G , G   
. This last aspect has led us to search an accurate method to the material properties of the orthotropic core that will be assigned to the equivalent solid at the macro-scale.

Second-level problem. At the second level of the strategy, we have to determine the optimal skins lay-up (the skin mesoscale) that satisfies the optimal combination of their material and geometrical parameters issued from the first level of the strategy. The goal of this phase is, hence, to find at least one stacking sequence, for each skin, which has to be quasihomogeneous, fully orthotropic and has to meet the optimal polar parameters issued from the first step. At this level of the strategy, the design variables are the layers orientations.

3-Formulation of the first level problem

-Optimisation variables

In this phase, we have to determine the optimal values of the following parameters:

the thickness of both top and bottom skins, We also remark that at this level of the optimisation procedure, the thickness mm. This assumption responds to a technological constraint and, addition, the optimal value of these parameters will give us the optimal number of layers n to be used during the secondlevel problem.

Concerning the mechanical variables, we use the polar formalism, which gives a representation of any planar tensor by means of a complete set of tensor invariants. A great advantage in the design of anisotropic structures is that the polar parameters are directly linked to the different symmetries of the tensor, see [V1, V2, V4]. Using the polar formalism, the representation of the reduced stiffness tensor Q of the orthotropic lamina is:

1 0 K 0 xyxy 1 1 1 0 K yyxy 1 1 1 0 K 1 0 yyyy 1 1 1 0 K xxxy 1 0 K 1 0 xxyy 1 1 1 0 K 1 0 xxxx 4 cos R ) 1 ( T Q 2 sin R 2 4 sin R ) 1 ( Q 2 cos R 4 4 cos R ) 1 ( T 2 T Q 2 sin R 2 4 sin R ) 1 ( Q 4 cos R ) 1 ( T 2 T Q 2 cos R 4 4 cos R ) 1 ( T 2 T Q                                    (1) where 0 T , 1 T , 0 R , 1 R and
K are the polar tensor invariants. K is the shape orthotropy parameter (that can get the values 0 or 1), whilst 1  is the polar angle that gives the othotropy orientation with respect to the global frame {0; x,y,z}.

The constitutive law of a laminate in the framework of the Classical Laminate Plate Theory (CLPT) is:

                   χ ε D B B A M N (2)
where N and M are the tensors representing the membrane forces and the bending moments , respectively. ε and χ are the second-order tensors of in-plane strains and curvature of the laminate middle plane, whilst A, D and B are the fourthorder tensors of membrane, bending and coupling stiffness, respectively.

In addition, even the laminate stiffness tensors can be expressed through the polar formalism, see [V1]. Here we want to highlight that, for a laminate with identical plies, thanks to quasi-homogeneity assumption and to the polar formalism, we are able to reduce the number of polar parameters describing the mechanical response of the laminate, see [START_REF] Montemurro | A twolevel procedure for the global optimum design of composite modular structures -application to the design of an aircraft wing. Part 1: theoretical formulation[END_REF]. In fact, they reduce from 18 to only three for each skin: the anisotropic polar moduli, i.e.  . Moreover, in the formulation of the optimisation problem for the first level of the strategy, we have also to consider the geometric and feasibility constraints on the polar parameters ensuring, in this way, that the polar parameters issued from the optimisation correspond to a feasible laminate that will be designed during the second step of the strategy. For more details about these aspects, the reader is addressed to [V2].

              b b * A 1 b * A 1 b * A K 0 t t * A 1 t * A 1 t * A K 0 c 1 2 c h , , R , R ... ,... h , , R , R , h , l , l , t ,     x ( 3
)
The optimisation problem can now be formulated as follows:

          0 E E E E E E E E 2 0 E E 0 E E 0 E E 0 G 0 G 0 G 0 E 0 E 0 E 0 R x 1 R x 2 0 R x 1 R
                                                               x x x ref : subject to (4)
where W is the weight of the sandwich plate, while  is the first buckling load. ref  is the buckling load determined on a reference structure having the same in-plane dimensions and boundary conditions than those of the sandwich plate that will be optimised, while  is the maximum admissible aspect-ratio between the thickness of the core and each skin. Constraints 4 and 5 are geometrical and feasibility constraints imposed on the polar parameters of top and bottom skins. Finally, constraints from 6 to 15 are imposed in order to ensure the positive definiteness of the stiffness tensor of the core.

-Numerical procedure

Problem (4) is a non-linear, non-convex problem in terms of both geometrical and mechanical variables. The total number of design variables is 13, see Eq. (3), while the total number of optimisation constraints is 15.

For the resolution of problem (4) we used a numerical strategy, that makes use of the GA BIANCA [M1] coupled with a meso-scale FE model for the numerical homogenisation of the honeycomb core and a macro-scale FE model for the buckling analysis of the whole panel, see Fig 3.

As shown in Fig. 3, for each individual at each generation, we perform a numerical simulation for the evaluation of the effective material properties of the core and a subsequent numerical simulation for the evaluation of the first buckling load of the sandwich structure along with its weight. The meso-scale FE model uses the geometrical parameters of the unit cell, given by the GA BIANCA, in order to homogenise the honeycomb core and to determine its effective material properties. Afterwards, the macro-scale FE model uses the geometrical and mechanical design variables of the skins given by the GA BIANCA along with the effective material properties of the core to evaluate the first buckling load of the structure and its weight. Therefore, for these purposes the genetic algorithm BIANCA has been interfaced with the commercial FE code ANSYS ® . The GA BIANCA elaborates the results of the two FE analyses in order to execute the genetic operations. These operations are repeated until the GA BIANCA meets the user-defined convergence criterion.

The generic individual of the GA BIANCA represents a solution. The genotype of the generic individual, for the optimisation problem of the first level of the strategy, is characterised by only one chromosome composed of 13 genes representing, each one, a component of the vector of the design variables, see Eq. (3).

4-Formulation of the second level problem

The second-level problem concerns the lay-up design of top and bottom skins. Such a problem consists in determining a laminate stack satisfying the optimum values of both geometric and polar parameters issued from the first level of the strategy.

The problem of finding a laminate stacking sequence having a given elastic behaviour is rather cumbersome and difficult because the laminate properties depend upon a combination of powers of circular functions of the layers orientations, see [START_REF] Montemurro | A twolevel procedure for the global optimum design of composite modular structures -application to the design of an aircraft wing. Part 2: numerical aspects and examples[END_REF].

In the framework of the polar formalism, such a problem can be stated in the form of an unconstrained minimisation problem:

         r 1 i 2 i i f f I min δ δ δ (5)
where δ is the vector of the layer orientations, i.e. the design variables of this phase, while   δ 2 i f are quadratic functions in the space of polar parameters, each one representing a requirement to be satisfied, such as orthotropy, uncoupling and so on. It is worth noting that the function

    δ i f I
of Eq. ( 5) is convex in the space of the laminate polar parameters, though it is highly non-convex in the space of the plies orientations (the true design variables) whose minima are known a priori, i.e. they are zeroes of this function. For more details about the nature of the second-level problem, see [START_REF] Catapano | Stiffness and strength optimisation of the anisotropy distribution for laminated structures[END_REF][START_REF] Montemurro | A twolevel procedure for the global optimum design of composite modular structures -application to the design of an aircraft wing. Part 2: numerical aspects and examples[END_REF].

We used the GA BIANCA to find a solution also for the second-level problem. In this case, each individual has a genotype composed of n chromosomes, one for each ply, characterised by a single gene coding the layer orientation.

5-Finite element models

The FE models used at the first-level of the strategy are built using the FE commercial code ANSYS ® . The need to analyse, within the same generation, different geometrical configurations (plates with different geometrical and material properties), each one corresponding to an individual, requires the creation of an ad-hoc input file for the FE code that has to be interfaced with BIANCA. The FE model must be conceived to take into account a variable geometry, material and mesh. Indeed, for each individual at the current generation the FE code has to be able to vary in the correct way the number of elements wherein the structure is discretised, thus a correct parameterisation of the model has to be achieved.

-FE model of the unit cell

In order to determine the effective properties of the core, a homogenisation technique reveals to be necessary. In this way, the periodic honeycomb structure can be replaced by an equivalent orthotropic homogeneous solid whose material properties depend on the geometric parameters of the repetitive unit of the honeycomb. In particular, these properties are determined using the strain energy-based homogenisation technique of periodic media. This technique makes use of the repetitive unit of the periodic structure to approximate its effective properties at the macro-scale level. The basic feature of the strain energy-based homogenisation technique consists in the assumption that the repetitive unit of the periodic structure and the corresponding volume of the homogeneous solid undergo the same deformation having, hence, the same strain energy, see [B1]. In this case, the periodic structure is the honeycomb core whose repetitive unit cell has three planes of symmetry, thus we decided to exploit these symmetries using, in the homogenisation process, only an eighth of the repetitive unit cell. As illustrated in Fig. 4 the model is built using the 20-node ANSYS solid element SOLID186.

In Fig. 4, the dark-grey elements represent the aluminium foils of the honeycomb core, while the light-grey ones are the fictitious elements used to model the "second phase" which has the properties of the so-called "elastic air", see [A2].

-FE model of the sandwich panel

At the macro-scale the structure is modelled with a combination of shell and solid elements. In particular, the laminated skins are modelled using ANSYS SHELL281 elements with eight nodes and six degrees of freedom (DOFs) per node, and their mechanical behaviour is described by defining directly the normalised stiffness tensors A * , B * and D * . The equivalent solid representing the core is modelled using ANSYS SOLID186 elements with 20 nodes and 3 DOFs per node having the material properties 2. In particular, such BCs are applied only on the edges of top and bottom skins. The compatibility between the displacement field of the skins (modelled with shell elements) and that of the core (modelled with solid elements) is obtained by means of constraint equations on each node belonging to contiguous solid and shell elements, see Fig. 5. In particular, we imposed rigid constraints between the nodes of the middle plane of the top (bottom) skin and the corresponding ones of the top (bottom) surface of the solid core. Through such constraints, the displacements of the nodes belonging to the top and bottom surfaces of the solid core are equal to those of the bottom and top faces of the top and bottom skins, respectively.

Sides

Constraint AB, A´B´, CD, C´D´

U x = 0 U z = 0 BC, B´C´, DA, D´A´ U y = 0 U z = 0
Table 2. BCs of the FE model of the sandwich panel.

6-Numerical results

In order to show the effectiveness of the proposed approach we studied several cases. However, for the sake of brevity, here we show only the results concerning one of these cases: a sandwich panel with different skins and with a core having a fixed thickness. In this case the core thickness does not belong to the vector of design variables, see Eq. (3), being equal to that of the reference structure. The reference structure is a square plate of side 1500 a  mm characterised by the material properties listed in Table 1 and the geometrical properties listed in Table 3.

Concerning the genetic parameters of the GA BIANCA used to solve the problem for this particular case, we consider one population of 140 individuals evolving along 300 generations with crossover and mutation probabilities of 0.85 and 0.017 respectively. The roulette-wheel operator performs selection, the elitism is active whilst the ADP method is used for handling constraints, see [START_REF] Montemurro | The Automatic Dynamic Penalisation method (ADP) for handling constraints with genetic algorithms[END_REF]. Table 3. Geometrical properties of the reference structure.

Core

 [deg] 1 l [mm] 2 l [mm] c h [mm]
The optimal values of the geometric as well as mechanical design variables issued from the first-level are listed in Table 4. As it can be easily seen, the optimum configuration has a weight of 36.88 Kg (about 10 % less than that of the reference structure) with a first buckling load of 5704.33 N/mm (about 0.2 % greater than the reference one). stacks in order to obtain the elastic uncoupling, balanced stacks to obtain the membrane orthotropy, and so on).

Core

 [deg] 1 l [mm] 2 l [mm] c h [mm]
  t * A K 0 R [MPa]   t * A 1 R [MPa]   t * A 1  [deg]   b * A K 0 R [MPa]   b * A 1 R [MPa]   b * A 1  [deg]

7-Conclusions

The main aim of the present work is to deal with the problem of the optimum design of a sandwich panel composed of two laminated skins and a honeycomb core. The design strategy that we propose is a numerical optimisation procedure that does not make use of any simplifying assumption. The design process that we propose is not submitted to restrictions: any parameter characterising our structure is an optimisation variable (geometry of the unit cell of the honeycomb core, as well as the orientations and the number of plies for the skins). In order to face the design of the sandwich structure in a very general way a two-level multi-scale strategy has been considered. The first level of the procedure involves two scales:

 the macro-scale wherein the sandwich panel is composed by two homogeneous anisotropic plates (the skins) whose behaviour is described in terms of the laminate polar parameters along with an homogeneous anisotropic core whose mechanical response is defined in terms of its effective elastic properties;

 the meso-scale of the honeycomb core where we need to model the related representative volume element in order to determine the effective material properties of the core used at the macro-scale.

Many types of design variables are included at this first level: the geometrical parameters of the honeycomb unit cell (mesoscale) together with the total thickness and the laminate polar parameters of each skin (macro-scale). The second level of the procedure concerns the meso-scale of the laminated skins: in this phase, we look for the optimal stacking sequences giving the optimum value of the thickness and of the laminate polar parameters issued from the first step.

Several features that make it an innovative, effective and general method for the design of complex multi-scale structures characterise the optimisation strategy presented in this work. The example presented in this paper shows that when standard rules for the laminate stacks are abandoned and when all the parameters characterising the structure, at each scale, are included among the design process a significant weight saving can be obtained: up to 10 % when compared to that of the reference structure with almost the same buckling load (0.2 % greater).

As a concluding remark, it can be noticed that the proposed strategy is really effective and robust and can be easily applied to other different problems.

7-References

[A1] H. G. Allen, Analysis and design of structural sandwich panels, Pergamon Press, 1969.

Figure 1 .

 1 Figure 1. Honeycomb core and the repetitive unit cell.

-

  the mechanical properties of each skin, namely the anisotropic polar parameters of the plate ( the thickness of the core c h ; -the geometrical properties of the unit cell of the honeycomb core (  ), see Fig.2;

h

  of the laminated skins are considered as discrete optimisation variables, the discretisation step being equal to the thickness of the elementary ply employed for the fabrication of the laminate, i.e.

R

  are the anisotropic ones,

Figure 2 .

 2 Figure 2. Geometrical parameters of the unit cell.

  As previously said, the aim of the first level optimisation is the weight minimisation of the sandwich panel satisfying, simultaneously, constraints of different nature. The design variables of the problem can be grouped into the following vector:

Figure 3 .

 3 Figure 3. Numerical procedure scheme for the first-level problem.

Figure 4 .

 4 Figure 4. FE model of the repetitive unit cell.

  0/45/45/-45/45/-45/0/0/45/-45/45/-45/-45/0/45] s Bottom skin sequence [deg] [45/0/45/45/-45/45/-45/0/0/45/-45/45/-45/-45/0/45] s Weight [Kg] 1 st buckling load [N/mm] 41.02 5691.88

Figure 5 .

 5 Figure 5. FE model at the macro-scale.

Material properties of the carbon-epoxy

			mm 3 ]
	70 000	0.33	2.7 x 10 -6
	E [MPa]	E [MPa]	E [MPa]
	1	2	3
	181 000	10 300	10 300
	G [MPa]	G [MPa]	[MPa]
	12	23	13
	7 170	3 843	7 170
			
	12	23	13
	0.28	0.34	0.28
	 [Kg/mm 3 ]	1.58 x 10 -6
	s

Table 1 . Material properties of the aluminium foils and of the carbon-epoxy plies.

 1

Table 4 . Geometrical and mechanical properties of the optimum configuration.

 4

	19594	356	-45	19324	168	45
		Top skin sequence [deg]
	[-44/46/-44/46/41/-44/-44/46/46/46/-49/-44/51/-44/46
	-49/41/-44/-39/41/46/-44/46/-44/-44/46/-49/46]
		Bottom skin sequence [deg]
	[43/43/-45/-45/-45/49/49/-41/-53/47/-44/43/-45/
	-45/39/43/-46/40/48/-44/48/48/-41/-50/-45/44/44/-45]
	Weight [Kg]		1 st buckling load [N/mm]
		36.88		5704.33
	The optimal laminate stacks, satisfying the values of the
	geometric and polar parameters issued from the first-level
	problem, for both top and bottom skins are also listed in

Table 4 .

 4 It is worth noting that these stacking sequences represent true general solutions: no hypotheses are imposed on the stack in order to meet the elastic requirements, unlike what is often done in the literature (for example symmetric

		Solid
	Shell	Element
	Element
		Rigid
		Constraint


Tomáš Kaiser
email: kaisert@kma.zcu.cz.

Ondřej Rucký

Matěj Stehlík
email: matej.stehlik@g-scop.inpg.fr.

Riste Škrekovski
email: skrekovski@gmail.com.

Strong parity vertex coloring of plane graphs *

Keywords: graph, strong parity vertex coloring, strong parity chromatic number, proper coloring, face, discharging

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the coloring we construct is proper. This proves a conjecture of Czap and Jendrol ' [Discuss. Math. Graph Theory 29 (2009), pp. 521-543.]. We also provide examples showing that eight colors may be necessary (ten when restricted to proper colorings).

Introduction

The notions of strong parity vertex coloring and the strong parity chromatic number were defined by Czap and Jendrol ' [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF]. Let us recall their definition in an equivalent form. Let G be a nontrivial connected plane graph, and let f be one of its faces. (Throughout the paper, graphs are allowed to have parallel edges but no loops.) Consider a (possibly improper) vertex coloring of G. The face f satisfies the strong parity vertex coloring condition (spvcondition for short) with respect to the coloring if for each color c of the coloring, there is zero or an odd number of occurrences of vertices colored with c on a closed facial walk of f . The coloring is a strong parity vertex coloring (spv-coloring for short) if the spv-condition holds for every face of G. Assume now that G is 2-connected. Then the minimum number of colors in an spv-coloring of G is called the strong parity chromatic number of G and is denoted by χ s (G). The restriction to 2-connected graphs in the definition of χ s is essential, since there are plane graphs of connectivity one that do not admit any spv-coloring (an example of Czap and Jendrol ' [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF] consists of two triangles sharing one vertex). Similarly, the existence of an spv-coloring cannot be guaranteed for graphs with loops (which is why we exclude them in our definition).

Czap and Jendrol ' [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF] conjectured that there is a constant bound K on χ s in the class of 2-connected plane graphs. Furthermore, they suggested that the best possible bound equals 6, providing an infinite family of graphs with χ s = 6. The main result of our paper confirms the conjecture for the class of 2-connected plane graphs with an added restriction to proper colorings: Theorem 1.1. Every 2-connected plane (loopless) graph has a proper spv-coloring with at most 97 colors.

The proof is given in Section 2. (During the preparation of this paper, another proofgiving a slightly worse constant-was independently found by Czap, Jendrol ' , and Voigt [START_REF] Czap | Parity vertex colouring of plane graphs[END_REF].) In Section 3, we present examples showing that the best possible value of K in the above conjecture is at least 8, or at least 10 with the restriction to proper colorings.

It should be noted that prior to the introduction of parity vertex colorings, a related type of edge coloring was considered in [START_REF] Bunde | Parity and strong parity edge-coloring of graphs[END_REF][START_REF] Bunde | Optimal strong parity edge-coloring of complete graphs[END_REF]. An edge variant of parity coloring (called facial parity edge coloring) was recently studied, e.g., in [START_REF] Czap | Facial parity edge colouring of plane pseudographs[END_REF].

In the remainder of this section, we establish the basic notation used throughout the paper; the notions not mentioned here are standard in graph theory [START_REF] Diestel | Graph Theory[END_REF]. As mentioned above, graphs are assumed to be loopless, but parallel edges are allowed. A graph is called trivial if it is empty or consists of a single vertex. Let G be a plane graph; let v be a vertex, e 1 and e 2 edges, and f a face of G. Then F (v) or F (e 1 ) denotes the set of faces incident with v and e 1 respectively. The boundary vertices and boundary edges of f are all the vertices and edges of G, respectively, incident with f . The sets of these vertices and edges are denoted by V (f ) and E(f ) respectively. We refer to |V (f )| as the length of f .

The degree of v in G, i.e., the number of edges of G incident with v, is denoted by d(v). If d(v) = 2, the vertex v is a 2-vertex ; when d(v) > 2, we call v a high-degree vertex or a vertex of high degree. The edges e 1 and e 2 are parallel if they are not loops and share their end-vertices. When e 1 and e 2 are parallel and constitute the boundary of f , the face f is called a digon. A path P is trivial if it comprises a single vertex, that is, the length of P equals 0. Every vertex of P other than its end-vertices is called an internal vertex of P . Finally, we remark that for all the notation defined, the relevant graph may be referred to by a subscript whenever necessary. For example, we write

F G (v) or d G (v) if this graph is G. v 1 = v 4 v 2 v 3 v 0 Figure 2.1.
The annihilation of a vertex v. The original graph G is on the left, the resulting graph G ′ on the right.

Upper bound

This section is devoted to the proof of the main result, Theorem 1.1. In Section 2.1, we prove certain structural properties of a minimal counterexample. These are used in an application of the discharging method in Section 2.2.

We now introduce a graph operation to be used in the proof of Lemma 2.4. Let G be a plane graph and v ∈ V (G) a vertex of degree d ≥ 2, and let the edges incident with v be enumerated in a clockwise order as e i = vv i , i ∈ Z d (we write Z d for the set {0, . . . , d -1} with addition modulo d). Suppose that the vertices v i are pairwise different (that is, v is not incident with a pair of parallel edges). The annihilation of v is the construction of a plane graph G ′ from G defined as follows:

(1) add edges e ′ i = v i v i+1 , i ∈ Z d , embedded in the plane so that for each i, the edges e i , e i+1 , and e ′ i , in this order, constitute a facial walk;

(2) delete v together with all the edges e i .

Intuitively, one may achieve the desired embeddings of the edges e ′ i by drawing each e ′ i 'close enough' to the curve consisting of the embeddings of e i and e i+1 ; see Figure 2.1 for an example of a properly conducted annihilation.

Regarding the faces of G and G ′ , it is obvious that the following holds:

Observation 2.1. Let G ′ be obtained from G by the annihilation of a vertex v ∈ V (G). Then (1) every face of G not in F G (v) is also a face of G ′ ;
(2) each face g ∈ F G (v) has its counterpart g ′ in G ′ such that a facial walk of g ′ may be obtained from a facial walk of g by replacing each of its subsequences of the form e i ve i+1 with e ′ i , and hence V (g ′ ) = V (g) -{v};

(3) there is precisely one more face in G ′ , having the sequence

v 0 e ′ d-1 v d-1 e ′ d-2 . . . v 1 e ′ 0 v 0 as its facial walk.
The assumption that v is not incident with a pair of parallel edges is essential: without it, the annihilation of v may produce a loop as well as a cutvertex. On the other hand, the following lemma shows that parallel edges incident with v are the only reason for such a result: Lemma 2.2. Let v be a vertex of a 2-connected (loopless) plane graph G, |V (G)| ≥ 4, such that v is incident with no pair of parallel edges. Then the graph G ′ obtained from G by annihilating v is 2-connected (and loopless).

Proof. We use the well-known fact that a connected loopless plane graph G on at least three vertices is 2-connected if and only if the facial walk of each of its faces is a cycle. (The 'only if' direction is Proposition 4.2.6 in [START_REF] Diestel | Graph Theory[END_REF]. Conversely, for any cutvertex v of G there is a face whose boundary contains two neighbors of v in different components of G -v. Since each cycle is contained within some block, the boundary of this face cannot be a cycle.)

We use this criterion for both G and G ′ in the following. (Note that G ′ is connected.) Take an arbitrary face f ′ of G ′ , and let W be a facial walk of f ′ . We may assume that f ′ is not a face of G, otherwise there is nothing to show. Thus by Observation 2.1, W is either the walk v 0 e ′ d-1 v d-1 e ′ d-2 . . . v 1 e ′ 0 v 0 (up to the choice of the end-vertex), or it arises from a facial walk of a face of G by replacing each of its subsequences of the form e i ve i+1 with e ′ i . In both cases, it follows from the assumptions that W is a cycle.

Finally, we include a technical lemma that will greatly simplify the case analysis in the proof of Claim 1 in Section 2.2. Lemma 2.3. Let (l i ), (l ′ i ), i = 0, . . . , k, be tuples of positive integers such that l j ≤ l ′ j for every j = k, and l ′ k ≥ l ′ j for every j = k with l j < l ′ j . Then

k i=0 l ′ i ≤ k i=0 l i or k i=0 1/l ′ i ≤ k i=0 1/l i . Proof. We first prove that if k i=0 l ′ i = k i=0 l i and the tuples are distinct, then k i=0 1/l ′ i < k i=0 1/l i .
We proceed by induction on the size of the set J := {j : j = k, l j < l ′ j }. From the assumption that (l ′ i ) and (l i ) are distinct and have the same sum (and l j ≤ l ′ j for j = k), it follows that J is nonempty. Now, fix j 0 as some index in J, and let

d := l ′ j 0 -l j 0 . Consider a tuple (l ′′ i ) such that l ′′ j 0 = l ′ j 0 = l j 0 + d, l ′′ k = l k -d, and l ′′ j = l j for each remaining index j. Clearly, k i=0 l ′′ i = k i=0 l ′ i , l ′′ k ≥ l ′ k , and the number of j = k such that l ′′ j = l ′ j equals |J| -1. We have k i=0 1 l ′′ i = k i=0 1 l i + 1 l ′′ j 0 - 1 l j 0 + 1 l ′′ k - 1 l k = k i=0 1 l i -d 1 l j 0 (l j 0 + d) - 1 l ′′ k (l ′′ k + d) ,
and since l ′′ k ≥ l ′ k ≥ l ′ j 0 > l j 0 by the assumptions and the choice of j 0 , it follows immediately that

k i=0 1 l ′′ i < k i=0 1 l i . (2.1)
When |J| = 1 (the base case of the induction), the tuple (l ′′ i ) equals (l ′ i ) and there is nothing more to prove. Otherwise, we may apply the induction hypothesis to (l ′′ i ) and (l ′ i ), in this order, obtaining k i=0 1/l ′ i < k i=0 1/l ′′ i ; this together with (2.1) gives the desired conclusion.

Now we prove the lemma. We may suppose that

k i=0 l ′ i > k i=0 l i . If l ′ k ≥ l k , then trivially k i=0 1/l ′ i < k i=0 1/l i .
Otherwise, we claim that there exists a tuple (l ′′ i ) such that l j ≤ l ′′ j ≤ l ′ j for every j = k, l ′′ k = l ′ k , and k i=0 l ′′ i = k i=0 l i . Indeed, (l ′′ i ) may be obtained from (l ′ i ) by replacing some of the values l ′ j (j < k) with smaller ones, using the fact that

k-1 i=0 (l ′ i -l i ) > l k -l ′ k . Note that (l ′′ i ) is distinct from both (l i ) and (l ′ i ). It follows from the above that k i=0 1/l ′′ i < k i=0 1/l i . Furthermore, since l ′′ i ≤ l ′ i for all i ≤ k and the tuples are not equal, k i=0 1/l ′ i < k i=0 1/l ′′ i .
The proof is now complete.

Reducibility

Let G be a counterexample to Theorem 1.1 with the minimum number of vertices, and subject to this condition, with the minimum number of edges. In Lemma 2.4 below, we infer several constraints applying to G. Based on these constraints, we derive bounds for the (reduced) face degree of a vertex in G in Lemma 2.5. As per standard terminology, a graph contradicting Lemma 2.4 is said to be reducible.

Before stating the lemma, we introduce some terminology. Let v be a vertex and f a face of G. The face-vertex neighborhood of v in G, denoted by N F (v), is defined as g∈F (v) V (g) -{v}. Similarly, the f -reduced face-vertex neighborhood of v, referred to as N F (v, f ), is the set g∈F (v), g =f V (g) -{v}. We call the sizes of these sets the face degree of v and f -reduced face degree of v respectively, writing d F (v) and d F (v, f ) respectively. As with the other notation, the graph G is included as a subscript if necessary. For instance, we may write

N F G (v) or d F G (v, f ). Lemma 2.4.
The graph G has the following properties:

(1) |V (G)| > 97;
(2) G does not contain parallel edges; in particular, G is without digons;

(3) no facial walk of a face of G contains four consecutive 2-vertices;

(4) for every vertex v of G, it holds d F (v) ≥ 97;

(5) for every two vertices u and v of G such that

F (u) ∩ F (v) = {f }, it holds d F (u, f ) + d F (v, f ) ≥ 96.
Proof. By assumption, G is a 2-connected graph. We prove each of the assertions by contradiction. To see [START_REF] Bunde | Parity and strong parity edge-coloring of graphs[END_REF], consider an assignment of a different color to each vertex of G.

We proceed to show assertion [START_REF] Bunde | Optimal strong parity edge-coloring of complete graphs[END_REF]. Let e 1 and e 2 denote two parallel edges in G. We distinguish two cases. If e 1 together with e 2 delimit a digon f , we simply delete one of the two edges, say e 1 , obtaining a (2-connected) graph G ′ . By the minimality of G, the graph G ′ has a proper spv-coloring c with at most 97 colors. As all faces of G except f have their counterparts in G ′ with the same sets of boundary vertices, and c is proper, c is also a proper spv-coloring of G.

When, on the other hand, the curve C comprising the embeddings of e 1 and e 2 is not the boundary of a digon, we produce two graphs G 1 and G 2 by deleting the interior and exterior of C from G, respectively. Both these graphs are clearly 2-connected (in particular, each has at least three vertices), and smaller than G with respect to the given ordering; thus each has a proper spv-colorings with at most 97 colors. The colorings can be chosen so that they coincide at the common vertices, i.e., the end-vertices of e 1 , and the number of colors in their union c is minimal. Then c is a proper spv-coloring of G using at most 97 colors.

Next, suppose x 1 x 2 x 3 x 4 is a path contradicting statement (3). Let v 1 be the neighbor of x 1 in G other than x 2 , and let v 4 be the neighbor of x 4 other than x 3 . The vertices v 1 and v 4 are distinct and different from all x i , i = 1, . . . , 4, otherwise the facial walk would contain just four or five vertices, and by the 2-connectedness of G these would be the only vertices of G; a contradiction to assertion [START_REF] Bunde | Parity and strong parity edge-coloring of graphs[END_REF]. We construct a graph G ′ by contracting the path x 1 . . . ). Now, we use the coloring for the corresponding vertices of G and assign the color c(v 1 ) to x 2 , x 4 , and the color c(v ′ 4 ) to x 1 , x 3 , v 4 . This way the occurrence of the colors c(v 1 ) and c(v ′ 4 ) preserves the parity on the corresponding facial walks, and we obtain a proper spv-coloring of G with no more than 97 colors. Now we focus on assertion (4). Suppose it does not hold. We perform the annihilation of v, obtaining a graph G ′ . By parts (1) and ( 2), G has obviously more than 3 vertices and has no parallel edges incident with v, and since G is 2-connected, Lemma 2.2 assures that G ′ is 2-connected, as well. By the minimality of G, G ′ has a proper spv-coloring c with at most 97 colors. Using c for G and assigning to v a color not used by c on any vertex in N F G (v), but if possible present in c, we obtain a proper coloring of G of cardinality less than or equal to 97.

By Observation 2.1, the only faces of G whose sets of boundary vertices differ from those of their counterparts in G ′ are the elements of F G (v), but by the choice of the color of v, the spv-condition is maintained for them. Hence, the coloring of G is also an spv-coloring; a contradiction.

Finally we deal with statement [START_REF] Czap | Facial parity edge colouring of plane pseudographs[END_REF]. Suppose it does not hold. We construct a graph G ′′ by annihilating u. As above, G ′′ is 2-connected, and hence we may annihilate v in G ′′ to obtain the graph G ′ . Since u and v have precisely one common incident face in G, they are not adjacent; therefore, the annihilation of u does not create any new edges at v. This means, by part [START_REF] Bunde | Optimal strong parity edge-coloring of complete graphs[END_REF], that there is no pair of parallel edges incident with v in G ′′ , and thus, considering statement (1) again, Lemma 2.2 can be applied to the annihilation of v. We conclude that G ′ is 2-connected. As it is also smaller than G with respect to our order, there is a proper spv-coloring c ′ of G ′ using at most 97 colors.

We extend the coloring to G as follows. If there exists a color used by c ′ on a vertex in

V G (f ) -N F G (u, f ) -N F G (v, f ) and on no vertex in N F G (u, f ) ∪ N F G (v, f
), we assign this color to both u and v. Otherwise we color each of u and v with a different color not used by c ′ on any vertex in

N F G (u, f ) ∪ N F G (v, f ), but if possible appearing in c ′ .
Either case yields a coloring c of G with no more than 97 colors.

For the desired contradiction, it remains to show that c is a proper spv-coloring of G. As the neighbors of u and v belong to

N F G (u, f ) ∪ N F G (v, f
), the coloring is indeed proper. Next, by Observation 2.1 and the assumption about

F (u) ∩ F (v), we see that each face g of G has its counterpart g ′ in G ′ with V G (g) equal to V G ′ (g ′ ) ∪ {u, v} if f = g, V G ′ (g ′ ) ∪ {u} if g ∈ F G (u) -{f }, V G ′ (g ′ ) ∪ {v} if g ∈ F G (v) -{f }, and V G ′ (g ′ ) otherwise.
Considering the particular choice of the colors of u and v in either case, it is straightforward that the spv-condition holds for every face of G.

Let f be a face of the graph G. The number of high-degree vertices (i.e., vertices of degree at least 3) on the boundary of f is called the weight of f and is denoted by w(f ). The face f is a pseudodigon if w(f ) = 2 and f is not a digon. We say that f is small if w(f ) < 20, and large if w(f ) ≥ 20. The configuration of a vertex v of G is the tuple obtained by ordering the elements from the multiset {w(g) : g ∈ F (v)} in a nondecreasing manner.

Lemma 2.5. Let v be a vertex of G of degree k ≥ 2. Let the faces incident with v be denoted by f 0 , . . . , f k-1 in a clockwise order around v. Let l i = w(f i ) for every such face f i . The following bounds hold for the face degree of v:

(1) if k ≥ 3, then d F (v) ≤ 4 k-1 i=0 l i -5k -3σ
, where σ is the number of all i = 0, . . . , k -1 with the property that l i + l i+1 ≤ 25 (indices modulo k);

(2) if k = 2, then d F (v) ≤ 4(l 0 + l 1 ) -6;
(3) If k = 3, then the configuration of v is different from [START_REF] Bunde | Optimal strong parity edge-coloring of complete graphs[END_REF]8,19) and [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF]8,19).

For the f 0 -reduced face degree, we have the following:

(4) if k ≥ 3, then d F (v, f 0 ) ≤ 4 k-1 i=1 l i -5k + 9; (5) if k = 3 and l 1 + l 2 ≤ 25, then d F (v, f 0 ) ≤ 4(l 1 + l 2 ) -9.
Proof. Let f j be a face of G incident with the vertex v. Traversing the boundary cycle of f j clockwise from v, let P v (f j ) be the subpath of the boundary cycle starting with the successor of v and ending with the predecessor of the last high-degree vertex before v. (See Figure 2.2 for an illustration.) Let p v (f j ) be the number of vertices of P v (f j ). Since each vertex in N F (v) is included in at least one of the paths P v (f i ) (i = 0, . . . , k -1), we have

d F (v) ≤ k-1 i=0 p v (f i ).
(2.2)

v P v (f 0 ) f 0 f 1 f 2 f 3 Figure 2.2.
The definition of the path P v (f i ) for i = 0 and a vertex v of degree 4. Highdegree vertices are shown as larger dots.

We now bound p v (f i ). Assume first that k ≥ 3. Recall that every two consecutive highdegree vertices on the boundary of f i are separated by at most three vertices of degree 2 (Lemma 2.4 (3)). Since exactly two out of the l i high-degree vertices are excluded from P v (f i ), the path P v (f i ) decomposes into l i -2 segments, each consisting of at most three vertices of degree 2 (in G) followed by a high-degree vertex, and one final segment consisting of up to three vertices of degree 2 and no high-degree vertex. The final segment may be empty. We find:

p v (f i ) ≤ 4(l i -2) + 3 = 4l i -5. (2.3)
We also observe an improvement in the following special case. Let us call the path P v (f i ) deficient if it starts or ends with a high-degree vertex (of G), or if it contains two consecutive high-degree vertices. In that case, one of the above defined segments contains zero instead of three vertices of degree 2, and we obtain:

p v (f i ) ≤ 4l i -8 if P v (f i ) is deficient. (2.4) If k = 2, analogous reasoning yields p v (f i ) ≤                4l i -9 if P v (f i ) contains three consecutive high-degree vertices, 4l i -7 if P v (f i ) starts with two high-degree vertices, 4l i -5 if P v (f i ) ends at a high-degree vertex, 4l i -4 if P v (f i ) is deficient, 4l i -2 otherwise.
(2.5)

We can now prove part (2) of the lemma. It may be assumed that P v (f 0 ) starts with a high-degree vertex, since adjacent 2-vertices have the same face degree. By (2.2) and (2.5),

d F (v) ≤ p v (f 0 ) + p v (f 1 ) ≤ (4l 0 -4) + (4l 1 -2) = 4(l 0 + l 1 ) -6.
Next, we derive part [START_REF] Bunde | Parity and strong parity edge-coloring of graphs[END_REF]. From (2.2) and (2.3), it follows that

d F (v) ≤ 4 k-1 i=0 l i -5k.
(2.6)

We need to improve this estimate by 3σ, where σ is as defined in the lemma. Let i be such that l i + l i+1 ≤ 25 (indices modulo k) and let w be the first vertex of P v (f i+1 ). If the degree of w is 2, then by part (2) of the lemma, d F (w) ≤ 94, contradicting Lemma 2.4 (4). Thus, P v (f i+1 ) starts with a high-degree vertex and we can apply (2.4) in place of (2.3) to bound p v (f i+1 ). This results in an improvement to the upper bound in (2.6) by 3 for each i satisfying l i + l i+1 ≤ 25, and hence in an improvement by 3σ in total. Part (1) of the lemma follows.

Let us proceed to part (3). First, note that {l 0 , l 1 , l 2 } = {2, 8, 19} by part (1): indeed, we would have

d F (v) ≤ 4 • (l 0 + l 1 + l 2 ) -5 • 3 -3 • 2 = 95,
contradicting Lemma 2.4 (4). Suppose then that l 0 = 3, l 1 = 8 and l 2 = 19. No vertex of degree 2 in G is incident with both f 0 and f 2 , since part (2) of the lemma would imply that its face degree is bounded by 4(3 + 19) -6 = 82, contradicting Lemma 2.4 (4). Thus, P v (f 0 ) starts with a high-degree vertex, and the same can be proved for P v (f 1 ) by an identical argument.

We claim that no vertex of degree 2 in G is incident with both f 1 and f 2 . Suppose to the contrary that there is such a vertex, and let z be the last 2-vertex encountered on the clockwise boundary cycle of f 1 before v. The fact that P v (f 0 ) starts with a high-degree vertex implies that P z (f 2 ) ends at a high-degree vertex. Furthermore, since P v (f 1 ) starts with a high-degree vertex, P z (f 1 ) either starts with two consecutive high-degree vertices (if z is a neighbor of v) or contains three consecutive high-degree vertices. By (2.5),

d F (z) ≤ (4l 1 -7) + (4l 2 -5) = 96,
a contradiction with Lemma 2.4 (4). It follows that besides P v (f 0 ) and P v (f 1 ), the path P v (f 2 ) is also deficient. By (2.4),

d F (v) ≤ 4 • (l 0 + l 1 + l 2 ) -3 • 8 = 96,
which again contradicts Lemma 2.4 (4).

We turn to part (4) of the lemma. Unlike the situation in the proof of part (1), N F (v, f 0 ) is not entirely covered by the sets V (P v (f i )), where i = 1, . . . , k -1. On the other hand, only a few vertices of N F (v, f 0 ) are missing in the union of these sets, namely the vertices on the boundary of f k-1 not contained in P v (f k-1 ). If we let u denote the vertex that follows P v (f k-1 ) on the boundary of f k-1 , then the missing vertices are u and the (up to three) vertices of degree 2 following u. Consequently,

d F (v, f 0 ) ≤ k-1 i=1 p v (f i ) + 4, (2.7)
and by (2.3),

d F (v, f 0 ) ≤ 4 k-1 i=1 l i -5(k -1) + 4 = 4 k-1 i=1 l i -5k + 9.
Part ( 5) follows easily from (2.7) using the estimate (2.3) for the face f 1 and the estimate (2.4) for f 2 (note that l 1 + l 2 ≤ 25 implies that P v (f 2 ) is deficient, just as in the proof of ( 1)). The proof is thus complete.

Discharging

Having explored the properties of the graph G, we are ready to use the discharging method to arrive at a contradiction.

We assign an initial charge to the vertices and faces of G as follows:

• each vertex v receives d(v) -6 units of charge;

• each face f receives 2|V (f )| -6 units of charge.

The following observation is a well-known consequence of Euler's formula.

Observation 2.6. The sum of the charges defined above is -12.

In the first phase, we redistribute the charges according to Rules 1-2:

Rule 1. Every face that is not a pseudodigon sends two units of charge to each incident 2-vertex. Each pseudodigon does the same, except that one of the respective 2-vertices receives no charge.

Observe that after the application of Rule 1, the charge of each face is nonnegative. In addition, the charge of every large face is at least 2 • 20 -6 = 34. Rule 2. Every small face distributes its remaining charge evenly to all incident high-degree vertices (i.e., vertices of degree at least 3). Each large face (i.e., a face of weight at least 20) behaves in the same way, except that it retains a charge of 4.

After applying the above rules the first phase is completed. In the second phase, Rule 3 is applied to the vertices that ended up with negative charge after the first phase.

Rule 3. If a vertex has a negative charge of c and is incident with a large face f , then it receives the charge of -c from f . We will show that the final charge of every vertex and face in G is nonnegative, contradicting Observation 2.6.

Recall from Subsection 2.1 that the configuration of a vertex v of G is obtained by ordering the multiset {w(g) : g ∈ F (v)} in a nondecreasing way. If we remove (one copy of) the element w(f ) from this ordered multiset, we obtain the f -reduced configuration of v.

It will be convenient to alter the definition of the weight of a face f and the configuration of a vertex v as follows. The modified weight w ′ (f ) of f is defined as 3 if w(f ) = 2, and w(f ) otherwise. Replacing the weight of each face by its modified weight in the definition of the configuration of v, we obtain the modified configuration of v. The modified f -reduced configuration of v is obtained from the f -reduced configuration of v in an analogous way.

First we analyze how much charge a vertex v of high degree d receives by Rule 2. Denote the faces incident with v by f i , i = 0, . . . , d -1, and let n i be the number of 2-vertices incident with f i . After applying Rule 1, each f i has charge 2|V (f i )| -6 -2n i if f i is not a pseudodigon, and 2|V (f i )| -6 -2(n i -1) otherwise. By Lemma 2.4 (2), f i is not a digon so in both cases the charge can be written as 2w ′ (f i ) -6. Hence, when f i is a small face, it sends v the charge of 2w

′ (f i ) -6 w(f i ) = 2 - 6 w ′ (f i )
.

(The equality is true as w(f i ) = w ′ (f i ) if f i is not a pseudodigon, and 2w ′ (f i ) -6 = 0 otherwise.) On the other hand, when f i is a large face, it sends v

2w ′ (f i ) -6 -4 w(f i ) = 2 - 10 w ′ (f i )
units of charge. Note that in both cases the charge received by v from f i is nonnegative. In total, the vertex v obtains the nonnegative charge of

i w ′ (f i )<20 2 - 6 w ′ (f i ) + i w ′ (f i )≥20 2 - 10 w ′ (f i ) = 2d -6 i w ′ (f i )<20 1 w ′ (f i ) -10 i w ′ (f i )≥20 1 w ′ (f i ) . (2.8)
Next, we establish the following two essential claims. For convenience, we refer to the vertices with a negative charge after the first phase as special vertices. Since the initial charge of a vertex v is d(v) -6 and each vertex receives a nonnegative charge during the application of Rule 2, every special vertex has degree at most 5.

Claim 1. Every special vertex is incident with a large face.

Proof. We proceed by contradiction, assuming that v is a special vertex not incident with any large face. First suppose that d(v) = 2; let f 1 and f 2 be the two faces incident with v. As the initial charge of v is -4, at least one of these faces, say f 1 , is a pseudodigon by Rule 1. By assumption, w(f 2 ) ≤ 19. Hence d F (v) ≤ 78 by Lemma 2.5 (2), a contradiction to Lemma 2.4 (4).

Therefore, let v be a special vertex of high degree d. Summing its initial charge and the charge (2.8) received by Rule 2 gives 3d -6 -

6 i 1 w ′ (f i ) < 0, or equivalently, i 1 w ′ (f i ) > d 2 -1.
(2.9)

We proceed by case analysis; let (l ′ i ) denote the modified configuration of v. (We write (l ′ i ) instead of (l i ) as a reminder that the configuration is a modified one.) Assume first that v is of degree 3. Then l ′ 0 ≤ 5, otherwise (2.9) fails since its left hand side is at most 3 • (1/6) which equals its right hand side 1/2. Since v is not incident with any large face, we have l ′ 1 , l ′ 2 ≤ 19. We aim to use Lemma 2.5 to bound d F (v). Although it is formulated for ordinary (non-modified) configurations, the monotonicity of the upper bounds ensures that the lemma remains valid if the configuration is a modified one. By Lemma 2.5 (1),

d F (v) ≤ 4 i l ′ i -21. Consequently, Lemma 2.4 (4) implies that i l ′ i ≥ 30.
(2.10)

If l ′ 0 = 3 and l ′ 1 ≤ 9, then by (2.10) (l ′ i ) is one of the three tuples [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF]8,19), (3, 9, 18), and [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF]9,19). The first of these is excluded by Lemma 2.5 (3), and the remaining two contradict (2.9). If l ′ 0 = 3 and l ′ 1 > 9, then by Lemma 2.3 applied to the tuples (3, 10, 15) and (l ′ i ), in this order, either i l ′ i ≤ 28 or i 1/l ′ i ≤ 1/2. However, that contradicts (2.10) or (2.9), respectively.

Hence

l ′ 0 ≥ 4. If l ′ 0 , l ′ 1 = 4, then i l ′ i ≤ 27
, which is impossible by (2.10). Otherwise we may use Lemma 2.3 for the tuples (4, 5, 20) and (l ′ i ), and obtain a contradiction to (2.10) or (2.9) again.

Thus d ≥ 4; as we have remarked above, d ≤ 5. Lemmas 2.5 (1) and 2.4 (4) imply (2.10) again. In particular, (l ′ i ) cannot be of the form (3, 3, 3, x). If d = 4, then by Lemma 2.3 applied to the tuple [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF][START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF][START_REF] Czap | Parity vertex colouring of plane graphs[END_REF]12), i l ′ i ≤ 22 or i 1/l ′ i ≤ 1, contradicting (2.10) or (2.9). For d = 5, we obtain a similar contradiction by applying Lemma 2.3 to [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF][START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF][START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF][START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF][START_REF] Diestel | Graph Theory[END_REF], which yields i l ′ i ≤ 18 or i 1/l ′ i ≤ 3/2.

Claim 2. Every large face has a nonnegative final charge.

Proof. Let f be an arbitrary large face of G. We start by listing the possible f -reduced or modified f -reduced configurations of special vertices incident with f , and for each case we note a lower bound on the charge of these vertices. Take such a special vertex v.

If v is a 2-vertex, then by Rule 1 its f -reduced configuration is (2) and the charge equals -2.

Now suppose that v is of high degree d. Let (l ′ i ), i = 1, . . . , d -1, be its modified f -reduced configuration, and let d ′ denote the number of large faces incident with v. As noted earlier, d ≤ 5. By considering the initial charge of v and (2.8), we see that after applying Rule 2, v has charge 3d -6 -

6 i w ′ (f i )<20 1 w ′ (f i ) -10 i w ′ (f i )≥20 1 w ′ (f i )
.

As the charge is negative by assumption,

3d -6 -6 i w ′ (f i )<20 1 w ′ (f i ) - d ′ 2 < 0 (2.11)
by the definition of large face. Furthermore, w ′ (f i ) ≥ 3 always, and hence

3d -6 -2(d -d ′ ) -d ′ /2 < 0.
Since the left hand side equals d -6 + 3d ′ /2, we deduce that d ′ = 1 (i.e., f is the only large face incident with v), and that d ≤ 4. Assume first that d = 3. Then (2.11) reduces to

5 2 -6 1 l ′ 1 + 1 l ′ 2 < 0.
We infer that either l ′ 1 = 3 and l ′ 2 ≤ 11, or l ′ 1 = 4 and l ′ 2 ≤ 5. The charge of v is at least 1/2 -6/l ′ 2 in the former, and at least 1 -6/l ′ 2 in the latter case. Now let d = 4. By (2.11), 11 2 -

6 i 1 l ′ i < 0.
If some l ′ i were greater than or equal to 4, this inequality would not hold. Hence (l ′ i ) = (3, 3, 3) and the charge of v is at least -1/2. We summarize the results in Table 1.

Let S denote the set of all special vertices incident with f and R their total charge after the completion of the first phase. We observe the following: Any two vertices u, v ∈ S have at least two common incident faces.

(2.12) Suppose the contrary. In view of the possible f -reduced or modified f -reduced configurations of u and v listed in Table 1, Lemma 2.5 (4) and ( 5) implies that both d F (u, f ) and d F (v, f ) are at most 47. On the other hand, Lemma 2.4 (5) and the assumption that f is the only face incident with both u and v imply that d F (u, f ) + d F (v, f ) > 95, a contradiction.

(modified) f -reduced configuration charge

(2) -2

(3, x), x ≤ 11 ≥ 1/2 -6/x ≥ -3/2 (4, x), x ≤ 5 ≥ 1 -6/x ≥ -1/2 (3, 3, 3) ≥ -1/2
Table 1. The proof of Claim 2: the list of possible f -reduced (the first line) or modified f -reduced (the other lines) configurations of special vertices incident with the face f , together with the charge of these vertices.

We proceed to prove Claim 2 by contradiction. Suppose that f has a negative charge after the application of Rule 3. Since the charge of f after the first phase is 4 units (by Rule 2 for large faces), this is equivalent to the condition R < -4.

(2.13)

Considering the lower bounds for charges in Table 1, we that there are at least three special vertices. Let v ∈ S be a 2-vertex; the other face f ′ incident with v is a pseudodigon. By Rule 1 and (2.12), every other vertex v ′ in S is one of the two high-degree vertices v 1 , v 2 incident with f ′ . Therefore S = {v, v 1 , v 2 }; it follows that v 1 and v 2 are both of degree 3 by assumption (2.13). This means that F (v 1 ) = F (v 2 ), and hence the configuration of both vertices is the same. Considering (2.13) again, the modified f -reduced configuration of both v 1 and v 2 is [START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF][START_REF] Czap | Colouring vertices of plane graphs under restrictions given by faces[END_REF].

At this point, we digress by making an auxiliary observation:

Let g be a face of G with w(g) ≤ 3. The intersection of the boundaries of f and g consists of pairwise disjoint paths, of which at most one is nontrivial; the internal vertices of all these paths are of degree 2 in G. Furthermore, any two vertices of degree 3 incident with both f and g are precisely the end-vertices of such a nontrivial path, and hence, there are at most two such vertices.

(2.14)

To prove this, let us denote the intersection of the boundaries of f and g by H. The assertion about the structure of H is obvious by considering the 2-connectedness of G and the weights of both f and g. Let P denote the set of the respective paths. If v is a vertex of degree 3 incident with f and g, then H must contain an edge incident with v, i.e., v lies on-and hence is an end-vertex of-a nontrivial path in P. The second assertion easily follows. Applying (2.14) to the face incident with v 1 different from f and f ′ , and recalling that f ′ is a pseudodigon, we infer that w(f ) = 2; a contradiction. Thus all vertices in S are of high degree. Suppose that S = {v 1 , v 2 , v 3 }. Then by assumption (2.13), the modified f -reduced configuration of v 1 , v 2 , and v 3 is (3, 3). Hence by (2.14), no face other than f is incident with the three vertices. By (2.12), G contains three different faces f ij , 1 ≤ i < j ≤ 3, incident with both v i and v j and different from f . By (2.14), the boundary of f is precisely P; thus w(f ) = 3, a contradiction to the assumption that f is large.

Therefore |S| ≥ 4. We claim that G contains a face f ′ = f incident with all the vertices in S. To prove this, consider three vertices u, x, v in S consecutively encountered on a facial walk of f . By (2.12), there is a curve C uv connecting u and v through a face f uv = f of G. Consider any vertex y ∈ S -{u, x, v}. There is a curve C xy connecting x and y through a face f xy = f . If we let C vu be a curve connecting v to u through f , then C uv ∪ C vu is a closed curve separating x from y. Consequently, C uv intersects C xy , and therefore y is incident with the face f uv . The assertion easily follows. Now let k := |S|. Then w(f ′ ) ≥ k, and consequently the f -reduced configuration of each v in S contains a number greater than or equal to k. From Table 1, we see that

R ≥ k 1 2 - 6 k = k 2 -6,
the right side of which is at least -4 by the condition on k. This contradicts assumption (2.13).

With the help of the two preceding claims, we can easily finish the proof. By Claim 1 and Rule 3, every special vertex-and hence every vertex-ends up with a nonnegative charge. The final charge of every face is nonnegative as well; Rule 2 and Claim 2 guarantee this for small and large faces respectively. However, as already mentioned, this contradicts Observation 2.6.

Lower bound

In this section, we provide examples showing that the best possible constant bound on χ s for the class of 2-connected plane simple graphs is at least 8, and the corresponding bound for proper spv-colorings is at least 10. Note that for the class of 2-connected plane (multi)graphs, the latter example implies a lower bound of 10 for general spv-colorings. Indeed, if we replace each of its edges by a digon bounding a face, then every spv-coloring of the resulting graph is necessarily a proper spv-coloring of the original simple graph.

First, we focus on the bound for proper spv-colorings. We construct a graph G 55 on ten vertices by linking two disjoint cycles C 1 , C 2 on five vertices with two additional edges whose endvertices in each cycle are adjacent. See Figure 3.1 (a).

By the spv-conditions for the two faces of G 55 of length 5, every proper spv-coloring c must assign each vertex of C 1 a different color; the same holds for C 2 . The spv-condition for the face of G 55 of length 10 then implies that c uses each color precisely once.

Second, we consider the bound on χ s (where the coloring is allowed to be improper). Take a three-sided prism G 3 embedded in the plane so that one of its triangular faces is the outer face f Finally, we reproduce the construction of G 55 with copies of G 4 in place of the cycles on five vertices. Thereby we obtain a graph G 44 with the outer face f 44 of length 8, such that every spv-coloring of G 44 is injective on V (f 44 ). The graph G 44 is shown in Figure 3.1 (c).

  x 4 v 4 into a single vertex v ′ 4 . It remains 2-connected due to statement (1), and hence by assumption, G ′ has a proper spv-coloring c with at most 97 colors. As v 1 and v ′ 4 are adjacent in G ′ , we obtain c(v 1 ) = c(v ′ 4

3 .

 3 As observed by Czap and Jendrol ' [3, proof of Lemma 5.1], every coloring

4 ( b )

 4b The graphs G 3 (left) and G 4 (right).

  The graph G 44 .

Figure 3 . 1 .

 31 Figure 3.1.Illustrations for Section 3. The labeled gray areas represent the respective subgraphs not depicted in detail. For each graph, the relevant coloring is unique up to symmetry; it is indicated by numerical labels.

* This work was supported by the Czech-Slovenian bilateral research project MEB 091037 and projects 201/09/0197 and P202/12/G061 of the Czech Science Foundation. † Department of Mathematics, Institute for Theoretical Computer Science (CE-ITI) and European Cen-Partially supported by Slovenian ARRS Program P1-00383 and Creative Core -FISNM -3330-13-500033.