Baptiste Hemery
email: baptiste.hemery@ensicaen.fr

Hélène Laurent
email: helene.laurent@ensi-bourges.fr

Bruno Emile
email: bruno.emile@univ-orleans.fr

Christophe Rosenberger
email: christophe.rosenberger@ensicaen.fr

Christophe Rosenberger Évaluation

Évaluation d'un résultat d'interprétation d'images

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

L'interprétation d'images concerne de nombreuses applications, notamment la détection de cibles et leur reconnaissance, l'imagerie médicale ou la vidéo surveillance. Quelle que soit l'application concernée, la qualité de l'extraction de l'information conditionne les performances de l'algorithme. Pour chaque objet d'intérêt, la qualité de la localisation et la reconnaissance est très importante. De nombreux algorithmes ont été proposés dans la littérature [START_REF] Cucchiara | Detecting moving objects, ghosts, and shadows in video streams[END_REF]; [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]; [START_REF] Jurie | Scale-invariant shape features for recognition of object categories[END_REF]; [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF]), mais il est encore difficile de comparer leurs performances.

Afin d'évaluer les algorithmes de détection et de reconnaissance d'objets, plusieurs compétitions ont vu le jour tels que le Pascal VOC Challenge [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2008[END_REF]) ou le projet Robin [START_REF] D'angelo | Robin challenge evaluation principles and metrics[END_REF]). Pour une vérité terrain donnée, ces compétitions utilisent des métriques afin d'évaluer et de comparer les résultats obtenus par différents algorithmes d'interprétation d'images. Si ces métriques font a priori appel à des caractérisations relevant du bon sens, aucune ne met en avant les mêmes caractéristiques. L'objectif de ces compétitions étant de comparer les algorithmes d'interprétation d'images en étudiant leur comportement global face à différents scénarios, il est primordial de disposer d'une métrique d'évaluation fiable.

De nombreuses métriques initialement proposées dans différents domaines peuvent se révéler utiles pour l'évaluation de résultats d'interprétation d'images. L'objectif de nos travaux est de mettre en concurrence ces métriques issues de contextes différents, afin de définir une métrique fiable d'évaluation de résultats d'interprétation prenant en compte la qualité de la détection, de la localisation et de la reconnaissance des objets. Dans l'exemple donné figure 1, nous aimerions ainsi pouvoir distinguer automatiquement le meilleur résultat d'interprétation. L'objectif de ce papier est de proposer une métrique permettant de combler ce manque. Cet article est organisé de la façon suivante : la première section présente les méthodes de la littérature, puis la seconde section présente la métrique développée. La troisième section est consacrée aux résultats que nous avons obtenus avec cette métrique. Enfin, nous concluons et présentons quelques perspectives.

1 État de l'art Nous présentons dans cette section un bref état de l'art des méthodes existantes d'évaluation supervisé, c'est à dire lorsque nous disposons de la vérité terrain, de la qualité de la localisation et de la reconnaissance d'objets dans une image.

Évaluation de la localisation

L'évaluation supervisée d'un résultat de localisation consiste à comparer deux images : la vérité terrain et le résultat de localisation. Plusieurs métriques ont été proposées pour cela [START_REF] Basseville | Distance measures for signal processing and pattern recognition[END_REF]; [START_REF] Wilson | A new metric for grey-scale image comparison[END_REF]; [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF]; [START_REF] Hafiane | A new supervised evaluation criterion for region based segmentation methods[END_REF]), avec des objectifs initiaux comme l'évaluation de la segmentation, et se révèlent utilisables dans le cadre de l'évaluation de résultats de localisation. Cependant, l'existence d'un grand nombre de métriques indique clairement le manque d'une métrique connue faisant le consensus.

Par ailleurs, trois modes de représentation d'un résultat de localisation sont utilisés. La plus simple est l'utilisation de boîtes englobantes, c'est-à-dire des rectangles présents dans l'image dont l'intérieure comprend l'objet recherché. Elles sont alors représentés pas un ensemble de coordonnées dans l'image. La seconde méthode consiste à utiliser des images représentant les pixels frontières, ou contour, des objets à localiser. Les pixels de ces images prennent leurs valeurs dans {0, 1}. Les 0 représentent l'objet et le fond de l'image qui sont délimités par les pixels frontières de valeur 1. Enfin, il est possible d'utiliser des images représentant une région d'intérêt, ou un masque. Les pixels des ces images prennent également leurs valeurs dans {0, 1}, les pixels 0 représentent le fond tandis que les pixels 1 représentent l'objet. Les trois types de représentation d'un résultat de localisation sont présentés à la figure 2. Quelques exemples de métriques d'évaluation de la localisation sont donnés ci-dessous, pour chaque type de représentation d'un résultat de localisation.

Le projet Robin [START_REF] D'angelo | Robin challenge evaluation principles and metrics[END_REF]) visait à évaluer des résultats d'interprétation. Cependant, la localisation et la reconnaissance sont évaluées séparément. La localisation est évaluée à partir d'une représentation par boîtes englobantes par les trois métriques suivantes : Dans un article précèdent [START_REF] Hemery | Comparative study of localization metrics for the evaluation of image interpretation systems[END_REF]), nous avons réalisé une étude comparative de 33 métriques d'évaluation de résultats de localisation, comprenant les métriques présentées ci-dessus. Pour cela, nous avons créé une base de données synthétiques contenant un total de 118 080 résultats de localisation. Les données ont été générées en prenant en compte quatre altérations : la translation, la mise à l'échelle, la rotation et la perspective. La figure 3 présente les quatre altérations appliquées au même objet original. Nous avons étudié les résultats d'évaluation au regard de quatre propriétés : la symétrie (une métrique doit pénaliser identiquement une altération dans une direction et dans celle opposée), la stricte monotonie (plus on altère un résultat de localisation par rapport à la vérité terrain, plus la métrique d'évaluation doit pénaliser cette altération), la continuité uniforme (le fait qu'il n'y ait pas de saut brusque dans l'évolution de la métrique d'évaluation) et la dépendance topologique (la métrique doit prendre en compte la forme et la taille des objets localisés). Notre conclusion était alors que les métriques exploitant une représentation basée région de l'objet permettent d'obtenir de meilleurs résultats. De plus, les métriques de Pascal [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2008[END_REF]) et de Martin et al. (2001) ont été jugées comme les plus pertinentes d'après notre étude.

ROB loc (BB l , BB vt ) = 2 π arctan(max( |x l -x vt | w vt , |y l -y vt | h vt )) (1) ROB com (BB l , BB vt ) = |A l -A vt | max(A l , A vt ) (2)

Évaluation de la reconnaissance

Nous avons vu qu'il était possible de quantifier la qualité d'un résultat de localisation étant donnée une vérité terrain. Nous souhaitons faire de même avec un résultat de reconnaissance. Cependant, il n'est pas possible de calculer directement une distance sur les labels renvoyés par les algorithmes, c'est-à-dire sur les identifiants numériques ou les chaînes de caractères renvoyés. En effet, ces identifiants sont des variables qualitatives non ordonnées et calculer une distance entre ces variables n'aurait pas de sens. Naïvement, la seule méthode permettant de calculer une distance sur ces variables est de regarder si celles-ci sont égales, et donc de dire que la distance est de 0 si les identifiants sont identiques et 1 sinon. Cette quantification reste peu précise et ne permet pas pondérer une erreur entre classes.

Il est intéressant de remarquer qu'il possible de calculer a priori, c'est à dire avant même d'avoir des résultats de reconnaissance à évaluer, l'ensemble des distances entre toutes les classes d'objets présentes dans la base de données ou application utilisées. En effet, le nombre de classes est limité et connu d'avance pour une application particulière. A titre d'exemple, nous souhaiterions que la distance entre les classes « chat » et « chien » soit plus petite que la distance entre les classes « voiture » et « chien ». L'ensemble de ces distances peut alors être stocké dans une matrice de distance MD ou matrice de similarité MS. Le problème est donc de calculer cette matrice.

Une façon de palier ce problème consiste alors à calculer la distance entre les descriptions des objets. La distance est alors dépendante de la méthode de représentation de l'objet. Par exemple, si l'objet est représenté par un histogramme, comme c'est le cas avec l'utilisation des méthodes se basant sur des sacs de mots, alors l'évaluation de la reconnaissance se fera en comparant les histogrammes des deux classes renvoyées par l'algorithme. Dans le cas d'une représentation des objets par un graphe, la distance d'édition peut être utilisée. Celle-ci peut être vue comme le coût d'édition du premier graphe G 1 pour le transformer en un graphe isomorphe au graphe G 2 . Cette édition se fait en une succession d'éditions élémentaires, chacune ayant un coût individuel. La distance d'édition est alors la somme des coûts nécessaires à cette transformation. Cette distance se révèle compliquée à calculer, aussi les algorithmes de [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF] ou de Riesen et al. (2007) peuvent-ils être utilisés afin d'accéder à une approximation de cette distance.

Évaluation de l'interprétation

Toutes les métriques d'évaluation proposées dans la littérature s'intéressent soit aux aspects de localisation soit aux aspects de reconnaissance des objets d'intérêt. Une métrique permettant d'évaluer un résultat d'interprétation, c'est-à-dire prenant en compte, en même temps, ces deux aspects n'existe pas à l'heure actuelle. Ceci est la principale contribution de ce papier.

La mise en correspondance

La mise en correspondance des objets permet de déterminer quels objets de la vérité terrain correspondent aux objets détectés par l'algorithme d'interprétation. Cette étape est nécessaire pour les deux étapes suivantes : le calcul des scores locaux et la compensation de la sous et surdétection. En effet, les objets sur-détectés correspondent à des objets présents dans le résultat d'interprétation qui ne correspondent à aucun objet de la vérité terrain. Les objets sous-détectés sont les objets présents dans la vérité terrain mais qui sont absents du résultat d'interprétation. Afin de faire cette mise en correspondance, nous calculons une matrice de recouvrement, de manière similaire aux travaux présentés par [START_REF] Phillips | Empirical performance evaluation of graphics recognition systems[END_REF]. Chaque ligne de la matrice correspond à un objet présent dans la vérité terrain, tandis que les colonnes correspondent aux objets présents dans le résultat d'interprétation. Dans la cellule (u, v), nous indiquons le recouvrement de l'objet u de la vérité terrain et de l'objet v du résultat d'interprétation. Le recouvrement est calculé avec la métrique P AS présentée dans la section précédente. La figure 5 2008). Nous utilisons l'algorithme hongrois [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF]) afin de calculer cette mise en correspondance. La deuxième méthode, dite « multiple », permet que chaque objet de la scène puisse être assigné à plusieurs objets dans la vérité terrain ou le résultat d'interprétation. Pour cela, nous faisons simplement un seuillage sur la matrice de recouvrement. Cela permet de prendre en compte, par exemple, le fait qu'un groupe d'objets soit reconnu comme un seul objet par l'algorithme. Cette méthode est utilisée dans [START_REF] Phillips | Empirical performance evaluation of graphics recognition systems[END_REF] ou [START_REF] Wolf | Object count/area graphs for the evaluation of object detection and segmentation algorithms[END_REF]. Après cette mise en correspondance, nous obtenons une matrice de correspondance, où un 1 dans une cellule (u, v) indique que l'objet u de la vérité terrain est mis en correspondance avec l'objet v du résultat d'interprétation. Par défaut, la méthode utilisée est la méthode « multiple » avec un seuil de 0, 2. Ces paramètres sont modifiables par l'utilisateur afin d'adapter la méthode d'évaluation en fonction de l'application visée.

Le calcul du score local

Pour chaque objet mis en correspondance, c'est-à-dire les cases (u, v) contenant un 1 dans la matrice de correspondance, nous calculons un score. Ce score est dit « local » car il correspond à l'évaluation d'un seul objet dans une scène en contenant potentiellement plusieurs. Il est calculé à partir de la qualité de la localisation et de la reconnaissance de l'objet. Le score local de localisation S loc est une version simplifiée pour un objet des métriques de [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF] qui ont montré leurs bonnes performances dans nos travaux précédents :

S loc (I vt , I i , u, v) = min   |I Re(u) vt\i | |I Re(u) vt | , |I Re(v) i\vt | |I Re(v) i |   (6) avec |I Re(u) vt
| le nombre de pixels de l'objet u présents dans la vérité terrain et |I

Re(u)
vt\i | le nombre de pixels de l'objet u présents dans la vérité terrain, mais pas dans le résultat d'interprétation. Ce score est compris entre 0 et 1, 0 indiquant un recouvrement parfait des deux objets (parfaite localisation).

Nous calculons ensuite un score pour la qualité de la reconnaissance. Pour cela, nous utilisons une matrice de distance entre les classes d'objets présentes dans la base de données. L'utilisateur doit fournir cette matrice de distance qu'il aura précédemment calculée ou, éventuellement, construite manuellement, comme nous l'avons vu dans la section 1.2. Si l'utilisateur ne fournit pas de matrice de distance, une matrice carrée contenant autant de lignes qu'il y a de classes dans la base de données est construite par défaut. Elle ne contient que des 1 avec des 0 sur la diagonale, soit la matrice (1 -δ i,j ), avec δ i,j le symbole de Kronecker. De plus, l'algorithme d'interprétation d'images peut fournir un indice de confiance pour chaque objet détecté. Le score est alors le suivant :

S rec (I vt , I i , u, v, µ) = M D(cl(u), cl(v)) * ind(cl(u), cl(v), µ) (7) avec ind(cl(u), cl(v), µ) = 1-µ 2 si cl(u) = cl(v) 1+µ 2 sinon (8)
et µ l'indice de confiance accordé au résultat de reconnaissance, M D la matrice des distance entre les classes et cl(u) la classe de l'objet u.

Suite à cela, nous calculons un score d'interprétation, qui est la combinaison de scores de localisation et de reconnaissance :

S(u, v, µ) = α * S loc (I vt , I i , u, v) + (1 -α) * S rec (I vt , I i , u, v, µ) (9)
Par défaut, la valeur du paramètre α est de 0, 8, mais l'utilisateur peut choisir de le modifier afin de donner plus de poids à la reconnaissance ou à la localisation. Nous avons choisi la valeur de 0, 8 afin de prendre davantage en considération la localisation que la reconnaissance étant donnée que la pénalisation par défaut de la reconnaissance est plus importante que celle de la localisation.

La compensation

Après avoir calculé un score pour chaque objet mis en correspondance, nous regardons les objets sous et sur-détectés. La sous-détection correspond à des lignes de la matrice de correspondance qui n'ont pas été associées à un objet du résultat d'interprétation, donc n'ayant pas de 1. De même, les objets sur-détectés vont correspondre à des colonnes de la matrice de correspondance qui n'ont été associées à aucun objet de la vérité terrain. Nous commençons par prendre en compte la sous-détection. Pour cela, on recherche la première ligne u sans association, puis pour cette ligne, on recherche la première colonne v sans association. On associe alors l'objet u à l'objet v dans la matrice de correspondance. Dans la matrice des scores locaux, le score de cette association est mis à 1 ce qui correspond à un mauvais score d'interprétation. On recommence ensuite jusqu'à ce que toutes les lignes soient associées. Pour la sur-détection, on fait le même travail en échangeant les lignes et les colonnes.

Le calcul de score global

Le score global est calculé à partir de la matrice des scores locaux, le score global étant alors la moyenne des scores locaux. même pour l'avion ainsi qu'une personne qui sont très clairement mis en correspondance. Le groupe de trois personnes correspond aux objets 2, 3 et 4 de la vérité terrain et à l'objet 3 du résultat de reconnaissance. Le score de recouvrement est donc moins important avec 0,235 et 0,242 pour 2 objets et 0,186 pour le dernier. Le seuil étant de 0,2, seulement 2 objets de la vérité terrain sont mis en correspondance avec l'objet du résultat d'interprétation. La seconde étape consiste à calculer les scores locaux obtenus pour chaque objet mis en correspondance. Pour cela, une matrice des scores de localisation est calculée, ainsi qu'une matrice des scores de reconnaissance. Pour la localisation, on peut voir que le groupe d'individus est bien localisé avec des scores de localisation inférieurs à 0,01 tandis que l'autre individu est le moins bien localisé avec un score de 0,065, ce qui reste un bon score de localisation. L'avion et le bus sont bien localisés avec des scores de localisation de 0,017 et 0,024. Pour la reconnaissance, nous pouvons voir qu'à l'exception du bus, les objets sont bien reconnus ce qui explique qu'ils aient un score de 0. Le bus étant reconnu comme un camion, son score est de 1. L'utilisation de d'une matrice de similarité à définir en fonction du contexte permettrait de réduire ce score étant donné que ces deux objets sont assez similaires. Une matrice de scores locaux est ensuite calculée comme la combinaison des deux matrices précédentes. Nous pouvons voir que le score du bus est fortement impacté par la mauvaise reconnaissance.

Illustration

La troisième étape est la compensation. On part pour cela de la matrice de correspondance afin d'identifier les lignes et/ou les colonnes n'ayant pas été affectées. Nous pouvons voir que toutes les colonnes contiennent au moins un 1, ce qui signifie que tous les objets du résultat d'interprétation ont été affectés à au moins un objet de la vérité terrain, et qu'il n'y a pas de sur-détection. Cependant, les lignes 2 et 7 sont vides, les objets correspondant dans la vérité terrain n'ont pas été convenablement détectés. Cette sous-détection est alors compensée en ajoutant des scores 1 dans les lignes correspondantes. Des colonnes sont ajoutées afin de ne pas affecter ces objets à des objets du résultat d'interprétation déjà correctement détectés.

La dernière étape consiste à calculer la matrice des scores locaux en prenant en compte la compensation. Cette matrice présente les scores locaux calculés précédemment en ajoutant les scores provenant de la compensation. A partir de cette matrice, on calcule le score moyen ce qui nous donne le score global. Dans notre cas, on calcule la moyenne de 7 scores obtenus : les 5 provenant de la mise en correspondance et les 2 provenant de la compensation. Le score final obtenu dans le cas étudié est de 0,328 (le score optimal correspond à la valeur nulle). Ce score est assez élevé car l'absence de détection de deux objets est très pénalisante : les objets manquants contribuent à hauteur de 0,285 et les objets présents à hauteur de 0,043.

3 Validation de la méthode

Protocole expérimental

Nous avons testé notre méthode d'évaluation globale sur une grande base de données dont les vérités terrain contiennent à la fois la localisation par des masques ainsi qu'une classe associée à chaque objet. Nous avons ensuite appliqué sur les objets issus de ces vérités terrain des altérations, puis nous avons étudié le comportement de notre méthode en fonction des différentes altérations. La suite de cette section présente la base de données ainsi que les altérations que nous avons appliquées aux vérités terrain. Cette base contient en tout 20 classes différentes : « avion », « bicyclette », « oiseau », « bateau », « bouteille », « bus », « voiture », « chat », « chaise », « vache », « table à manger », « chien », « cheval », « moto », « personne », « plante en pot », « mouton », « sofa », « train » et « télévision ». Nous avons ordonné ces classes selon les catégories de la base Caltech256 [START_REF] Griffin | Caltech-256 object category dataset[END_REF]), présentée à la figure 9, afin de créer la matrice de distance.

Altérations

Nous avons tout d'abord considéré les mêmes altérations que lors de l'étude comparative réalisée sur la localisation [START_REF] Hemery | Comparative study of localization metrics for the evaluation of image interpretation systems[END_REF]) : la translation, la mise à l'échelle, la rotation et enfin la perspective. Pour chacune de ces altérations, nous avons utilisé un paramètre d'altération allant de 1 à 20 dans deux directions différentes : horizontale et verticale pour les altérations de translation, mise à l'échelle et perspective, sens horaire et antihoraire pour la rotation. Cela a amené à créer 160 altérations pour chaque objet, soit un total de 341 440 altérations considérées. Nous avons ensuite simulé des erreurs de reconnaissance en altérant la classe des objets. Pour cela, nous avons remplacé la classe de 1 à tous les objets présents dans

Paramétrage

Nous nous sommes également intéressés à l'évolution de la métrique en fonction des différents paramètres de celle-ci. Nous avons alors regardé l'effet du choix de mise en correspondance ainsi que l'effet du seuil sur la méthode de mise en correspondance « multiple ». Nous avons donc comparé la mise en correspondance « un pour un » et « multiple », avec un seuil valant 0,2, 0,3, 0,4 et 0,5. Nous avons également regardé les effets de l'utilisation d'un indice de confiance pour la reconnaissance, ainsi que l'utilisation d'une matrice de similarité entre les différentes classes d'objets.

Résultats expérimentaux

Localisation

La figure 10 présente l'évolution moyenne de la métrique globale en fonction de différentes altérations de la localisation et selon le nombre d'objets présents dans la vérité terrain. Chaque courbe présente l'évolution de la métrique en fonction de la puissance d'altération de la localisation. La métrique est ici présentée avec les valeurs par défaut. Nous remarquons tout d'abord que plus le nombre d'objets dans la vérité terrain augmente et moins le critère est pénalisant. Ceci est normal puisque le score global est la moyenne des scores locaux. Ce résultat est donc correct et en adéquation avec la manière dont nous avons développé la métrique. Nous pouvons voir également que les propriétés définies dans la section 1.1 sont respectées. Quelle que soit l'altération considérée ou le nombre d'objets, les courbes sont uniformément régulières et strictement monotones. Nous pouvons voir que la métrique a bien la propriété de séparabilité également. De plus, bien que cela ne soit pas visible sur les courbes, la métrique est symétrique. Nous pouvons également remarquer que la translation et la rotation sont les deux altérations

Reconnaissance

Concernant la reconnaissance, nous avons étudié l'évolution de la métrique en fonction du nombre d'objets dont nous avons altéré la classe. Étant donné que nous travaillons avec les paramètres par défaut, la classe affectée à l'objet altéré n'a pas d'importance sur le résultat. Nous pouvons voir à la figure 11 l'évolution de la métrique globale en fonction du nombre d'objets altérés, les différentes courbes représentant le nombre d'objets dans la vérité terrain. Nous pouvons remarquer que la métrique évolue correctement puisque la pénalisation maxi-FIG. 11 -Résultats concernant la reconnaissance male, d'une valeur de 0,2 (1 -α, le paramètre α étant fixé par défaut à 0,8), est atteinte lorsque tous les objets de la vérité terrain ont été altérés.

Sous et sur-détection

Nous avons ensuite étudié l'effet de la sous et sur-détection sur l'évolution de la métrique globale. Nous avons étudié l'évolution de la métrique d'évaluation, avec les paramètres par défaut, en fonction du nombre d'objets supprimés de la vérité terrain ou bien ajoutés. La figure 12 présente l'évolution de la métrique en fonction du nombre d'objets altérés (les nombres négatifs indiquent les objets supprimés et les positifs les objets ajoutés) où chaque courbe correspond à un nombre d'objets dans la vérité terrain. Nous pouvons voir que ces situations sont correctement gérées et que la métrique est toujours plus pénalisante lorsque le nombre d'objets dans la vérité terrain est faible. Nous pouvons noter que la sous-détection est légèrement plus pénalisée que la sur-détection. Tout cela montre que la métrique, lorsqu'elle est utilisée avec les critères par défaut, donne de bons résultats. Cependant, il peut être intéressant de la paramétrer selon une application visée. La suite de cette section présente l'influence du paramétrage sur le comportement de cette métrique.

Paramétrage

Mode de mise en correspondance Le premier paramètre que nous avons considéré est le mode de mise en correspondance, ainsi que le seuil de mise en correspondance. Pour cela, nous nous sommes intéressés à l'évolution de notre métrique d'évaluation en fonction des quatre altérations de la localisation. Nous nous sommes limités à l'étude des vérités terrain contenant un seul objet. Chaque courbe de la figure 13 représente un paramétrage différent de la métrique. Nous pouvons remarquer sur les résultats obtenus que le paramétrage « multiple » est plus pénalisant que le paramétrage « un pour un ». De plus, plus le seuil est élevé, et plus les altérations sont pénalisées. Cela s'explique par le fait qu'il n'y ait qu'un seul objet par vérité terrain. Ainsi, la méthode « un pour un » associe toujours l'objet altéré à l'objet de la vérité terrain, tandis que la méthode « multiple » ne l'associera plus à partir d'une certaine altération, cela se produisant d'autant plus rapidement que le seuil est élevé. Notons également que cela

Discussion

Les résultats que nous avons obtenus avec la méthode proposée sont satisfaisants. Nous avons vu que la métrique permet de bien prendre en compte : (i) une mauvaise localisation, (ii) une mauvaise reconnaissance et (iii) une mauvaise détection. Il est à noter que les altérations sont pénalisées dans l'ordre d'importance suivant : d'abord la mauvaise détection, ensuite la reconnaissance puis la localisation. De même, parmi les altérations possibles de localisation, les problèmes de rotation et de translation sont pénalisés en priorité, suivis des problèmes de mise à l'échelle et enfin des problèmes de perspective.

Il est intéressant de remarquer que les cas des sur-et sous-détection sont traités à la fois par la mise en correspondance et la compensation. La mise en correspondance permet de gérer les cas où plusieurs objets sont détectés là où la vérité terrain n'en présente qu'un (et réciproquement), ce qui a peu d'impact sur la note finale. La compensation permet quant à elle de gérer les cas où des objets sont détectés là où aucun objet n'est présent dans la vérité terrain, ce qui a un fort impact sur la note finale.

Nous avons également vu que la méthode est paramétrable et que cela influe sur les résultats d'évaluation. Le mode de mise en correspondance « multiple » permet notamment de rendre la méthode d'évaluation plus sévère en augmentant le seuil. L'ajout de l'indice de confiance renvoyé par l'algorithme ainsi que l'utilisation de matrice de similarité permettent d'avoir un résultat d'évaluation plus fin.

Si nous reprenons les résultats d'interprétation de la figure 1

Conclusions et perspectives

Nous avons travaillé sur la création d'une métrique permettant l'évaluation d'un résultat d'interprétation. Cette métrique permet de prendre en compte à la fois les informations concernant la localisation et la reconnaissance des objets dans la scène. Cette métrique se base sur une mise en correspondance, le calcul d'un score local pour chaque objet mis en correspondance, puis le calcul d'un score global prenant en compte la sous et sur-détection. Nous avons créé cette métrique afin qu'elle soit paramétrable pour s'adapter à une application visée. Nous avons vu que la méthode de mise en correspondance peut être modifiée. De même, l'importance de la reconnaissance par rapport à la localisation peut être modifiée. Enfin, l'utilisation d'une matrice de distance, créée automatiquement ou manuellement, permet de grandement améliorer les performances de la méthode d'évaluation. Les résultats obtenus par notre méthode d'évaluation correspondent aux objectifs que nous nous étions fixés. Nous avons vu qu'elle pénalise correctement les différentes altérations possibles et permet donc de comparer plusieurs résultats d'interprétation de façon à faire ressortir le meilleur.

Les perspectives concernent en premier lieu la création automatique de matrice de distance depuis une base de données. Une autre perspective est de faire une étude subjective permettant de comparer les résultats d'évaluation de la métrique proposée et les résultats d'évaluations réalisées par des humains. Ainsi, nous serons en mesure de paramétrer la métrique afin qu'elle reproduise au mieux un comportement humain. Enfin, la dernière perspective est d'utiliser la métrique sur diverses applications pratiques d'interprétation d'images.

FIG. 1 -

 1 FIG. 1 -Exemples de résultats d'interprétation d'images (image originale et vérité terrain issues d'Everingham et al. (2008)) : les lignes rouges correspondent à la vérité terrain

  FIG. 2 -Différentes représentations d'un résultat de localisation

  FIG. 3 -Quatre images avec la même puissance d'altération (les lignes rouges représentent les contours de l'objet original, la région noire représente l'objet altéré)

  FIG. 4 -Schéma de l'évaluation globale d'un résultat d'interprétation

  présente l'ensemble I Re vt ∩ I Re i en vert tandis que l'ensemble I Re vt ∪ I Re i est la réunion des régions verte, bleue et rouge.

  FIG.5-La métrique PAS correspond à l'ensemble vert de pixels en commun divisé par l'ensemble des pixels localisés, c'est-à-dire vert, rouge et bleu

  FIG. 6 -Une image originale de la base Pascal VOC challenge 2007

  FIG. 8 -Images provenant de l'ensemble « Segmentation Taster Set »

FIG. 9 -

 9 FIG. 9 -Classes de la base Pascal 2008 représentées en utilisant la taxonomie de la base Caltech256

  FIG. 10 -Résultats concernant la localisation les plus pénalisées (à puissance d'altération égale), suivies par le changement d'échelle puis le changement de perspective. Ceci semble correct au regard de la figure 3, où toutes les images ont été altérées avec le même paramètre de 20. La métrique évolue donc correctement en ce qui concerne la localisation.

FIG. 12 -

 12 FIG.12 -Résultats concernant la sous et sur-détection

  FIG. 13 -Résultats concernant l'effet du paramétrage sur l'évaluation de la localisation

  et que nous les évaluons, nous obtenons les résultats présentés à la figure 16. Nous pouvons voir que le résultat (c) est le moins bon puisqu'il manque un objet. Suit le résultat (d), pour lequel il manque également un objet. Cependant, un objet du résultat d'interprétation chevauche deux objets de la vérité terrain, ce qui permet d'avoir une évaluation moins pénalisante que pour le résultat (c). Les résultats (a) et (b) obtiennent de meilleurs scores d'évaluation. Le premier ne contenant que des erreurs de localisation et aucune erreur de reconnaissance, il est mieux noté que le second. Des paramètres différents de ceux proposés par défaut permettraient d'avoir des résultats différents. Ainsi, avec une valeur différente du paramètre α, il serait possible de mettre en avant le résultat (d) qui ne présente aucune erreur de reconnaissance, peu d'erreur de localisation mais simplement un problème de détection.

  FIG. 16 -Exemples d'évaluation de résultats d'interprétation sur une scène (image originale tirée de Everingham et al. (2008)). Le résultat 1 est jugé comme le meilleur par la métrique proposée Enfin, il convient de remarquer que la métrique compare et donne une distance entre deux résultats d'interprétation. Pour effectuer une bonne évaluation d'un algorithme d'interprétation, l'un des deux résultats est en réalité une vérité terrain, c'est-à-dire un résultat d'interprétation idéale, fourni par des experts. Il est donc primordial d'avoir une bonne vérité terrain pour effectuer une bonne évaluation d'un algorithme. Cependant, la métrique présentée dans cet article peut également être utilisé pour comparer deux résultats d'interprétation provenant de deux algorithmes différents. Le résultat permettra alors de conclure si les deux algorithmes fournissent des résultats similaires, indépendamment de leur qualité.

Dans un article précèdent[START_REF] Hemery | Comparative study of local descriptors for measuring object taxonomy[END_REF]), nous nous sommes intéressés à la représentation d'un objet par un nuage de points de descripteurs. Ce nuage de points est ensemble des points détectés automatiquement sur l'image. Chacun de ses points est ensuite caractérisé par un vecteur calculé au voisinage de ce point. Pour construire ce nuage de points, nous avons alors utilisé les descripteurs SIFT proposés par[START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], afin de détecter et caractériser les points d'intérêt de l'objet. Disposant de deux images représentant des objets, nous avions donc deux nuages des points, chacun associé à un objet. Nous avons alors ensuite apparié les points du premier objet avec ceux du second lorsque cela était possible (en considérant la valeur du descripteur), puis nous avons défini une mesure de similarité basée sur le nombre d'appariements réalisés. Il est alors possible d'obtenir une mesure de similarité entre plusieurs classes d'objets en prenant les scores de similarité en moyenne sur une grande base d'apprentissage.Enfin, on pourra construire la matrice MD ou MS (si l'on utilise une mesure de similarité), soit en la remplissant manuellement de façon subjective, soit en utilisant une connaissance a priori comme une taxonomie ou une hiérarchie.

http://www.pascal-network.org/challenges/VOC/databases.html


Laurent Beaudou

Sylvain Gravier

Sandi Klavžar

Matjaž Kovše

Michel Mollard

Covering codes in Sierpi ński graphs

Keywords: codes in graphs, perfect codes, Sierpiński graphs 1365-8050

For a graph G and integers a and b, an (a, b)-code of G is a set C of vertices such that any vertex from C has exactly a neighbors in C and any vertex not in C has exactly b neighbors in C. In this paper we classify integers a and b for which there exist (a, b)-codes in Sierpiński graphs.

Introduction

In coding theory, a binary code is defined as a subset of {0, 1} n . Since a code should at least correct one error, the Hamming distance between any pair of code vertices must be at least 3. In terms of graph theory, we seek for a vertex subset C of the n-cube Q n , such that d(u, v) ≥ 3 for any u, v ∈ V (Q n ), u = v. (As usual, d(u, v), is the shortest-path distance between u and v.)

The above concepts can be extended from hypercubes to arbitrary graphs. Let G be an arbitrary (connected) graph. Then a subset C of vertices of G is called a 1-code (or simply a code) if d(u, v) ≥ 3 holds for any u, v ∈ C, u = v. Moreover, C is a perfect code provided that the closed neighborhoods of elements of C form a partition of V . It was Biggs [START_REF] Biggs | Perfect codes in graphs[END_REF] who initiated the study of perfect codes in distance regular graphs. Kratochvíl with his co-workers follows with the study of codes in general graphs, see the monograph [START_REF] Kratochvíl | Perfect Codes in General Graphs[END_REF], references therein, and [START_REF] Hedetniemi | Complexity results[END_REF] for result on the related complexity issues.

Tower of Hanoi graphs model the classical Tower of Hanoi puzzle with 3 pegs and n discs. Their nice fractal structure enables to observe many nice properties. In particular, Cull and Nelson [START_REF] Cull | Error-correcting codes on the Towers of Hanoi graphs[END_REF] proved that they contain (essentially) unique perfect codes, see also [START_REF] Li | Perfect codes on the Towers of Hanoi graphs[END_REF]. The Tower of Hanoi graphs extend naturally to graphs S(n, k), n, k ≥ 1, where S(n, 3) are isomorphic to the graphs of the puzzle with 3 pegs and n discs. The theorem of Cull and Nelson was extended to S(n, k) in [START_REF] Klavžar | 1-perfect codes in Sierpiński graphs[END_REF], see also [START_REF] Gravier | Codes and L(2, 1)-labelings in Sierpiński graphs[END_REF] where in particular shorter arguments are provided.

In [START_REF] Cohen | Weighted covering and packings[END_REF], Cohen, Honkala, Lytsin and Mattson introduced a generalization of covering codes using weights and named them weighted codes. For a study of small radius weighted coverings see [3]. Independently, Axenovich [START_REF] Axenovich | On multiple coverings of the infinite rectangular grid with balls of constant radius[END_REF] studied some special cases of perfect weighted codes calling them (t, i, j)-coverings.

In order to have a more convenient definition of perfect weighted coverings of radius one, (a, b)-codes were introduced in the following way [START_REF] Dorbec | Weighted codes in Lee metrics[END_REF]. Let G be a graph and a, b nonnegative integers. Then a set C of vertices of G is an (a, b)-code of G if any vertex from C has exactly a neighbors in C and any vertex from G \ C has exactly b neighbors in C. Defined in this way, an (a, b)-code is exactly a perfect ( b-a b , 1 b )-covering as defined in [START_REF] Cohen | Weighted covering and packings[END_REF]. Moreover, (1, i, j)-coverings from [START_REF] Axenovich | On multiple coverings of the infinite rectangular grid with balls of constant radius[END_REF] are exactly (i -1, j)-codes. Finally, Telle defines [i, j]-dominating sets in [START_REF] Telle | Complexity of domination-type problems in graphs[END_REF] which are exactly (i, j)-codes, see also [START_REF] Fiala | Generalized H-coloring and H-covering of trees[END_REF]. We will simply speak about (a, b)-codes when referring to such sets.

Graphs S(n, k), n, k ≥ 1, form a two-parametric family of graphs of fractal type and have been wellstudied by now. (See the next section for their definition and basic properties.) In this paper we give a characterization of the parameters n and k for which S(n, k) admits an (a, b)-code. Since S(n, 1), n ≥ 1, and S(1, k), k ≥ 1, are of no special interest, let us assume in the rest that n ≥ 2 and k ≥ 2. Then our main result is the following. Theorem 1.1 Let n, k ≥ 2. Then S(n, k) contains an (a, b)-code if and only if a < k and one of the following cases holds:

(i) a ≥ 1, b = a, k even; (ii) a ≥ 2 even, b = a, k odd; (iii) a = 0, b = 1; (iv) a ≥ 1, b = a + 1, n odd; (v) a ≥ 1, b = a + 2, n = 2, k = 2a + 1.
Note that (0, 1)-codes coincide with perfect codes. Indeed, if two vertices from a (0, 1)-code would be at distance 2, then their common neighbor would have two neighbors in the code. Hence Theorem 1.1 (iii) covers the before mentioned result on perfect codes in graphs S(n, k).

We proceed as follow. In the next section we introduce and describe graphs S(n, k). Then, in Section 3, we give necessary conditions on a and b for the existence of (a, b)-codes in graphs S(n, k). In the subsequent sections we construct the claimed (a, a), (a, a + 2), and (a, a + 1)-codes, therefore completing the proof of the Theorem 1.1. We conclude with some ideas for further research.

(i) i t = j t , for t = 1, . . . , h -1;

(ii) i h = j h ; and (iii) i t = j h and j t = i h for t = h + 1, . . . , n.

In the rest of the paper we will write i 1 i 2 . . . i n as short for (i 1 , i 2 , . . . , i n ). The graphs S(2, 3), S(3, 3), and S(2, 4) are shown in Fig. 1. Note that the graph S(n, 1), n ≥ 1, has only one vertex, that is, S(n, 1) = K 1 . On the other hand, if n = 1, then S(1, k) = K k .

A vertex of the form ii . . . i of S(n, k) is called extreme, other vertices are inner. The set of extreme vertices of S(n, k) will be denoted X(S(n, k)). Note that the extreme vertices of S(n, k) are of degree k -1 and the degree of the inner vertices is k. Note also that |X(S(n, k)

)| = k and that |S(n, k)| = k n .
Finally, for a vertex u = i 1 i 2 . . . i n of S(n, k) let K(u) denote the k-clique induced by vertices i 1 i 2 . . . i n-1 j , 1 ≤ j ≤ k.

Necessary conditions

In this section we restrict the possible couples (a, b) for which (a, b)-codes in graphs S(n, k) are possible.

Note that S(n, 2) is isomorphic to the path on 2 n vertices. The only possible (a, b) codes for them are (0, 1), (1, 1) and (1, 2). More precisely, P 2 n has a (0, 1)-code and a (1, 1)-code for any n ≥ 1, while it contains a (1, 2)-code if and only if n is odd. In the latter case, such a code is 1 101 101 • • • 101 1, where 1 denotes code vertices. Hence Theorem 1.1 holds for k = 2, in particular, item (iv) is covered with the (1, 2)-codes for odd n. We will therefore assume in the rest that k ≥ 3. Proof: Suppose b = 0. Then it follows that C = V (S(n, k)), which is neither a (k, 0)-code nor a (k -1, 0)-code. Therefore b > 0.

Clearly a ≤ k. Suppose a = k and let x ∈ X(S(n, k)). Since x has degree k -1, it is not in the code. Consider y a neighbor of x. Since n ≥ 2, y has degree k, and at least one of them is not in the code (namely x). Therefore, y cannot have a neighbors in the code and y is not in the code. Thus, none of the neighbors of x is in the code and b = 0, which is not possible, as shown at the beginning of the proof.

2 Lemma 3.2 Let C be an (a, b)-code in S(n, k) and K k any of its k-cliques. Then b -1 ≤ |C ∩ K k | ≤ a + 1 . Proof: If there is a clique K k with |C ∩K k | > a+1, then any vertex v ∈ C ∩K k satisfies |N (v)∩C| > a, which yields a contradiction.
Since n ≥ 2, S(n, k) is not regular and thus, the code cannot be the whole graph. There exists a vertex u which is not in C. Consider the clique K(u). Then u has at most one neighbor not in K(u) and

|C ∩ K(u)| ≥ b -1 so that b ≤ k. Consider a clique K k . Either there is a vertex v in K k \ C and the preceding study yields |C ∩ K k | ≥ b -1, or K k ⊂ C and |C ∩ K k | = k > b -1. 2 Lemma 3.3 Let C be an (a, b)-code of S(n, k) with d extreme vertices in C. Then |C| • (k -a + b) = bk n + d . Proof: Consider the bipartite subgraph B of S(n, k) with bipartition V 1 = C and V 2 = V (S(n, k)) \ C, keeping only the edges between V 1 and V 2 . Every vertex in V 2 has degree b in B. Let v be a vertex in X(S(n, k)) ∩ V 1 . Then its degree in B is k -a -1. Other vertices of V 1 have degree k -a.
Then counting the number of edges in B in two ways we have

|C| • (k -a) -d = (k n -|C|) • b ,
from which the lemma follows. 2

Corollary 3.4 Let C be an (a, b)-code of S(n, k) without extreme vertices. Then (k -a + b)|bk n . Lemma 3.5 Let C be an (a, b)-code of S(n, k). Then a ≤ b.
Proof: If a = 0, the statement holds trivially. We now assume a > 0.

Suppose first that there exists u ∈ X(S(n, k)) \ C. Then u is adjacent to b vertices in K(u). An arbitrary code vertex from K(u) has b -1 neighbors in K(u) ∩ C and, maybe, one more in C. Thus a ≤ b. Now, suppose X(S(n, k)) ⊂ C. Let u be an extreme vertex of S(n, k). Let w = u be a vertex in C ∩ K(u), such a vertex exists since a > 0. Then the neighbor x of w, x / ∈ K(u), does not belong to C, for otherwise w would be adjacent to more code vertices than u. Hence x is adjacent precisely to b -1 code vertices in K(x).

If b > 1, each code vertex of K(x) has at most one other neighbor in

C \ K(x). Thus a ≤ (b -2) + 1 = b -1.
Else, b = 1. Therefore any clique K k contains either 0, 1 or k vertices of the code. Since K(u) contains u and w, it means that K(u) ⊂ C. Let v be another neighbor of u (we recall that k ≥ 3), it is in the code and its neighbor y not in K(u) is not for the same reason as x. Since y and x have already one neighbor in the code, we may state that K(x) and K(y) contain no vertex of the code. Consider vertices x and y linking these two cliques. They have no neighbor in the code which is impossible. Thus we may conclude that b > 1.

2

Note that in the proof of Lemma 3.5 we need k > 2 when we study the case b = 1. However, we have assumed in the beginning of the section that this is indeed the case.

From Lemmas 3.2 and 3.5 we deduce that the only possible (a, b)-codes are (a, a), (a, a + 1), and (a, a + 2). Next we will obtain some additional necessary conditions for the existence of such codes. Lemma 3.6 If a and k are odd then there is no (a, a)-code in S(n, k).

Proof: Let C be an (a, a)-code in S(n, k) with a odd, and k odd.

Suppose first that there is some x ∈ X(S(n, k)) ∩ C. Since a is odd, a ≥ 1, there exists a vertex y ∈ K(x) ∩ C, y = x. Since k ≥ 3, there exists another vertex v in K(x). Either it is in C and a > 1 or it is not in C and has at least two neighbors in the code so that a ≥ 2. Let z be the neighbor of y that is not in K(x). Then z / ∈ C, for otherwise y would be adjacent to more code vertices than x. Now, in K(z), z has a -1 neighbors from C. Since a -1 > 0 we can consider such a vertex. It can have at most a -1 adjacent code vertices. It follows that there is no extreme vertex in C.

We next claim that for any vertex u, |K(u) ∩ C| = a. By way of contradiction, suppose that there is a vertex u such that |K(u)∩C| < a. Then, by Lemma 3.2, we get |K(u)∩C| = a-1. Then x ∈ K(u)∩C is adjacent to at most a -1 code vertices, a contradiction.

We have thus shown that for every vertex u, |K(u) ∩ C| = a. Since we have assumed that k ≥ 3, the number of k-cliques in S(n, k) is k n-1 . Thus the above implies that |C| = a • k n-1 . Because the subgraph induced by C is a-regular with a odd, it means that |C| must be even. But a • k n-1 is odd. 2 Note that it follows from the above proof that no extreme vertex can belong to an (a, a)-code for any a ≥ 1. Lemma 3.7 If an (a, a + 2)-code exists in S(n, k), then n = 2 and k = 2a + 1.

Proof: By Lemma 3.2, |C ∩ K k | = a + 1 for any k-clique K k . Thus |C| = k n-1 • (a + 1) .
On the other hand, Lemma 3.3 implies that

|C| • (k -a + (a + 2)) = k n-1 • (a + 1) • (k + 2) = k n • (a + 2) + d ,
where 0 ≤ d ≤ k. Dividing both sides of the equality by k n-1 we arrive at

2a + 2 -k = d k • 1 k n-2 .
By the right-hand side of the last equality we infer that this number is between 0 and 1 (recall that n ≥ 2), and by the left side of the equality it is an integer, thus it can only be 1 or 0.

The first case implies n = 2, d = k and k = 2a + 1. The second case is impossible, because it implies d = 0, thus extreme vertices would have in this case exactly a + 1 neighbors in the code. 2

4 Existence results for (a, a) and (a, a + 2)

In this section we construct (a, a)and (a, a + 2)-codes. We first observe the following useful fact. (i) a is even or (ii) a is odd and k is even.

Proof: By Lemma 3.6, a and k cannot both be odd if an (a, a)-code exists. Moreover, we have observed that no extreme vertex belongs to such a code. Hence by Lemma 4.1 it suffices to prove the existence of codes for the graphs S(2, k) when at least one of a and k is even. We distinguish two cases.

Case 1. a = 2p. We claim that

C = {ij | j = i ± ε (mod k), 0 ≤ i ≤ k -1, 1 ≤ ε ≤ p} is an (a, a)-code in S(2, k). Let ij ∈ C. Then there exists ε, 1 ≤ ε ≤ p, such that j = i ± ε (mod k). Without loss of generality let j = i + ε (mod k) (the proof follows similar lines if j = i -ε (mod k)). Neighbors of ij in K( ij ) ∩ C are of the form il with l ≡ i ± ε (mod k), where ε = ε, 1 ≤ ε ≤ p,
= 2q. We claim that C = { ij | j = i ± ε (mod k), 0 ≤ i ≤ k -1, 1 ≤ ε ≤ p} ∪ { il | 0 ≤ i ≤ k -1, l = i + q (mod k)
} is an (a, a)-code in S(n, k). By Lemma 3.1, a < k and it follows 2p + 1 < 2q and therefore p < q. Let ij ∈ C. Then ij has 2p neighbors in K( ij ) ∩ C. Moreover for vertex ji it follows that ji ∈ C, since i + q ≡ iq ( mod k). Hence ij has precisely 2p + 1 = a neighbors in C.

Let ij / ∈ C. Then ij has precisely 2p + 1 = a neighbors in K( ij ) ∩ C and its neighbor ji does not belong to C. Therefore C is an (a, a)-code in S(2, k).

Note finally that in both cases C contains no extreme vertex, hence Lemma 4.1 applies.

2

Combining Lemma 3.3 with the fact that an (a, a)-code contains no extreme vertices we infer:

Corollary 4.3 Let C be an (a, a)-code in S(n, k). Then |C| = a • k n-1 .
Lemma 4.4 S(2, 2a + 1) contains an (a, a + 2)-code.

Proof: Let Q be the complete graph on k = 2a + 1 vertices and let 1, 2, . . . , 2a + 1 be its vertices. Then Q is an Eulerian graph and let v 1 , . . . , v a(2a+1) be an Eulerian tour T in Q. Using T we describe an (a, a + 2)-code C in S(2, k) as follows.

First set ii ∈ C for all i = 0, . . . , k -1. In addition, for j = i set ij ∈ C if and only if there is some t such that v t = i and v t+1 = j (where subscript are modulo a(2a + 1)). Note that ji ∈ C. (The construction is illustrated in Fig. 2 where a (2, 4)-code is constructed in S(2, 5) using an Eulerian tour in K 5 .)

Second, let ij ∈ C. By definition of an Eulerian tour, the edge ij of Q must belong in one way in T . Since ij ∈ C, there must be some t such that v t = j and v t+1 = i. Then ij has a + 1 neighbors in C ∩ K( ij ) plus a neighbor ji .

Therefore C is an (a, a + 2)-code of S(2, k). 2

One may remark that if there is an (a, a + 2)-code C in S(2, 2a + 1) then all extreme vertices must belong to C moreover from C one may exhibit an Eulerian tour of K 2a+1 (contract all vertices of C belonging to the same (2a + 1)-clique and consider the orientation of the edges between different cliques of S(2, 2a + 1), where an edge is always oriented from a vertex in the code to the vertex not in the code). So all (a, a + 2)-codes in S(2, 2a + 1) are obtained by the construction given in the proof of Lemma 4.4.

Corollary 4.5 Let C be an (a, a + 2)-code in S(2, 2a + 1). Then |C| = 2a 2 + 3a + 1.

Case of (a, a + 1)-code

To settle the case of (a, a + 1)-codes in Theorem 1.1, we prove a stronger result. Before we need some additional definitions. Given a set C of vertices of a graph G and a vertex x, let

w(x) = a -|N (x) ∩ C|; x ∈ C, a + 1 -|N (x) ∩ C|; otherwise .
be the weight of x. (The weight of x is also a function of C and a (and of G), but since these will be clear from the context we write simply w(x).) Then we say that a subset C of vertices of S(n, k) is a near code if w(x) = 0 for all x ∈ V (S(n, k))\X(S(n, k)), and w(x) ≤ 1 for vertices x in X(S(n, k)). Given n and k, we denote S i (n, k) (for short S i ) the subgraph of S(n, k) induced by { ii 2 . . . i n for all i 2 , . . . , i n ∈ {0, . . . k -1}} . The graph S i is isomorphic to S(n -1, k).

: 0 → 1 → 2 → 3 → 4 → 0 → 2 → 4 → 1 → 3 → 0 0 1 2 3 4
From the definition of the near code and since the only edges between S i and G -S i are incident to extreme vertices of S i , we have that C ∩ V (S i ) is a near code in S i if C is a near code in S(n, k).

We denote by • extreme vertices that lie in the near code and by • the other extreme vertices. Furthermore, we add the subscript * for a vertex of weight 0 and the subscript + for weight 1. For example, • + is an extreme vertex which is not in the code and which has a neighbors in the code. Let us now define the following special near codes C:

• SO n is a near code where n is odd, a + 1 many extreme vertices are • * , the other ka -1 extreme vertices are • * .

• W O n is a near code where n is odd, a many extreme vertices are • + , the other ka extreme vertices are • +

• SE n is a near code where n is even, a many extreme vertices are • + , the other ka extreme vertices are • * .

• W E n is a near code where n is even, a + 1 many extreme vertices are • + , the other ka -1 extreme vertices are • * Note that by definition SO n is an (a, a + 1)-code. Now we are ready to state:

Theorem 5.1 Let n ≥ 1, a ≥ 0 and k > a be integers. The near codes of S(n, k) are precisely SO n and W O n if n is odd and SE n and W E n if n is even.

Proof: Let C be a near code of S(n, k) with n ≥ 2. The main argument of the proof is that the only possible matchings between extreme vertices of different subgraphs S i , 0 ≤ i ≤ k -1, are :

• + -• + , • * -• * and • * -• + .
The proof works by induction on n.

For n = 1, it is clear that any near code in the clique K k is a set of a or a + 1 vertices which give respectively a W O 1 and a SO 1 code.

Further we divide induction step into two cases, according to the parity of n. Assume first that n is odd. Suppose that there is an extreme vertex x of kind • + . Without loss of generality one may assume that x belongs to S 1 . By induction hypothesis, C ∩ S 1 is isomorphic to SE n-1 . Now for each extreme vertex y = x of S 1 of kind • + we need an S i containing a • + as extreme vertex. Therefore, there are a -1 graphs S i such that S i ∩ C is isomorphic to SE n-1 . Similarly, for the • * extreme vertices of S 1 , we need ka graphs S j having extreme vertex of kind

• + which implies that S j ∩ C is isomorphic to W E n-1 .
Now to obtain a near code, each remaining • + not in an extreme vertex of S(n, k) must be matched together in an arbitrary way. Since there are a graphs S i containing a extreme vertices • + and only one edge between two distinct S i , it implies that each extreme vertex of S(n, k) belonging to some S i must be • + . Now, the ka other S j contain a + 1 extreme vertices • + . If such a vertex is not extreme in S(n, k) it must be matched to a • * vertex. Since we have only (ka) • a vertices of kind • * , it follows that each S j must contain an extreme vertex • + of S(n, k). Hence in this case we get C = W O n .

If C contains a • + the proof goes along similar lines as above. Suppose next that there is an extreme vertex x of kind • * . Without loss of generality one may assume that x belongs to S 1 . By induction hypothesis, C ∩ S 1 is isomorphic to SE n-1 . Now for each extreme vertex of S 1 of kind • + we need an S i containing a • + as extreme vertex. Therefore, there are a additional graphs S i such that S i ∩ C is isomorphic to SE n-1 (altogether there a + 1 such graphs). Similarly, for the • * extreme vertex y = x of S 1 , we need ka -1 graphs S j having extreme vertex of kind • + which by induction hypothesis implies that S j ∩ C is isomorphic to W E n-1 .

To obtain a near code, each remaining • + not an extreme vertex of S(n, k) must be matched together. Since there are a + 1 graphs S i containing a extreme vertices • + and only one edge between two distinct S i , it implies that each extreme vertex of S(n, k) belonging to some S i must be • * . The ka -1 other S j graphs contain a + 1 extreme vertices • + . If such a vertex is not extreme in S(n, k) it must be matched to a • * vertex. We have exactly (ka -1) • (a + 1) vertices of kind • * that are not in X(S(n, k)) ( and are from (a + 1) SE n-1 graphs) and the same number of • + vertices -a + 1 of them in each of ka -1 copies of W E n-1 , hence they can be matched together. Also the remaining vertices • * can be matched together where ka -1 of such vertices belong to X(S(n, k)). Therefore C = SE n , in particular C is an (a, a + 1)-code in S(n, k).

If C contains a • * the arguments are similar. Next let n be even and n ≥ 2. Suppose that there is an extreme vertex x of the kind • * . Without loss of generality one may assume that x belongs to S 1 . By induction hypothesis, C ∩ S 1 is isomorphic to SO n-1 . Now for each extreme vertex y = x of S 1 of kind • * we need an S i containing a • + as extreme vertex. Therefore, there are a graphs S i such that S i ∩ C is isomorphic to W O n-1 . Similarly, for the • * extreme vertices of S 1 , we need ka -1 graphs S j having extreme vertex of kind • * which implies that S j ∩ C is isomorphic to SO n-1 .

To obtain a near code, each of the remaining • + vertices that are not extreme vertices of S(n, k) must be matched together. Since there are a graphs S i containing a extreme vertices • + and only one edge between two distinct S i . It follows that each extreme vertex of S(n, k) belonging to some S i , that is of type W O n-1 must be • + . Altogether there are a extreme vertices • + of S(n, k). The remaining unmatched vertices from SO n-1 are all • * and there is precisely one from each component, hence there are ka such extreme vertices in S(n, k). It follows C = SE n .

When C contains a • + the proof works similarly. Suppose finally that there is an extreme vertex x of kind • * . Without loss of generality one may assume that x belongs to S 1 . By induction hypothesis, C ∩ S 1 is isomorphic to SO n-1 . Now for each extreme vertex y of S 1 of kind • + , y = x, we need an S i containing a • + as extreme vertex. Therefore, there are ka -2 additional graphs S i such that S i ∩ C is isomorphic to SO n-1 (altogether there ka -1 such graphs). Similarly, for the • * extreme vertex of S 1 , we need a + 1 graphs S j having extreme vertex of kind • * which by induction hypothesis implies that S j ∩ C is isomorphic to W O n-1 . Now to obtain a near code, each remaining • + not an extreme vertex of S(n, k) must be matched together. Since we have ka -1 graphs of type SO n-1 and in each of those graphs the same number of vertices • + , it follows that among extreme vertices of S(n, k) there are ka -1 vertices of type • + . Similarly we can conclude that the remaining a + 1 vertices of X(S(n, k)) are • * . It follows C = W E n .

Again, if C contains a • + the proof works similarly. Hence we have completed the induction step and hence the proof.

2

The recursive construction of an (1, 2)-code in S(3, 3) is illustrated in Fig. 3. The next consequences are immediate.

Concluding remarks

We have thus characterized integers a, b for which there exist (a, b)-codes in graphs S(n, k). For the case of (0, 1)-codes, that is, perfect codes, the uniqueness (modulo obvious symmetries) has been proved in [START_REF] Klavžar | 1-perfect codes in Sierpiński graphs[END_REF]. As exhibited in our paper all existing (a, b)-codes of graphs S(n, k), n ≥ 2, are constructed in a unique way from (a , b )-codes of graphs S(n -1, k) or their weak codes, where the unique means that there are always the same k building blocks of graphs S(n -1, k) with corresponding (weak) codes.

(Graphs S(n -1, k) might have, comparing to each other, different types of weak codes, as in the case of (a, a + 1)-codes, but altogether the set of all k graphs S(n -1, k) with the corresponding (weak) codes is as a set always the same.) Different types of extreme vertices of graphs S(n -1, k) are matched together in S(n, k) in a unique way. As shown in [START_REF] Klavžar | Crossing numbers of Sierpiński-like graphs[END_REF], the automorphism group of a graph S(n, k) is isomorphic to the symmetric group Sym(k), where any automorphism of S(n, k) permutes extreme vertices and the corresponding subgraphs S(n -1, k). It follows that also all existing (a, b)-codes in graphs S(n, k) are unique up to symmetries. A more precise description (using labels) of the constructed (a, a + 1)-codes would be of interest.

SO 1 SO 1 SO 1 W O 1 W O 1 W O 1 W O 1 SE 2 SE 2 W E 2

Fig. 1 :

 1 Fig. 1: S(2, 3), S(2, 4), and S(3, 3)

Lemma 3 . 1

 31 Let C = ∅ be an (a, b)-code in S(n, k). Then a < k and b > 0.

Lemma 4 . 1 2 Lemma 4 . 2

 41242 Suppose there exists an (a, b)-code in S(2, k) that does not include any of the extreme vertices. Then there exists (a, b)-codes in S(n, k) for all n ≥ 3.Proof: Suppose S(2, k) contains an (a, b)-code that includes none of the extreme vertices. We extend this code inductively to S(n, k) for all n ≥ 3 as follows. Let n ≥ 3 and suppose that S(n -1, k) contains an (a, b)-code C that does not include any of its extreme vertices. We extend C to C by settingi 1 i 2 . . . i n ∈ C if and only if i 2 . . . i n ∈ C.It is now straightforward to see that C is an (a, b)-code in S(n, k) that does not include any of the extreme vertices. Let n ≥ 2 and a < k. Then an (a, a)-code of S(n, k) exists if and only if

  and one more additional neighbor iiε . Since by Lemma 3.1, a < k, it follows that p < k and vertex ij has precisely 2p -1 neighbors in K( ij ) ∩ C. Moreover ij is also adjacent to ji ∈ C. Therefore ij has exactly 2p = a neighbors in C. Let ij / ∈ C. First we observe that the vertex ii has 2p neighbors in C. Second, if i = j it follows that (ji) (mod k) > p, since ij / ∈ C. Then ij has 2p neighbors in K( ij ) ∩ C and vertex ji which is the neighbor of ij not belonging to the clique K( ij ) also does not belong to C. Therefore C is an (a, a)-code in S(2, k). Case 2. a = 2p + 1 and k

  in K 5

Fig. 2 :

 2 Fig. 2: A (2, 4) code (black vertices) in S(2, 5) obtained via an Eulerian tour in K5

Corollary 5 . 2 1 . 5 . 3

 52153 Graphs S(n, k) admits an (a, a + 1)-code if and only if n is odd and 0 ≤ a ≤ k -Corollary Let C be an (a, a + 1)-code in S(n, k), where n is an odd number. Then |C| = (a + 1) • k n +1 k+1 .

Fig. 3 :

 3 Fig. 3: Recursive construction of an (1, 2)-code in Sierpiński graph S(3, 3).

Acknowledgements

This research was supported in part by the Slovene-French project Proteus 17934PB. Sandi Klavžar and Matjaž Kovše were also supported in part by the Ministry of Science of Slovenia under the grant P1-0297.


Mieczyslaw Borowiecki

Anna Fiedorowicz
email: a.fiedorowicz@wmie.uz.zgora.pl

Katarzyna Jesse-Jozefczyk
email: k.jesse-jozefczyk@wmie.uz.zgora.pl

Elzbieta Sidorowicz
email: e.sidorowicz@wmie.uz.zgora.pl

Mieczysław Borowiecki

Katarzyna Jesse-Józefczyk

Elżbieta Sidorowicz

Acyclic colourings of graphs with bounded degree

Keywords:

  L'archive ouverte pluridisciplinaire

Introduction and notation

All graphs, which we consider, are finite and simple. For a graph G we denote its vertex set by V (G) and its edge set by E(G). The set of neighbours of a vertex v ∈ V (G) is denoted by N G (v), or briefly by N (v). Let ∆(G) denote maximum degree of G. Let W ⊆ E(G). We denote by G[W ] the subgraph of G induced by the set W .

For any k ≥ 0, we denote by S k the class of all graphs of maximum degree at most k. Furthermore, we say that a graph G is subcubic if G ∈ S 3 . Let D 1 denote the class of all acyclic graphs.

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours. We can also regard a k-colouring of G as a partition of the set V (G) into colour classes V 1 , . . . , V k such that each V i is the set of vertices coloured with i.

Let P 1 , P 2 , . . . , P k be nonempty classes of graphs. A k-colouring of a graph G is called a (P 1 , P 2 , . . . , P k )-colouring of G if for every colour 1 ≤ i ≤ k the subgraph induced in G by the colour class V i belongs to P i . Such a colouring is called an acyclic (P 1 , P 2 , . . . , P k )-colouring, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with colour i and a vertex coloured with colour j is acyclic. In other words, every bichromatic cycle in G contains at least one monochromatic edge. A bichromatic cycle (path) having no monochromatic edge will be called an alternating cycle (path). The acyclic (P 1 , P 2 , . . . , P k )-colouring is called an acyclic k-colouring if for each i, 1 ≤ i ≤ k, the class P i is the set of all edgeless graphs. The minimum k such that G has an acyclic k-colouring is called the acyclic chromatic number of G, denoted by χ a (G).

The acyclic chromatic number and acyclic k-colouring have been investigated by many authors. In [START_REF] Grűnbaum | Acyclic coloring of planar graphs[END_REF] Grünbaum showed that the acyclic chromatic number of any subcubic graph is at most 4. In [START_REF] Skulrattanakulchai | Acyclic colorings of subcubic graphs[END_REF] a linear time algorithm that uses at most 4 colours to acyclically colour vertices of such graph is presented. Burstein [START_REF] Burstein | Every 4-valent graph has an acyclic 5-coloring[END_REF] proved that the acyclic chromatic number of graphs of maximum degree 4 is at most 5. In 1978 Kostochka [START_REF] Kostochka | Upper bounds of chromatic functions of graphs[END_REF] proved that it is an NP-complete problem to decide for a given graph G if χ a (G) ≤ 3. Acyclic colourings of planar graphs, outerplanar graphs and graphs of maximum degree 5 were considered, see [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF], [START_REF] Borodin | Acyclic colorings of planar graphs with large girth[END_REF], [START_REF] Fertin | Acyclic coloring of graphs of maximum degree five: Nine colors are enough[END_REF].

Boiron et al. studied the problem of acyclic (P 1 , . . . , P k )-colourings of graphs. In [START_REF] Boiron | Acyclic improper colourings of graphs with bounded degree[END_REF] they proved that a subcubic graph G has an acyclic (D 1 , S 2 )-colouring as well as an acyclic (S 1 , S 1 , S 1 )-colouring. They also proved that any such G has an acyclic (D 1 , D 1 )-colouring, provided G is neither K 3,3 nor K 4 . In the same paper it was conjectured that any subcubic graph has an acyclic (S 2 , S 2 )-colouring. In Section 2 we verify this conjecture to be true. Moreover, this conjecture cannot be generalized for an arbitrary k, what shows the following theorem:

Theorem 1 Let k ≥ 4.
Then there exists a graph with maximum degree k which has no acyclic

(S k-1 , S k-1 )-colouring. Proof: Let us consider a graph G = C k + D k-2
, where D n denotes a graph without edges of order n and '+' stands for the join operation. Obviously, G ∈ S k .

Let us assume, to the contrary, that c is an acyclic

(S k-1 , S k-1 )-colouring of G.
First observe, that if there is a pair of vertices x, y ∈ V (C k ) such that x and y have the same colour, say colour 1, then at most one vertex a ∈ V (D k-2 ) can have colour 2, since c is acyclic. Similarly, if for a pair of vertices x , y ∈ V (D k-2 ) we have c(x ) = c(y ), then at most one vertex from V (C k ) can have the colour different from c(x ). Therefore, if k > 4 then all vertices of C k , except at most one, say z, must have the same colour, for example colour 1, and all vertices of D k-2 , except at most one, say z , also must have colour 1. One can observe that at least one of the vertices z, z also must have colour 1, to avoid alternating cycles of length four. But in this case there is a vertex v such that v and its k neighbours have the same colour, a contradiction.

In the case k = 4 it is easy to verify that if two vertices of C 4 have colour 1 and another two have colour 2, then one vertex of D 2 must have colour 1 and another one colour 2, to avoid alternating cycles of length four, but then we obtain an alternating cycle of length six, a contradiction.

On the other hand, if all the vertices of C 4 , except exactly one, have colour 1, then all the vertices of D 2 must have colour 1, to avoid alternating cycles, but then there is a vertex z ∈ V (C 4 ) which has colour 1 and all of its four neighbours also have colour 1, a contradiction.

In the remaining case, if all vertices of C 4 have colour 1, then at least one vertex of D 2 also must have colour 1, to avoid an alternating cycle, but this vertex has four neighbours in colour 1, a contradiction. 2

The remainder of this paper is organised as follows. In the next section we show that any subcubic graph has an acyclic (S 2 , S 2 )-colouring. In Section 3 we present a polynomial-time algorithm which produces an acyclic (S 2 , S 2 )-colouring of any cubic graph. In Section 4 we prove that it is an NP-complete problem to decide if a given graph G ∈ S 4 has an acyclic (S 2 , S 2 )-colouring.

2 Acyclic (S 2 , S 2 )-colourings of subcubic graphs

In this section we prove the following theorem: Theorem 2 For any subcubic graph there is an acyclic (S 2 , S 2 )-colouring.

We start with the following straightforward Lemma:

Lemma 1 If G ∈ S 3 then G has an (S 2 , S 2 )-colouring.
Remark 1 Every subcubic graph has also an (S 1 , S 1 )-colouring. Any 2-colouring of G with the maximum number of bichromatic edges is an (S 1 , S 1 )-colouring of G.

First we prove that any cubic graph has an acyclic (S 2 , S 2 )-colouring. Let us consider a cubic graph G and its (S 2 , S 2 )-colouring. If this colouring is not an acyclic (S 2 , S 2 )-colouring, then there are vertices coloured such that they form an alternating cycle. We describe an algorithm which for a given alternating cycle C recolours vertices of G such that we obtain an (S 2 , S 2 )-colouring in which vertices of C do not form any alternating cycle and no new alternating cycle appears.

Let G be an (S 2 , S 2 )-coloured cubic graph and let C be an alternating cycle. Let v ∈ V (C). If we change the colour of v, then C is not alternating. Now the graph G has fewer alternating cycles, because v has two vertices coloured with the same colour as it has, then there is no new alternating cycle, but we could create a monochromatic K 1,3 . If we change the colour of its centre, then no new monochromatic K 1,3 appears, but in this case an alternating cycle could be formed. In our algorithm we destroy one forbidden structure and if our recolouring causes a creation of a new forbidden structure, then it will be destroyed in the next step.

First we describe the structures which can appear if we recolour vertices. Every forbidden structure is a coloured subgraph of cubic graph with two distinguished vertices: a root and a pre-root. The pre-root is the vertex whose colour will be changed.

Forbidden Structures

Structure (1) A monochromatic K 1,3 with the centre y which satisfies the following: let N (y) = {x 1 , x 2 , z}, the vertices x 1 and x 2 are connected by an alternating path and the vertex z has at least one neighbour coloured with colour other than c(z). The root of the structure is the vertex y and the pre-root is the vertex x 1 or x 2 .

Structure (2)

A monochromatic K 1,3 with the centre x which satisfies the following: there is a vertex y ∈ N (x) such that y has exactly one neighbour z coloured with a colour other than c(y). Moreover, z has two neighbours coloured with colour c(z). The root of the structure is the vertex y and the pre-root is the vertex x.

Structure (3) Two monochromatic subgraphs K 1,3 one with the centre x the other with the centre y such that x = y and the vertices x and y are adjacent. Moreover, there are two vertices z 1 , z 2 ∈ N (y) \ {x} which are connected by an alternating path. The root of the structure is the vertex y and the pre-root is the vertex x.

Structure (4) The set of alternating cycles C 1 , C 2 , . . . , C k such that {x 1 , y, x 2 } ⊆ V (C 1 ) ∩ V (C 2 ) ∩ • • • ∩ V (C k ) and x 1 ,
y, x 2 are three successive vertices of the cycles. The root of the structure is the vertex y and the pre-root is the vertex x 1 if it has a neighbour coloured with c(x 1 ) outside the cycle, otherwise the pre-root is the vertex x 2 . Observation 1 Let G be a cubic graph whose vertices are coloured with two colours.

x 2 x 1 y z z y x y z 1 x z 2 x 1 x 2 y (1) (2)
1. Suppose that the 2-colouring of G satisfies the following:

(i) there is exactly one vertex y which has all neighbours coloured with the same colour as y and there is no other monochromatic K 1,3 and

(ii) the vertex y is a root of Structure (1).

Let x be the pre-root of Structure (1) which has the root at y. Then after recolouring x either there is no alternating cycle containing x and there is no monochromatic K 1,3 in G or there is exactly one monochromatic K 1,3 , which has the centre at x and forms Structure [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF] with the root at the vertex x.

2. Suppose that the 2-colouring of G satisfies the following:

(i) there is exactly one vertex x which has all neighbours coloured with the same colour and there is no other monochromatic K 1,3 and

(ii) the vertex x is a pre-root of Structure (2).

Let y be the root of Structure (2) which has the pre-root at x. Then after recolouring x there is no monochromatic K 1,3 in G. Moreover, if new alternating cycles appear, then they form Structure [START_REF] Burstein | Every 4-valent graph has an acyclic 5-coloring[END_REF] with the root at the vertex x and the vertex y is not contained in any of them.

3. Suppose that the 2-colouring of G satisfies the following:

(i) there are exactly two monochromatic K 1,3 , one with the centre in the vertex x and the other with the centre at the vertex y and

(ii) the vertex x is a pre-root and the vertex y is a root of Structure (3).

Then after recolouring the pre-root x of this Structure (3) there is no monochromatic K 1,3 in G. Moreover, if new alternating cycles appear, then they form Structure (4) with the root at the vertex x and none of them contains the vertex y.

Observation 2 Let G be a cubic graph whose vertices are (S 2 , S 2 )-coloured. Let C be an alternating cycle of G and y ∈ V (C).

1. Let x ∈ N (y) \ V (C) and c(x) = c(y). If we change the colour of y then no monochromatic K 1,3 appears.

2. Let x ∈ N (y) \ V (C) and c(x) = c(y). If we change the colour of y then either (i) there is exactly one monochromatic K 1,3 , which has the centre at the vertex y and it forms Structure (1) or (ii) there are exactly two monochromatic K 1,3 : one with the centre at the vertex y, the other with the centre at the vertex x and they form Structure (3) with a pre-root at x and a root at y.

Moreover, vertices of C do not form any alternating cycle and no new alternating cycle appears in any of these cases. Now we present an algorithm which recolours vertices of an (S 2 , S 2 )-coloured cubic graph in such a way that the number of alternating cycles is decreased and the graph is still (S 2 , S 2 )-coloured. We input a cubic graph G which is (S 2 , S 2 )-coloured and a vertex v which is contained in an alternating cycle C. The algorithm returns an (S 2 , S 2 )-colouring in which the vertices of C do not form any alternating cycle and no new alternating cycle appears. An ordering X contains the vertices which are recoloured during the execution of the algorithm, initially X := ∅. Every vertex in X is recoloured only once.

Reduction Algorithm

Input: a cubic graph G with an (S 2 , S 2 )-colouring, a vertex v which is contained in an alternating cycle.

Output: a new (S 2 , S 2 )-colouring of G. 1. x := v.
2. Change the colour of x.

3. Append x to X.

4. If there is a structure which has the root at the vertex x then 4.1. if there is a structure in which the root is at the vertex x and the pre-root r is not in X then

x := r and go to 2;

4.2. else find one vertex or two vertices such that after recolouring these vertices the structure is destroyed and no new structure appears.

To prove that the Reduction Algorithm is correct and decreases the number of alternating cycles we need the following properties of the ordering X: e) If v i was a root of Structure (4), then v i+1 was a root of Structure (1) or (3).

Proposition 1 Let X = {v 1 , v 2 , . . . , v t }. a) v 1 = v. b) If v i
Proposition 2 Let X = (v 1 , v 2 , . . . , v t ). Then v i v i+1 ∈ E(G) for i = 1, . . . , t -1.
Proposition 3 No three successive vertices of the ordering X are coloured with the same colour.

Proposition 4 Let X = (v 1 , v 2 , . . . , v t ). If c(v i-1 ) = c(v i ) and c(v i+1 ) = c(v i ), then c(v i-2 ) = c(v i-1 ) = c(v i+1 ) = c(v i+2 ) for i = 3, . . . , t -2. Proposition 5 Let X = (v 1 , v 2 , . . . , v t ). a) If c(v i ) = c(v i-1 ) and w ∈ N (v i ) \ X, then c(w) = c(v i ) for i = 2, . . . , t. b) If c(v i ) = c(v i+1 ) and w ∈ N (v i ) \ X, then c(w) = c(v i ) for i = 1, . . . , t -1. c) If c(v i-1 ) = c(v i ) and c(v i+1 ) = c(v i ) and w ∈ N (v i ) \ X, then c(w) = c(v i ) for i = 2, . . . , t -1. q q q t t t t t t t t t t t t t t v i-1 v i v i+1 v i+2
q q q Fig. 2: Properties of the ordering X Figure 2 illustrates the properties of the ordering X which are described in Propositions 4 and 5.

Proposition 6 Let X = (v 1 , v 2 , . . . , v t ). Then one of the following conditions holds:

a) c(v 1 ) = c(v 3 ) = c(v 4 ), c(v 2 ) = c(v 1
) and the vertices in N (v 1 ) \ X are coloured with c(v 1 ) and the vertices in

N (v 2 ) \ X are coloured with c(v 2 ); b) c(v 1 ) = c(v 4 ), c(v 2 ) = c(v 3 ), c(v 2 ) = c(v 1
) and the vertices in N (v 1 ) \ X are coloured with c(v 1 ) and the vertices in N (v 2 ) \ X are coloured with a colour other than c(v 2 ).

Lemma 2 Let G be a cubic graph whose vertices are (S 2 , S 2 )-coloured. Let C be an alternating cycle of G and v ∈ V (C). Then after execution of the Reduction Algorithm with the starting point in v we obtain an (S 2 , S 2 )-colouring of G in which the vertex v is not contained in any alternating cycle and this colouring does not contain any new alternating cycle.

Proof: By Observation 2 we have that if we change the colour of the vertex v, then either we obtain an (S 2 , S 2 )-colouring of G in which C is not alternating and no new alternating cycle appears or exactly one of Structures ( 1), (2) appears. From Observations 1 and 2 it follows that if we change the colour of a pre-root of any forbidden structure, then we destroy this structure and we obtain an (S 2 , S 2 )-colouring of G which does not contain any new alternating cycle, or we obtain a monochromatic K 1,3 , or alternating cycles which are contained in Structure (4). Thus to complete the proof it is sufficient to show that in step 4.2 there exist appropriate vertices, i.e., the vertices such that after changing their colours the forbidden structure is destroyed and no new forbidden structure appears. Let (v 1 , v 2 , ..., v t ) be vertices of the ordering X such that v t is a root of the forbidden structure which has the pre-root x belonging to X. Note that v 1 = v and every vertex of X was recoloured only once. Let S be the forbidden structure which appears after recolouring the vertex v t . Then v t is a root of S and x is a pre-root of S. By Proposition 2 we have that v t and x are adjacent. If x = v 1 then two neighbours of x are in X. By Proposition 3, in X there are no three successive vertices with the same colour, so that S is isomorphic neither to Structure (2) nor to Structure [START_REF] Borodin | Acyclic colorings of planar graphs with large girth[END_REF]. By Proposition 6, c(v 1 ) = c(v 2 ), so if x = v 1 , then also S is isomorphic neither to Structure (2) nor to (3). Thus we will consider two cases: when S is isomorphic to Structure (1) and when S is isomorphic to Structure (4). Since x ∈ X, assume that First note that i = 1, because by Proposition 6, the neighbours of v 1 which are not in X have the same colour as v 1 . Before v t was recoloured it had a colour different from c(v 1 ) and it was not in X, so the vertices v 1 and v t cannot be adjacent.

x = v i ¡ ¡ v t v i+1 v i v i-1 r ¨¡ ¡ v t v i+1 v i v i-1 t t q q q t t t t t t q q q t t t t
Assume that i = t -1.

In Structure (1) the root is a centre of the monochromatic K 1,3 and the pre-root is a leaf of K 1,3 , hence vertices v t and v i have the same colour. Thus before the vertex v t was recoloured, it had a colour other than v i . Therefore, before vertex v t was recoloured, the vertex v i had a neighbour outside the ordering X (the vertex v t ) coloured with a colour other than c(v i ). Thus from the properties of the ordering X it follows that c(v i ) = c(v i+1 ) (Proposition 5b) and c(v i-1 ) = c(v i ) (Proposition 3).

In Structure (1) the pre-root is connected by an alternating path with the neighbour of the root, therefore there is an alternating path which starts at the vertex v i and goes through the vertex v i-1 . Hence if we change the colour of v i no new forbidden structure appears and the algorithm stops (Fig. 3).

Suppose now that i = t -1. Since in Structure (1) there are two vertices x 1 and x 2 which can be a pre-root and the algorithm chooses as a pre-root the vertex v t-1 , it follows that both x 1 an x 2 are in X. Thus we can choose a vertex to recolouring similarly as in the case described above. The pre-root of Structure ( 4) is contained in alternating cycles which also go through the vertex v t . By Proposition 1 the vertex v t was the pre-root of Structure (2) or (3) in which the root was v t-1 , hence there are no alternating cycles going through v t-1 . Therefore i = t -1.

¡ ¡ v t v i+1 v i v i-1 r ¨¡ ¡ v t v i+1 v i v i-1 (a) t q q q t t t t t t q q q t t t t t ¡ ¡ v t v i+1 v i v i-1 r ¨¡ ¡ v t v i+1 v i v i-1 (b) t q q q t t t t t t q q q t t t t t
We first consider the case i = 1.

In Structure (4) the root and the pre-root are two successive vertices of an alternating cycle, therefore c(v t ) = c(v i ). Thus before we recoloured the vertex v t , it had the same colour as v i . By Proposition 5 we have to distinguish two cases: one when c(v i ) = c(v i+1 ) and c(v i ) = c(v i-1 ) and the other when

c(v i ) = c(v i+1 ) and c(v i ) = c(v i-1 ). Subcase 2.1 c(v i ) = c(v i+1 ) and c(v i ) = c(v i-1 ). From Proposition 4 it follows that c(v i-2 ) = c(v i-1 ) = c(v i+2 ).
Every alternating cycle of the structure S contains the root v t and the pre-root v i . Therefore, all these cycles contain the vertex v i-1 or v i+1 .

First suppose that both v i-1 and v i+1 have at most one neighbour coloured with their colour. Then at least one of the vertices v i-1 , v i+1 , say v i-1 , is contained in one of the alternating cycles of S. If we change the colour of v i and v i-1 , then we destroy the structure S and no new structure appears, so the algorithm stops (Fig. 4 (a)).

Assume now that only one of the vertices v i-1 , v i+1 has exactly one neighbour coloured with the same colour, say v i-1 has exactly one neighbour coloured with c(v i-1 ) and v i+1 has two neighbours coloured with c(v i+1 ). Note that every alternating cycle of the structure S contains the vertex v i-1 . If we recolour the vertex v i-1 then we destroy S and no new structure appears, so the algorithm stops (Fig. 4 (b)).

¡ ¡ v t v i+1 v i v i-1 r ¨¡ ¡ v t v i+1 v i v i-1 t q q q t t t t t q q q t t t t Fig. 5: Recolouring in Subcase 2.2 Subcase 2.2 c(v i ) = c(v i+1 ) and c(v i ) = c(v i-1 ).
Note that every alternating cycle of S contains the vertex v i+1 . If we recolour the vertex v i then we destroy S and no new structure appears because now the vertex v i-1 has a colour other than c(v i ). Thus the algorithm stops (Fig. 5).

Suppose now that i = 1. Since in Structure (4) there are two vertices x 1 and x 2 which can be a pre-root and the algorithm chooses as a pre-root the vertex v 1 , it follows that both x 1 an x 2 are in X. Thus we can choose vertices to recolouring similarly as in the previous case.

2

Lemma 3 For any cubic graph there is an acyclic (S 2 , S 2 )-colouring.

Proof: Let G be a cubic graph. By Lemma 1, there is an (S 2 , S 2 )-colouring of G. Suppose that there is no acyclic (S 2 , S 2 )-colouring of G. Let c be an (S 2 , S 2 )-colouring of G in which the number of alternating cycles is minimum. Let C be an alternating cycle and v ∈ V (C). By Lemma 2, after execution of the Reduction Algorithm with the starting point in v we obtain an (S 2 , S 2 )-colouring of G which has fewer alternating cycles than c, a contradiction. 2

Proof of Theorem 2: Let G ∈ S 3 . If G is a cubic graph then, by Lemma 3, the Theorem holds. Otherwise there is a cubic graph F such that G ⊆ F . Clearly, an acyclic (S 2 , S 2 )-colouring of F is also an acyclic (S 2 , S 2 )-colouring of G. 2

Theorem 3 There is a polynomial algorithm which produces an acyclic (S 2 , S 2 )-colouring of a cubic graph.

Proof: We discuss the running time of the Colour Acyclic Algorithm and we show that it is O(n 3 ), where n is the order of the input graph.

Step I can be done due to Lemma 1. Moreover, it is easy to observe that a simple, iterative algorithm produces such a colouring in O(n) time. Clearly, Function Cycle(v) takes O(n) time. By Lemma 2, we have that after visiting each vertex v of G at most once and executing the Reduction Algorithm with the starting point in v, we obtain an acyclic (S 2 , S 2 )-colouring of G.

We now estimate the time complexity of the Reduction Algorithm. Finding a forbidden structure in step 4 takes O(n) time (we use Function Cycle to find Structure (4), Structures ( 1)-( 3) can be found in O(1) time). The loop is iterated at most n times. From the proof of Lemma 2, it follows that step 2 can be implemented to run in O(1) time. Thus, on the whole, the Colour Acyclic Algorithm takes O(n 3 ) time. 24 Acyclic (S 2 , S 2 )-colourings of graphs from S 4

By Theorem 1 we have that there are graphs with maximum degree 4 which do not have any acyclic (S 2 , S 2 )-colouring. We show that it is an NP-complete problem to decide if a graph with maximum degree 4 has an acyclic (S 2 , S 2 )-colouring, i.e., we prove the following: Proof: Suppose first that b, c, e are coloured with the same colour. Then all the other vertices must be coloured with the other one. But then there is an alternating cycle induced by the vertices a, b, c, d, e, f . Suppose now, without loss of generality, that e is coloured with colour 1 and b, c are coloured with colour 2. Then a must be coloured with colour 2 since otherwise the vertices a, b, c, e would induce an alternating cycle. That implies that the vertices d and f are coloured with colour 1 (because the vertices b, c have now two neighbours coloured with colour 2). Obviously we obtained an acyclic (S 2 , S 2 )-colouring of the graph and the set of vertices coloured with colour 1 induces P 3 and the set of vertices coloured with colour 2 induces K 3 .

2

Let us now take a quick look on the graph G(C j ), which includes the graph B as an induced subgraph. From Lemma 4 the next one follows.

Lemma 5 There does not exist an acyclic (S 2 , S 2 )-colouring of the graph G(C j ) such that v j1 , v j2 , v j3 are in the same colour class.

Lemma 6 Any non-monochromatic 2-colouring of the vertices v j1 , v j2 , v j3 can be extended to an acyclic (S 2 , S 2 )-colouring of the graph G(C j ).

Proof: The graph B is an induced subgraph of the graph G(C j ), the non-monochromatic 2-colouring of the vertices v j1 , v j2 , v j3 must be consistent with Lemma 4. By symmetry of G(C j ) it is enough to consider only the case when v j3 is coloured with colour 1 and v j1 , v j2 are coloured with colour 2. Then the vertices a, b must be coloured with colour 1 and the vertices c, d must be coloured with colour 2 and we obtain the acyclic (S 2 , S 2 )-colouring of the graph G(C j ).

From the above proof Lemma 7 follows. The graph B is an induced subgraph of H , so the vertices a, b, c, e, f, g must be coloured in accordance with Lemma 4. Thus suppose that the vertices e, b, f (f, g, c) are coloured with colour 1 and the vertices a, c, g (a, b, e) are coloured with colour 2. That implies that the vertex d (h) must be coloured with colour 2. Now the vertex a has two neighbours coloured with colour 2, so the vertex h (d) must be coloured with colour 1. But now the vertices a, b, c, f, g, h (a, b, c, d, e, f ) induce an alternating cycle. It is easy to see that if we colour the vertices a, b, c with colour 1, we must colour all the other vertices with colour 2. Furthermore this colouring defines the only acyclic (S 2 , S 2 )-colouring of the graph H .

It is obvious that the colouring of the graph H determines the colouring of the graph H. One can see that because the vertex e has two neighbours coloured with colour 2 then the vertex o must be coloured with colour 1. Furthermore from the fact that the vertex d is coloured with colour 2 and the vertex o is coloured with colour 1 from Lemma 4 it follows that the vertices j, n must be coloured with colour 1 and the vertices i, m must be coloured with colour 2. The remaining part of the graph can be coloured in both ways. Either we colour the vertices k, p, r with colour 1 and the vertices l, s with colour 2 or we colour the vertices r, l, s with colour 1 and the vertices k, p with colour 2. In this way we obtain the acyclic (S 2 , S 2 )-colouring of the graph H.

2

On the basis of the graph H we create the graph F (see Fig. 9).

Lemma 9

The graph F has an acyclic (S 2 , S 2 )-colouring and maximum degree of F is 4.

Lemma 10 In all acyclic (S 2 , S 2 )-colourings of F the vertices x and x are coloured differently from the vertex a.

The proof of the above lemma follows directly from Lemma 8. Finally, let us consider the graph G(x i ) which we create as it is shown in Figure 10. From Lemma 10 the next one follows.

Lemma 11 In every acyclic (S 2 , S 2 )-colouring of the graph G(x i ) for i = 1, ..., n, k = 1, ..., m the vertices x ik belong to the same colour class.

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

  was a root of Structure (1), then v i+1 was a root of Structure (2). c) If v i was a root of Structure (2), then v i+1 was a root of Structure (4). d) If v i was a root of Structure (3), then v i+1 was a root of Structure (4).

Fig. 3 :Case 1 S

 31 Fig. 3: Recolouring in Case 1

Fig. 4 : 1 Case 2 S

 412 Fig. 4: Recolourings in Subcase 2.1

Theorem 4 Fig. 6 :Lemma 4

 464 Fig. 6: The graph B

Fig. 7 :Observation 3

 73 Fig. 7: The graph G(Cj)

Fig. 8 :

 8 Fig. 8: The graph H

  a

Fig. 9 :Fig. 10 :

 910 Fig. 9: The graph F

  Lemma 7 In any acyclic (S 2 , S 2 )-colouring of the graph G(C j ) for every vertex v ji , where i = 1, 2, 3, the colour class which contains the vertex v ji contains also exactly two neighbours of v ji . In every acyclic (S 2 , S 2 )-colouring of the graph H, either the vertices {a, b, c, j, k, n, o, p, r} or the vertices {a, b, c, j, l, n, o, r, s} belong to the same colour class.

	Now let us consider the graph H. i m Lemma 8 a b d e f j n o t t t t t t t t t t	c t	g p t t	k	t	r t t	h	t	l	s t

3 The complexity of acyclic (S 2 , S 2 )-colourings of cubic graphs

In this section we present a polynomial algorithm which produces an acyclic (S 2 , S 2 )-colouring of a cubic graph G of order n. In the algorithm we first find an (S 2 , S 2 )-colouring of G. Then we find an alternating cycle and using the Reduction Algorithm we recolour the vertices of G to destroy this alternating cycle in such a way that the graph G is still (S 2 , S 2 )-coloured. To find an alternating cycle we use the following function:

Function Cycle(v) Input: a cubic graph G with a 2-colouring, a vertex v. Output: an alternating cycle C containing v or a message that such a cycle does not exist.

where W ⊆ E(G) is the subset of bichromatic edges.

2.

T := the BFS tree of the graph G with the root in v.

3.

Let v 1 , v 2 , v 3 be the neighbours of v.

4. V l := the set of descendants of v l in T , for l = 1, 2, 3. C. mark v as visited.

If there is an edge xy

To determine the complexity of the problem to decide if a given graph G ∈ S 4 has an acyclic (S 2 , S 2 )colouring we will use the 3NN-SAT problem. The NP-completeness of 3NN-SAT was proved in [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF] Proof of Theorem 4: Clearly our problem is in NP. In our proof we will make a polynomial-time reduction from the 3NN-SAT problem, which belongs to the class NP-c, to our problem. Let C = {C 1 , .., C m } be a set of clauses and let V = {x 1 , ..., x 1 } be a set of Boolean variables. Furthermore, C j ⊆ V and for j = 1, 2, ..., m C j = (c j1 , c j2 , c j3 ). In 3NN-SAT we ask if there is a truth assignment such that in each clause there exist at least one true variable and at least one false variable. Note that there are no negative variables. Given an instance of 3NN-SAT we create an instance of our problem, i.e., the graph G in the following way. For each clause we create the graph G(C j ) and for each variable x i ∈ V we create the graph G(x i ). To obtain the whole graph G we have to connect the graphs G(C j ) and G(x i ). To do that for i = 1, ..., n, k = 1, ..., m, p = 1, 2, 3 we add an edge x ik v kp , where x ik ∈ V (G(x i )) and v kp ∈ V (G(C j )), if and only if the variable x i is c kp . From Lemma 7 and the construction of the graph G a further Lemma follows.

Lemma 12 In every acyclic (S 2 , S 2 )-colouring of the graph G for j = 1, ..., m and p = 1, 2, 3 the vertex v jp ∈ V (G(C j )) has exactly one neighbour x ij in exactly one graph G(x i ) where 1 ≤ i ≤ n and moreover x ij belongs to a different colour class than v jp .

Let us suppose that the 3NN-SAT problem has a solution. We obtain an acyclic (S 2 , S 2 )-colouring of the graph G in the following way. For each true variable x i we colour every vertex x ik ∈ V (G(x i )) with colour 1 and for each false variable x i we colour every vertex x ik ∈ V (G(x i )) with colour 2 where i = 1, ..., n, k = 1, ..., m. We colour the neighbours of the vertices x ik ∈ V (G(x i )) in the graph G(C j ) differently from x ik . From Lemmas 5, 6, 8, 11 and 12 we have that such 2-colouring can be extended to an acyclic (S 2 , S 2 )-colouring of the graph G. Now suppose that the graph G has an acyclic (S 2 , S 2 )-colouring. To obtain a solution of the 3NN-SAT problem we assign true value to every variable x i ∈ V for which the corresponding vertex x ik ∈ V (G(x i )) is coloured with colour 1 where i = 1, ..., n, k = 1, ..., m. Furthermore we assign false value to every variable x i ∈ V for which the corresponding vertex x ik ∈ V (G(x i )) is coloured with colour 2 where i = 1, ..., n, k = 1, ..., m. The correctness of this assignment follows from Lemmas 5, 11 and 12.

2