2011-2012
2011 - 2012
Vendredi 9 septembre 2011 - Adjacent vertex-distinguishing edge-coloring of graphs - M. Montassier .
Vendredi 16 septembre 2011 - Vizing conjecture, a short proof? - P. Dorbec.
Résumé : Nous présenterons une preuve (?) récente (06/09/11), courte et élégante, due à Elliot Krop, de la conjecture de Vizing. Cette conjecture, qui était ouverte depuis 1963, dit que le nombre de domination du produit Cartésien de deux graphes est au moins le produit des nombre de domination des facteurs. Nous présenterons la preuve et l'illustrerons sur un exemple.
Jeudi 29 septembre 2011 - Girth and the Greedy algorithm - Bert Hartnell
Résumé : Finding an efficient algorithm to decide if a given graph or network has a certain property is often difficult or unlikely. Thus there is some interest in graphs with the characteristic that a simple, such as the greedy, algorithm produces a set with the desired property efficiently. For example, well-covered graphs (every maximal independent set of vertices is of one size and, hence, maximum) fall into this category. Many such problems have the rather curious feature that if one knows the structure of trees in the collection, then this characterization is essentially the same even with cycles present as long as they are not too small. For instance, the well-covered graphs of girth 8 or more (i.e., no cycles of length 7 or smaller) can be described essentially the same as the well covered trees. A similar situation arises with the problem of where to locate undesirable objects (garbage dumps, nuclear sites) so that we have no more than k in the neighborhood of anyone. A number of problems of this type will be outlined.
Vendredi 21 octobre 2011, 1ère moitié - Partition arbitraire et préaffectation de sommets - Julien Bensmail.
Résumé : Soit G = (V, E) un graphe d'ordre n. Une partition tau = (tau_1, ..., tau_k) de n, avec tau_1 >= ... >= tau_k, est dite réalisable dans G s'il est possible de partitionner V en k parts V_1, ..., V_k de sorte que quelque soit i de [1,k], le sous-graphe G[V_i] soit connexe et d'ordre tau_i. G est dit arbitrairement partitionnable si toute partition de n y est ainsi réalisable. Plusieurs versions de la partition arbitraire, augmentées de contraintes supplémentaires, ont fait l'objet de diverses études, articulées principalement autour de la famille des arbres. Après un bref rappel des résultats principaux la concernant, nous nous concentrerons sur le cas des graphes biconnexes. Pour cela, nous introduirons une version forte de la partition arbitraire, dite "avec une préaffectation", caractérisant le fait qu'il soit toujours possible de trouver, étant donnés un sommet arbitraire v de G et un entier quelconque i appartenant à [1,k], une réalisation V_1, ..., V_k de tau dans G vérifiant v inclus dans V_i. Une fois la biconnexité des graphes arbitrairement partitionnables de cette manière mise en évidence, nous montrerons qu'il en existe une infinité et étudierons plus spécifiquement certaines classes de graphes, notamment celle des ballons.
Vendredi 21 octobre 2011, 2ème moitié - Vertex Nim : une variante de Nim dans les graphes - Gabriel Renault.
Résumé : Le jeu de Nim a été introduit et résolu par Bouton en 1904. En 2003, Fukuyama a proposé une variante de ce jeu qui se joue dans les graphes, avec des poids sur les arêtes. Nous proposons une autre variante, Vertex Nim, qui se joue également dans les graphes, mais avec des poids sur les sommets.
Vendredi 28 octobre 2011, 1ère moitié - Degré minmax des graphes planaires et cycles interdits - Clément Charpentier.
Résumé : Le degré minmax d'un graphe G est le plus grand entier k tel que toute arête de G est incidente à un sommet de degré au moins k.
Borodin et al. ont montré qu'un graphe planaire sans feuilles et sans 4-cycles a un degré minmax d'au plus 7. Ils ont également montré que la borne descendait à 5 si l'on interdit en plus les cycles de taille 5.
Nous montrons que l'on atteint également cette borne si, au lieu d'interdire les 4- et 5-cycles, on interdit les 4- et 6-cycles. De même si on interdit les 4- et 7-cycles.
Vendredi 28 octobre 2011, 2ème moitié - Énumération et élection dans les environnements de diffusion multisauts anonymes - Thomas Morsellino.
Résumé : Nous étudions les problèmes de l'énumération et de l'élection dans des environnements de diffusion multisauts. Nous considérons un modèle de communication asynchrone dans lequel chaque noeud du réseau diffuse un message et son voisinage le reçoit après un délai de temps arbitraire inconnu. Ce délai dépend du temps pris par les couches réseaux pour assurer l'acheminement du message. Dans ce travail, nous présentons les conditions nécessaires que doivent satisfaire les graphes pour résoudre ces problèmes puis nous montrons que ces conditions sont suffisantes en fournissant un algorithme pour l'énumération et un algorithme pour l'élection. Pour ces deux problèmes, nous mettons en avant l'importance de la connaissance initiale. Concernant le problème de l'énumération, chaque noeud connait le nombre de noeuds du graphe et, contrairement aux travaux existants, n'a pas connaissance de son voisinage. Pour le problème de l'élection, nous montrons que cette connaissance n'est pas suffisante. Nous proposons un algorithme dans lequel nous supposons que chaque noeud connait une carte du graphe (sans connaitre sa position dans ce graphe). Nos algorithmes offrent une meilleure complexité (mémoire et messages) en regard des travaux existants la réduisant ainsi d'exponentielle à polynomiale.
Vendredi 4 novembre 2011 - Rainbow numbers and rainbow connection - Ingo Schiermeyer.
Résumé :
In this talk we consider edge colourings of graphs. A subgraph H of a graph
G is called rainbow subgraph, if all its edges are coloured distinct.
In the first part we will survey the computation of rainbow numbers. For
given graphs G,H the rainbow number rb(G,H) is the smallest number m of
colours such that if we colour the edges of G with at least m different colours,
then there is always a totally multicoloured or rainbow copy of H. For various
graph classes of H we will list the known rainbow numbers if G is the complete
graph and report about recent progress on the computation of rainbow numbers.
Finally, new results on the rainbow numbers rb(Qn,Qk) for the hypercube Qn
will be presented.
An edge-coloured graph G is called rainbow connected if any two vertices are
connected by a path whose edges have distinct colours. This concept of rainbow
connection in graphs was introduced by Chartrand et al.. The rainbow connection
number of a connected graph G, denoted rc(G), is the smallest number of colours
that are needed in order to make G rainbow connected.
In the second part we will show several complexity results and present lower
and upper bounds for rc(G). We will discuss rc(G) for graphs with given minimum
degree. Finally, we will present some recent Erdös-Gallai type results for
rc(G).
Vendredi 4 novembre 2011 - On acyclic vertex colourings of graphs - Elzbieta Sidorowicz.
Résumé :
Let P1 , . . . , Pk be hereditary properties. A k-colouring of a graph G is
called a (P1 , . . . , Pk )-colouring of G if for 1 ≤ i ≤ k the subgraph induced
in G by the colour class Vi (the set of vertices coloured with i) belongs
to Pi . Such a colouring is called an acyclic (P1 , . . . , Pk )-colouring if for
every two distinct colours i and j the subgraph formed by the edges whose
endpoints have colours i and j is acyclic. An acyclic (P1 , . . . , Pk )-colouring
is an acyclic k-colouring if for 1 ≤ i ≤ k the property Pi is the set of all
edgeless graphs. An acyclic (P1 , . . . , Pk )-colouring such that for 1 ≤ i ≤ k the
property Pi is the set of of graphs with degree at most d is called d-improper
acyclic colouring. We deal with the acyclic (P1 , . . . , Pk )-colouring where the
property Pi (i = 1, . . . , k) is the set of acyclic graphs or the set of graphs
with bounded maximum degree. We study the acyclic (P1 , . . . , Pk )-colouring
of graphs with bounded degree.
Vendredi 18 novembre 2011 - pas de GT
Journées Graphes et Algorithmes
Semaine du 21 au 25 novembre 2011
Bordeaux Workshop on Identifying Codes (and related topics)
Programme sur http://bwic2011.labri.fr
Lundi 5 décembre 2011 - 10:00 - Amphi LaBRI - Soutenance de thèse de Hervé Hocquard.
Mardi 6 décembre 2011 - 14:00 - Amphi LaBRI - Jeux de coloration de graphes - Soutenance de thèse de Adrien Guignard.
Résumé :
Nous présenterons deux jeux de coloration de graphes.
En première partie, nous introduirons un jeu combinatoire où les joueurs colorient proprement et alternativement les sommets d'un graphe avec k couleurs, et où le perdant est le 1er joueur ne pouvant plus jouer. Après avoir réduit ce jeu à un jeu de retrait de sommets, nous présenterons un algorithme cubique pour calculer les stratégies gagnantes sur la famille des chenilles.
Nous étudierons également quelques variantes de ce jeu sur la famille des chemins, et déterminerons sur un exemple l'ensemble des chemins perdants.
En seconde partie nous nous pencherons sur le problème de détermination du nombre chromatique ludique des arbres. Ce paramètre de graphe est calculé à partir d'un jeu où Alice et Bob colorient le graphe avec des objectifs distincts: Alice essaye de colorier tout le graphe alors que Bob tente de l'en empêcher. Nous présenterons quelques outils permettant l'étude de ce problème, et donnerons quelques résultats, notamment sur la famille des 1-chenilles.
Jeudi 8 décembre 2011 - 14:30 - Bât A29, Amphi E - Etude structurelle et algorithmique des graphes k-chemins séparables - Soutenance de thèse de Emilie Diot.
Vendredi 9 décembre 2011 - Frédéric Mazoit - Le théorème du sommet redondant pour les graphes sur les
surfaces.
Salle 4, bât A29
Résumé : Étant donnés k couples (s1, t1), ..., (sk, tk) de sommets dans un graphes, le problème des k chemins disjoint (k-DDP) demande s'il existe k chemins disjoints dont les extrémités sont les couples (si, ti). Robertson et Seymour ont donné un algorithme qui fonctionne en temps O(n^3) pour résoudre ce problème. Dans certains cas, l'algorithme donne une réponse directe, sinon, il identifie un sommet redondant dont la suppression ne change pas la réponse au problème. Malheureusement, cet algorithme fait intervenir des constantes dont l'existence n'est montré que de façon existentielle et même si Robertson et Seymour ont affirmé qu'il était possible de rendre effectif leurs preuves, ce travail n'avait pas encore été fini.
Dans cet exposé, je présenterai un travail en collaboration avec Geelen, Huynh et Richter dans lequel nous terminons ce travail en donnant une preuve effective du théorème du sommet redondant pour les graphes sur les surfaces.
Vendredi 13 janvier 2012 - Strong chromatic index of planar graphs with large girth - André Raspaud .
Résumé : Let $G$ be a graph. A {\em strong $k$-edge-coloring} of $G$ is a
mapping from $E(G)$ to $\{1,\ldots,k\}$ such that every two adjacent
edges or two edges adjacent to a same edge receive two distinct
colors. We will give the sketch of the proof of the existence of a linear function $c(\Delta)$ such that every planar graph with maximum
degree $\Delta$ and girth at least $c(\Delta)$ is strong $(2\Delta
-1)$-edge-colorable, that is best possible (in terms of number of
colors) as soon as $G$ contains two adjacent vertices of degree
$\Delta$.
Vendredi 20 janvier 2012 - Paired versus double domination in graphs - Paul Dorbec.
Résumé :
A vertex is said to dominate itself and its neighbours. A subset of vertices in a graph is a dominating set if it dominates all the vertices. It is a paired dominating set it induces a perfect matching. A dominating set is a double-dominating set if it dominates every vertex twice. During this talk, we will discuss relationship between these two parameters, and especially in the case when the graph does not contain induced stars of a given order.
Vendredi 3 février 2012 - Quelques problèmes classiques sur des graphes dynamiques - Sébastien Choplin (Université de Picardie Jules Verne).
Résumé :
Nous présenterons un modèle de graphes dynamiques et la transposition de problèmes classiques (plus court chemins, flots...) sur ces graphes. Nous présenterons aussi le problème des corrélations dans l'évolution, qui est intrinsèquement lié à la dynamique du modèle.
Vendredi 10 février 2012 - Arnaud Pêcher - Petite histoire d'une petite preuve.
Résumé :
Grötschel, Lovasz et Schrijver ont démontré en 1984 que le nombre Theta de Lovasz d'un graphe minimal imparfait n'est pas entier.
Pour les besoins d'une preuve d'un lemme, j'ai réutilisé cet argument pour un graphe partitionable bien spécifique, en mentionnant que le résultat ci-dessus s'appliquait en fait à tous les graphes partitionables.
Voici la réponse sur ce point d'un arbitre d'humeur taquine: "I would advise to give a proof, along the lines of the reference - it is not difficult and it is informative to have the argument in the paper."
Puisque cette preuve est "informative" et "not difficult", je vous en expliquerai le mécanisme dans cet exposé, puis vous montrerai comment faire "mieux" dans le cas qui m'intéressait.
Vendredi 17 février 2012 - Induced decomposition of graphs - Nathann Cohen.
Résumé :
Given two graphs F and G, an induced F-decomposition of G is a
partition of E(G) into induced copies of F. Bondy and Szwarcfiter
defined the value ex(n; F) as the maximum number of edges of a graph
of order n admitting an induced F-decomposition and studied its values
for several families of graphs F. In this talk, I will present an
explanation of the asymptotic behaviour of the function "ex", by
showing that ex(n, F) = (1/2) n^2 - o(n^2). This result has been
obtained in collaboration with Zsolt Tuza.
Vendredi 23 février 2012 - Des limites de la coloration quasi propre - Paul Dorbec et/ou Mickaël Montassier.
Résumé :
Une coloration quasi propre est une coloration des sommets où chaque classe de couleurs induit un sous graphe de degré maximum fixé. Dans cet exposé, nous nous intéresserons au cas où les couleurs sont de deux types: a couleurs induisant un sous graphe de degré maximum d, et b couleurs induisant un stable (coloration propre): on parle de (d,a,b)*-coloration. Nous montrons que tout graphe dont le mad (degré moyen maximum) est inférieur à une certaine fonction f est (d,a,b)*-coloriable. Cette fonction f tend (par valeurs inférieures) vers 2a+b quand d tend vers l'infini. Ce résultat est asymptotiquement optimal : il existe des graphes non (d,a,b)*-coloriables dont le mad tend (par valeurs inférieures également) vers 2a+b. Ceci montre en quelque sorte qu'en terme de degré moyen, une couleur d-impropre n'est pas plus efficace que deux couleurs propres.
Vendredi 9 mars 2012 - session travail - Arnaud Pêcher.
Vendredi 16 mars 2012 - Coloration des arêtes à distance 2 - Hervé Hocquard.
Salle 76
Résumé : Une k-coloration d'arêtes distance 2 (ou forte) d'un graphe est une
coloration d'arêtes, qui utilise au plus k couleurs, telle que deux
arêtes adjacentes ou adjacentes une même arête reçoivent des couleurs
différentes. L'indice chromatique fort d'un graphe G est le nombre
minimum de couleurs k tel que G admet une k-coloration forte d'arêtes.
La première partie de cet expos sera consacre la majoration de
l'indice chromatique fort pour certaines classes de graphes. Dans la
seconde partie nous présenterons des résultats de complexité (du
problème de k-coloration forte d'arêtes) pour les graphes planaires.
Vendredi 23 mars 2012 - Des codes (correcteurs) systématiques représentés sur une grille - Eleonora Guerrini.
Salle: A29/ Amphi E
Résumé : Un code à correction d'erreurs est l'espace des mots utilises
dans les communications digitaux (téléphone, satellites, CD) pour
encoder les messages qu'on veut transmettre.
Un bon code est un ensemble de mots qui permet au décodeur de
reconstituer le message envoyé même s'il y a eu du "bruit" pendant la
transmission. La quantité de bruit que l'on peut corriger dépend du
code choisi et elle est reliée a la distance entre les mots.
On présente une classification des codes systématiques basée sur la distance a l'aide de la résolution d'un système polynomiale multivarié. Cela est en générale assez difficile a résoudre, mais si on visualise ces codes sur une grille (les sommets sont les codes de différents paramètres et les arêtes sont des inclusions) pas seulement on peut simplifier les calcules du système, mais aussi on trouve des propriétés de structure.
Vendredi 6 avril 2012 - Une (nouvelle?) décomposition canonique des graphes fortement connexes. Applications aux mots de Gauss - Bruno Courcelle.
Résumé : We introduce a canonical decomposition of strongly connected graphs that we call the *atomic decomposition*. We can construct it in linear time from the canonical decomposition in 3-connected components (by Tutte) of the considered graph. With it, we study *Gauss words*: these words are associated with self-intersecting closed curves in the plane.We characterize, up to homeomorphism, all such curves with a given Gauss word. We extend this characterization to tuples of words, associated with tuples of closed curves in the plane.
Vendredi 13 avril 2012 - Arbitrarily Partionable Graphs - Olivier Baudon.
Résumé :
Soit G un graphe d'ordre n et n1, ..., nk une suite d'entiers dont la somme vaut n. G est dit (n1, ..., nk)-partitionable s'il est possible de partitionner ses sommets en une suite de k sous-ensembles disjoints V1, ..., Vk telle que pour tout i, |Vi| = ni et le sous-graphe induit par Vi est connexe.
Un graphe est dit arbitrairement partitionnable s'il est (n1, ..., nk)-partitionable pour toute suite d'entiers (n1, ..., nk) dont la somme vaut n.
Nous présenterons quelques résultats récents sur ce problème, en particulier sur des questions de degré maximum, et de taille des composantes lorsque l'on enlève un séparateur.
Vendredi 20 avril 2012 - Cycle cover for signed graphs - Edita Rollova.
Résumé :
Given a graph G, a cycle cover of G is a set C of cycles of G such that each edge of G belongs to at
least one cycle of C. The length of C is the sum of the lengths of the cycles
in C. It is clear that a graph admits a cycle cover if and only if it contains no bridges that is it admits a nowhere-zero flow. In this talk we introduce a brand new concept of a cycle cover for signed graphs.
A signed graph is a graph where each edge is either positive or negative. We define a cycle cover of a signed graph with respect to a flow-admissibility, which is equivalent to a property that each edge of the signed graph is contained in a balanced circuit or in a barbell. A circuit is called balanced, if it contains an even number of negative edges, otherwise it is unbalanced. A barbell is a graph consisting of two edge-disjoint unbalanced circuits joined by a path that meets the circuits only in its end-vertices (the path is allowed to have zero length and it is the only case when we admit the unbalanced circuits in the barbell to share a vertex). Balanced circuits and barbells are together called signed circuits and so a cycle cover C* of a signed graph G* is a set of signed circuits of G* such that each edge of G* is contained in at least one of them. The length of C* is again the sum of the lengths of the signed circuits in C*.
The main result presented in this talk is that each signed graph that admits a nowhere-zero 2-flow has a cycle cover with the total length at most 4/3 . |E(G)|. This bound is tight for infinitely many graphs.
This is a joint work with Edita Máèajová, André Raspaud and Martin Skoviera.
Vendredi 27 avril 2012 -Méthode d'accélération en optimisation global - Jordan Ninin.
Résumé :
Depuis quelques années, les algorithmes de branch and bound ont montré leur intérêt pour la résolution exacte de problèmes d'optimisation non-convexes avec contraintes. Cependant, ces méthodes nécessitent parfois beaucoup de temps CPU, c’est pourquoi l’intégration de méthode d’accélération s’avère généralement indispensable. Nous reviendrons sur différentes techniques basées sur l'analyse d'intervalles, des algorithmes de réduction de boites issue de la programmation par contraintes, ainsi que des techniques de calcul de borne basées sur des relaxations linéaires et SDP.
Vendredi 4 mai 2012 - Perfect matchings in cubic graphs - Frantisek Kardos.
Résumé :
Lovász and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite cubic graphs by Voorhoeve in 1979, and for planar cubic graphs by Chudnovsky and Seymour in 2008. Then several general lower bounds for the number of perfect matchings in cubic bridgeless graphs appeared, and finally, the conjecture has been settled last year. In this talk, a survey on methods used to attain these results is provided.
Vendredi 11 mai 2012 - Complexity and algorithms for max-coloring problems - Giorgio Lucarelli.
Résumé : We deal with generalizations of the classical graph edge/vertex-coloring problems motivated by scheduling questions arising in computer and communication systems. The most general problems we attack are called bounded max-edge/vertex-coloring problems and take as input an edge/vertex weighted graph and a bound b. In these problems each color class is of cardinality at most b and of weight equal to that of the heaviest edge/vertex in this class. The objective is to find a proper coloring of the input graph minimizing the sum of all color classes' weights. For unit weights these problems reduce to the known bounded coloring problems, while in the absence of the cardinality bound we get the (unbounded) max-coloring problems. The max-coloring problems have been well motivated and studied in the literature. Max-edge-coloring problems arise in switch based communication systems, like SS/TDMA, where messages are to be transmitted through direct connections established by an underlying network. Max-vertex-coloring problems arise in the management of dedicated memories, organized as buffer pools, which is the case for wireless protocol stacks like GPRS or 3G. Moreover, max-coloring problems correspond to scheduling jobs with conflicts in multiprocessor or batch scheduling environments. However, in all practical applications there exist physical constraints on the number of entities (corresponding to vertices/edges of a graph) assigned the same resource (color), which motivate the study of the bounded max-coloring problems. In this talk, we present complexity results as well as algorithms for the bounded max-edge/vertex-coloring problems.
Mardi 15 mai 2012 - Chemins disjoints avec congestion dans les graphes à mineur exclu - Guyslain Naves.
Résumé : Nous étudions le problème de trouver un nombre maximum de chemins disjoints dans des classes de graphes fermées par mineur. En général, ce problème est très difficile à approximer, même dans des classes très simples comme les graphes planaires, avec des ratios d'inapproximabilité en $\Omega(\sqrt{n})$ ou plus. Pour contourner cette difficulté, plusieurs travaux autorisent l'utilisation de congestion: sous congestion $c$, on autorise $c$ chemins à utiliser la même arête. Chuzhoy a montré en 2011 qu'en permettant une congestion constante, il existe une algorithme de ratio polylogarithmique. Si nous cherchons plutôt des algorithmes ayant des ratios d'approximations constants, Chekuri, Khanna et Shepherd ont pu trouver un algorithme avec ratio d'approximation constant et congestion 2, dans le cas des graphes planaires. Nous souhaitons généraliser ce résultat, et nous prouvons que pour les graphes à largeur d'arbre bornée, et pour les graphes plongeables dans une surface fixée, il existe des algorithmes avec ratio et congestion constants. Ces deux types de classes de graphes étant fermées par mineur, nous conjecturons que toute classe de graphes à mineur exclu admet de tels algorithmes.
Vendredi 25 mai 2012 - Largest Planar Ocliques - Sagnik Sen.
Résumé : An oclique is an oriented graph where every pair of distinct non-adjacent vertices are connected by a directed path of length 2.
Klostermeyer and MacGillivray conjectured (2004) that the maximum order of a planar oclique is 15. Here we settle that conjecture.
We also show that the maximum order of a planar oclique with girth 4, 5 and k (> 5) are respectively 6, 5 and 3.
Vendredi 15 juin 2012 - Application de la théorie spectrale des graphes à des objets musicaux. Modélisation et visualisation en Hyperespace - Gilles Baroin.
Amphi du LaBRI
Résumé : Nous déduisions puis projetons spectralement le produit cartésien C3 □ C4, afin de construire le "graphe Planet", solution unique répondant aux conditions de symétrie propres à l'espace des notes de musique de notre système tempéré. Nous utilisons une coloration à deux dimensions pour les sommets, ainsi que la technique de projection spectrale pour créer un modèle géométrique dont les sommets sont en surface d'une hypersphére. Celle-ci se décline ensuite selon les applications et contextes musicaux. La projection spectrale est aussi utilisée pour comparer différents "Pitch Spaces" (répartitions spatiales de notes) ou claviers d'instruments. Dans le cas de réseaux d'accords non circulants, nous utilisons des "graphes de graphes" circulants et symétriques afin d'obtenir des visualisations simples.
Vendredi 22 juin 2012 - Partitioning Harary graphs into connected subgraphs containing prescribed vertices - Julien Bensmail.
Résumé :
A graph G is said to be arbitrarily partitionable (AP for short) if for every partition (tau_1, ..., tau_p) of |V(G)| there exists a partition (V_1, ..., V_p) of V(G) such that each V_i induces a connected subgraph of G with order tau_i. If, additionally, each of k of these subgraphs contains an arbitrary vertex of G prescribed beforehand, then G is said to be AP+k. Complete graphs on strictly more than k vertices are AP+k but are not convenient because of their size. In this talk, for any k ≠ 2 and n ≥ k+1, we will see that the Harary graph H_{k+1,n}, known to be one of the smallest (k+1)-connected graphs on n vertices, is AP+k. To overcome the fact that H_{3,n} is not AP+2 for some n, we will also introduce a class of edge-minimal 3-connected AP+2 graphs to complete our hierarchy of AP+k graphs with minimum size. These results are best possible in the sense that we cannot allow more prescriptions while partitioning these graphs.
Joint work with O. Baudon, J. Przybyło, E. Sopena, and M. Woźniak.
Lundi 9 juillet 2012 - 14:00 - Amphi du LaBRI - On packing, colouring and identification problems - Soutenance de thèse de Petru Valicov.
