AlGCo : algorithmique, graphes et combinatoire
Séminaire/Groupe de Travail

Flavia Bonomo (Université de Bueno Aires, Argentine)
Some new results on the b-coloring problem
This is a mix of joint works with C. Betancur, S. Choudum, G. Duran, T. Karthick, I. Koch, M. Kouider, F. Maffray, J. Marenco and M. Valencia-Pabon.

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G is the maximum number t such that G admits a b-coloring with t colors.
Several problems related to b-coloring of graphs have been introduced in the literature. Recently, the theory of b-colorings of graphs has been applied in to some clustering problems in data mining processes. In fact, clustering is generally defined as an unsupervised data mining process which aims to divide a set of data into groups, or clusters, such that the data within the same group are similar to each other while data from different groups are dissimilar. However, additional background information (namely constraints) is available in some domains and must be considered in the clustering solutions. A b-coloring-based approach exhibits more important clustering features an enables to build a fine partition of the data set in clusters when the number of clusters is not predefined.
In this talk, we will summarize the last algorithmic and theoretical results obtained on b-coloring and the related notions of b-perfection, b-continuity and b-monotonicity within some graph classes.

Steve Chaplick (Université de Toronto, Canada)
Characterizing the Intersection Models of Path graphs using PR-trees

A new data structure, the PR-tree, is introduced to characterize the sets of path-tree models of path graphs. We further characterize the sets of directed path-tree models of directed path graphs with a slight modification to the PR-tree. An algorithm is presented which constructs a PR-tree that captures the path-tree models of a given graph. This algorithm is extended to construct the modified PR-tree which captures the directed path-tree models of a given graph. For a given graph with $n$ vertices and $m$ edges, these algorithms have a runtime complexity of $O(a(n+m) * n * m)$ (where $a(s)$ is the inverse of Ackermann's function arising from Union-Find). Additionally, the size of any PR-tree which is produced by these algorithms will be linear with respect to the graph it is produced from. These algorithms are further used to recognize path graphs and directed path graphs. This nearly matches the best known recognition algorithms for both path graphs and directed path graphs (each of which has a runtime complexity of $O(n*m)$).

Éric Duchêne
Etiquetages identifiants et carrés latins

Un étiquetage identifiant des sommets d'un graphe G est une coloration impropre qui doit permettre d'identifier de manière unique les arêtes de G selon une fonction f de codage donnée. Par exemple, dans le cas des étiquetages gracieux, le code d'une arête f(uv) est |f(u)-f(v)|. Bien souvent, on s'interroge sur l'existence de tels étiquetages pour que f soit en bijection avec {1,..,|E|}. Dans cet exposé, nous évoquerons le cas d'une coloration récente, le set coloring, où la fonction de codage vérifie f(uv)=f(u) XOR f(v). Cette coloration a été introduite en 2009 par Hedge, et très peu de résultats sont connus à son sujet. Nous évoquerons la résolution du problème sur des premières familles de graphes telles que les chaines, les cycles ou les arbres binaires, et verront comment l'utilisation des carrés latins peut nous aider à colorier optimalement ces graphes.

Stéphan Thomassé
Dimension de Vapnik Chervonenkis (suite de l'exposé du 28/01/10)

Sylvia Tondato (Universidad Nacional de La Plata - Argentina)
Optimal clique trees in subclasses of chordal graphs

A graph G is chordal if and only if it has a clique tree: a tree T whose vertices are cliques of G and such that for every vertex x of G, C_x, cliques of G containing x, induces a subtree of T. DV, UV graphs are subclasses of chordal graph and they can be characterized by clique trees. A graph is UV if there exists T, UV-clique tree: a tree such that every C_x induces a path in T. A graph is DV if there exists T, DV-clique tree: a directed tree such that every C_x induces a path in T. In this work we present a construction of clique trees for these subclasses which have minimum number of leaves.

Marisa Guitterez (Universidad Nacional de La Plata - Argentina)
From Montpellier to Montpellier: the path followed by our group of Graph Theory

Some years ago, at the beginnings of our group, Professor Andre Batdedat, from the University of Montpellier, had a strong influence in the path taken for us. He cooperated with the first mathematician who works on Graph Theory in Argentina, Lia Oubina, my supervisor. He made known Lia his interest in the study of a certain class of graphs associated with Taxonomy: it was the class of Dually Chordal Graphs. Through this class of graphs I had the fortune to meet Jayme Szwarcfiter and his group. Today is my intention to tell you how this initial study was diversifying and growing to get here, again in Montpellier, with the study of the class of Rooted Path graphs. In this talk we will try to give a summary to the topics that we have studied and we are studying, giving an overview of the most important results that we have obtained. It could be said that our main interest is the study of certain classes of graphs: structural properties, resolution of some problems restricted to them, construction of special models, etc. On the other hand, the clique operator is one of our favorite topics, its behavior such in particular classes as in general. The topics on which we will discuss in this talk, can be divided into three main groups:

• Classes of graphs defined by a property of its cliques: Indifference, Dually Chordal, Comparability (Tree-like).
• Clique Graphs: general operator theory for particular classes. New characterization, complexity of its recognition, open problems.
• Classes of graphs defined by intersection: Loop, Helly-circular arc, Chordal: path graphs, directed path graphs. rooted path.

Pim van 't Hof (Durham University)
On graph contractions and induced minors
Joint work with Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos and Stefan Szeider.

A graph H is a minor of a connected graph G if H can be obtained from a subgraph of G by contracting edges. If H can be obtained from an induced subgraph of G, or from G itself, by contracting edges, then we say that H is an induced minor or a contraction of G, respectively. A celebrated result by Robertson and Seymour states that the problem of deciding whether G contains a fixed graph H as a minor can be solved in polynomial time for any graph H. For the two related problems of deciding whether G contains a fixed graph H as an induced minor or as a contraction, the complexity picture is not so clear. The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G contains H as an induced minor. We show that this problem is fixed parameter tractable in |V(H)| if G belongs to any nontrivial minor-closed graph class and H is a planar graph. For a fixed graph H, the H-Contractibility problem is to decide whether a graph can be contracted to H. So far, H has a dominating vertex in all cases known to be polynomially solvable, whereas H does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-Contractibility is NP-complete. We also present a new class of graphs H for which H-Contractibility is solvable in polynomial time. Finally, we study the (H,v)-Contractibility problem, where v is a vertex of H. The input of this problem is a graph G and an integer k, and the question is whether G is H-contractible such that the "bag" of G corresponding to v contains at least k vertices. We show that this problem is NP-complete whenever H is connected and v is not a dominating vertex of H.

Hajo Broersma
Best possible degree sequence conditions for graph properties

We discuss recent work on graphical degree sequences, i.e., sequences of integers that correspond to the degrees of the vertices of a graph. Historically, such degree sequences have been used to provide sufficient conditions for graphs to have a certain property, such as being $k$-connected or hamiltonian. For hamiltonicity, this research has culminated in a beautiful theorem due to Chv\'atal (1972). This theorem gives a sufficient condition for a graphical degree sequence to be forcibly hamiltonian, i.e., such that every graph with this degree sequence is hamiltonian. Moreover, the theorem is the strongest of an entire class of theorems in the following sense: if the theorem does not guarantee that a sequence $\pi$ is forcibly hamiltonian, then there exists a nonhamiltonian graph with a degree sequence that majorizes $\pi$. Kriesell solved an open problem due to Bauer et al. by establishing similar conditions for $k$-edge connectivity for any fixed $k$. We will introduce a general framework for such conditions and discuss recent progress on similar sufficient conditions for a variety of graph properties.
This is based on joint work with Bauer, van den Heuvel, Kahl, and Schmeichel.

Shalom Eliahou
Permutations signees et theoreme des quatre couleurs
Ce travail est en commun avec Cedric Lecouvey.

L'objet de cet expose est de presenter une nouvelle reformulation algebrique du theoreme des quatre couleurs. Etant donnees deux permutations dans le groupe symetrique Sn, de nombreux chemins vont de l'une a l'autre dans le graphe de Cayley de Sn relatif aux transpositions elementaires. Certains de ces chemins peuvent avoir une propriete supplementaire, appelee la signabilite. Celle-ci s'exprime en terme d'une comparaison entre les graphes de Cayley de Sn et du groupe hyperoctaedral Bn des permutations signees. On montrera que le theoreme des quatre couleurs est equivalent a l'affirmation que, pour tout n>=1 et toute paire de permutations dans Sn, il existe un chemin signable entre celles-ci.

Transparents de l'exposé

Eric Fusy
Bois de Schnyder en genre supérieur

Schnyder a montré en 1989 que toute triangulation plane peut etre munie de 3 arbres couvrants tel que chaque arete interne apparait exactement dans un arbre. Cette structure combinatoire, désormais appelée bois de Schnyder, a de nombreuses applications : nouveau critère de planarité pour les graphes, dessin en lignes droites sur une grille, codage, et comptage bijectif des triangulations planes. Nous proposons ici une définition des bois de Schnyder étendue au genre supérieur. Comme application nous présentons une procédure qui permet de coder les triangulations de genre g avec 4n+O(g log(n)) bits par sommet.

Benjamin Lévêque
Triangle contact representations and duality

A contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. de Fraysseix et al. proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A primal-dual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intesertection between the triangles corresponding to u and v is the same point as the intesertection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal-dual contact representation by triangles. Moreover, it can be required that the interiors of the triangles form a tiling of the triangle corresponding to the outer face and that each contact point is a node of exactly three triangles. Then, these representations are in one-to-one correspondance with generalized Schnyder woods defined by Felsner for 3-connected planar maps.

Yann Strozecki
Une approche logique des matroïdes décomposables

Les matroïdes sont des objets généralisant la notion d'indépendance linéaire. Les graphes peuvent être vus par exemple comme des matroïdes très simples. Dans cet exposé on montre comment les idées de décomposition de graphe (tree-width, branch-width) peuvent être adaptées aux matroïdes. Pour des matroïdes représentables (= matrices) de branch width fixée la décision de la logique monadique du second ordre est facile. On montre ensuite comment on peut construire des classes de matroides abstraits représentés par des arbres, afin que la logique monadique du second ordre soit également décidable en temps linéaire.

Transparents de l'exposé

Stéphan Thomassé
Coloring dense graphs via VC-dimension

Nicolas Bonichon
Spanners Géométriques : liens étroits entre triangulations de TD-Delaunay et demi-Thêta-graphes
(Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et David Ilcinkas)

Un s-spanner est un sous-graphe H d’un graphe G, tel que pour tout couple de sommets, la distance dans H soit au plus s fois la distance dans G. Les Thêta-graphes sont une famille classique de spanner du graphe Euclidien (graphe complet sur n sommets du plan dont la longueur d'une arête est égale à la distance Euclidienne entre ses extrémités). Nous montrons qu’un demi-Thêta-graphe avec thêta = pi/3 est un 2-spanner du graphe Euclidien.
Pour obtenir ce résultat nous étudions les liens étroits qu’il y a entre les 1/2-théta-graphes, les surfaces orthogonales coplanaires et les triangulations de TD-Delaunay.
Nous présenterons également plusieurs résultats secondaires et généralisations possibles liés à ces correspondances.

Jean Daligault

Je ferai une synthèse de quelques exposés de la série de conférences ALGO'09+Worker'09 qui m'ont marqués. Je parlerai d'une part d'un résultat de Marx et Razgon sur la complexité paramétrée de Multicut, et d'autre part de résultat négatifs sur l'existence de noyaux, par Holger Dell et Moritz Mueller.

Mickael Montassier (LaBRI)
Décomposition de graphes peu denses.

Soit k un entier positif. Nous montrerons que tout graphe de degré moyen maximum inférieur à 4(k+1)(k+3)/(k2+6k+6) admet une partition des arêtes en une forêt et un sous-graphe de degré maximum au plus k. La preuve de ce résultat fera intervenir une méthode de déchargement à caractère global.

Derek Corneil Dept. of Computer Science, University of Toronto
The attempt to find an application of Lexicographic Depth First Search

Lexicograph Breadth First Search (LBFS) was introduced in the mid 1970s and became very popular in the 1990s and beyond. Much of its success was based on a 4-vertex characterization of when an ordering of the vertices of a given graph could have been produced by an LBFS. The determination of similar 4-vertex characterizations for BFS and DFS led to the discovery of Lexicographic Depth First Search (LDFS). Although algorithms were developed for LDFS, applications of the new search didn't follow quickly.
Finally (in joint work with Barnaby Dalton and Michel Habib), such an application has been found. In particular, LDFS yields a new algorithm for finding the Minimum Path Cover (MPC) of a cocomparability graph G without calculating the bump number of a poset associated with G's complement. This new algorithm also finds a cutset of vertices that certifies the MPC. Futhermore, this algorithm can be applied to posets to obtain an easy minimum bump number algorithm together with a certi?cate. It is also shown that LBFS cannot be used to solve these problems.

Matthias Mnich
On Feedback Vertex Sets in Tournaments
(joint work with Serge Gaspers, formerly LIRMM)

In this talk we consider tournaments $T$, which are orientations of a complete graph. A feedback vertex set of $T$ is a subset of vertices intersecting every directed cycle of $T$. We prove that every tournament on $n$ vertices has at most $1.6740^n$ minimal feedback vertex sets and some tournaments have $1.5448^n$ minimal feedback vertex sets. This improves an old result by Moon from 1971.

Transparents de l'exposé

Joergen Bang-Jensen (University of Southern Denmark, Odense, Denmark)
Paths, cycles, trees and sub(di)graphs in directed graphs

We survey a number of recent results concerning paths, cycles or strong subdigraphs of digraphs. We illustrate the richness of the topic by a number of results and open problems in the area. The talk is based on the second edition of the book "Digraphs: Theory, Algorithms and Applications", Bang-Jensen and Gutin, to be published by Springer London 2009 as well as on a recent paper by Bang-Jensen and Kriesell on mixed linkings in digraphs.

Transparents de l'exposé