2017 - 2018

---

Vendredi 1 septembre 2017 - ​Un algorithme optimal pour ​Cycle Hamiltonien paramétré par la largeur de clique​ - Benjamin Bergougnoux (LIMOS, Clermont-Ferrand).
La largeur de clique (clique-width) est plus générale que la largeur arborescente (tree-width)​: elle est bornée dans plus de classes de graphes​,​​ dont certaines classes de graphes denses. Malgré cette généralité, elle permet de résoudre en temps FPT tous les problèmes exprimables en logique monadique du premier ordre.

D'un point de vu pratique son intérêt est limité car on ne sait toujours pas la calculer "rapidement". ​​Elle reste intéressante car elle permet d'étudier la complexité des problèmes NP-difficiles dans les graphes denses.

Je vais présenter un algorithme résolvant Cycle Hamiltonien en temps n^O(k). Cet algorithme est optimal sous ETH (Exponential Time Hypothesis) et répond à une question ouverte soulevée par Fomin et al. (SIAM. J. Computing, 2014).

Notre algorithme bat l'algorithme naïf dont le temps d'exécution est n^O(k²). Il s'appuie sur une relation d’équivalence qui se base sur un résultat amusant concernant l'existence d'une marche Eulérienne (alternant deux types d'arêtes) dans les multigraphes.

Travail en collaboration avec Mamadou M. Kanté et O-joung Kwon.

Vendredi 8 septembre 2017 11h - Large Induced 2-degenerate Subgraphs of Triangle-free Planar Graphs - Tom Kelly (University of Waterloo, Canada).
A graph is k-degenerate if every subgraph has minimum degree at most k. Studying lower bounds on the size of induced subgraphs of low degeneracy has attracted a lot of attention. In this talk we will discuss lower bounding the size of a maximum induced 2-degenerate subgraph of a triangle-free planar graph. We prove that if G is a connected triangle-free planar graph with n vertices and m edges, then G contains an induced 2-degenerate subgraph on at least four fifths of its vertices. We also prove that if G is a triangle-free planar graph on n vertices with at most n_3 vertices of degree at most three, then G contains an induced 2-degenerate subgraph on at least 7n/8 - 28n_3 vertices. Joint work with Zdenek Dvorak.

Jeudi 14 septembre 2017 10h - Domination in structured tournaments - Nicolas Bousquet (G-SCOP, Grenoble).
Salle 76 !
There exist tournaments, such as random tournaments, for which the domination number is arbitrarily large. One can naturally ask what happens if we add some structure on the tournament, for instance if the tournament can be "covered" using a bounded number of partial orders. Alon et al. showed that k-majority tournaments have bounded domination number. Gyarfas and Palvolgyi conjectured that the following is true : If a tournament admits a partition of its arc set into k quasi orders, then its domination number is bounded in terms of k. We provide a short proof that the following more general conjecture of Erdos, Sands, Sauer and Woodrow: If the arcs of a tournament T are colored with k colors, there exist a set X of at most g(k) vertices such that for every vertex v of T, there is a monochromatic path from X to v.

(joint work with William Lochet and Stéphan Thomassé)

Vendredi 15 septembre 2017 - Turan problems for sets of binary vectors - Peter Nelson (University of Waterloo, Canada).
Given a fixed set N of vectors in GF(2)^k, we study, for large n, the maximum size of a set M of vectors in GF(2)^n that does not contain a linear copy of N. We argue that such problems closely resemble analogous extremal problems for H-free graphs, and discuss a surprising matroidal analogue of chromatic number that supports this view.

Vendredi 22 septembre 2017 - On the List Coloring Version of Reed's Conjecture - Michelle Delcourt (University of Birmingham, Royaume-Uni).
Reed conjectured in 1998 the chromatic number of a graph should be at most halfway between clique number (trivial lower bound) and maximum degree plus one (trivial upper bound); Reed proved it is at most some convex combination of these quantities. Last year, Bonamy, Perrett, and Postle proved for large enough maximum degree, a fraction of 1/26 away from the upper bound holds. Using new techniques, we show the list-coloring version holds; for large enough maximum degree, a fraction of 1/13 suffices for list chromatic number. Thus, 1/13 suffices for ordinary chromatic number. This is joint work with Luke Postle.

Mardi 26 Septembre 2017 14h30 - Correspondence Coloring: A Survey - Luke Postle (University of Waterloo, Canada).
Recently introduced in 2015, correspondence coloring is a generalization of list coloring, which is a generalization of coloring introduced in the 1970s. In correspondence coloring, vertices are given lists of colors as in list coloring; however, the meaning of color is only local rather than global. In this talk, we survey what is known about correspondence coloring, how it has been used to prove results for list coloring that were not previously known, as well as some open questions.

Vendredi 13 octobre 2017 - Orientations of sparse uniform hypergraphs - William Lochet (ÉNS de Lyon et Université de Nice Sophia Antipolis).
A classical result in graph theory states that any graph G can be oriented in a way that the indegree and the outdegree of each vertex differ by at most one. In 2011 Cairo, West and Yuster tried to generalise this result to r-uniform hypergraphs, where an orientation of an hyperedge is a total ordering of its element. They conjectured an existence result of such orientations for sparse hypergraphs, of which we present a proof. The proof relies on two probabilistic tools: Moser's entropy compression method and the Lopsided Lovasz Local Lemma.

Vendredi 13 octobre 2017 15h - How to properly distinguish neighbours randomly choosing edge colours from prescribed lists? - Jakub Przybyło (AGH University, Cracovie, Pologne).
Let G=(V,E) be a graph. Consider an edge colouring c:E-> C. For a given vertex v in V, by E(v) we denote the set of all edges incident with v in G, while the set of colours associated to these under c is denoted as: Sc(v)={c(e):e in E(v)} The colouring c is called adjacent vertex distinguishing if it is proper and Sc(u) <> Sc(v) for every edge uv in E. It exists if only G contains no isolated edges. The least number of colours in C necessary to provide such a colouring is then denoted by chi'_a(G) and called the adjacent vertex distinguishing edge chromatic number of G. Obviously, chi'_a(G) >= chi'(G) >= Delta, where Delta is the maximum degree of G, while it was conjectured that chi'_a(G) <= Delta+2 for every connected graph G of order at least three different from the cycle C5. Hatami proved the postulated upper bound up to an additive constant by showing that chi'_a(G) <= Delta+300 for every graph G with no isolated edges and with maximum degree Delta>10^20.
Suppose now that every edge e in E is endowed with a list of available colours L_e. The adjacent vertex distinguishing edge choice number of a graph G (without isolated edges) is defined as the least k so that for every set of lists of size k associated to the edges of G we are able to choose colours from the respective lists to obtain an adjacent vertex distinguishing edge colouring of G. We denote it by ch'_a(G). Analogously as above, ch'_a(G) >= ch'(G), while the best (to my knowledge) general result on the classical edge choosability implies that ch'(G)=Delta+O(Delta^1/2 log^4(Delta)). Extending the thesis of this, a four-stage probabilistic argument granting ch'_a(G)=Delta+O(Delta^1/2 log^4(Delta)) for the class of all graphs without isolated edges shall be presented during the talk.
This is joint work with Jakub Kwa ́sny.

Vendredi 20 octobre 2017 - Sur le plus petit ensemble de transitions nécessaire pour connecter un graphe - 1/2 - Thomas Bellitto (LaBRI).
Une transition dans un graphe est une paire d'arêtes adjacentes, qui peuvent donc être empruntées l'une à la suite de l'autre lors d'une marche dans le graphe. Par exemple, la marche u→v→w utilise les arêtes {u,v} et {v,w} et la transition {{u,v},{ v,w}}. Un graphe à transitions interdites est un triplet (V,E,T) où T est l'ensemble des transitions autorisées. On dit qu'une marche sur un graphe est T-compatible si elle n'utilise que des transitions de T et on dit que le graphe est T-connexe s'il existe une marche T-compatible entre toute paire de sommets de V. Le problème qui nous intéresse dans cet exposé est, étant donné un graphe à transitions interdites G=(V,E,T) T-connexe, de trouver le plus petit sous-ensemble T' de T tel que G est T'-connexe. Nous étudierons tout particulièrement le cas où T contient toutes les paires d'arêtes adjacentes de E.

Mardi 24 octobre 2017 - Sur le plus petit ensemble de transitions nécessaire pour connecter un graphe - 2/2 - Thomas Bellitto (LaBRI).
Une transition dans un graphe est une paire d'arêtes adjacentes, qui peuvent donc être empruntées l'une à la suite de l'autre lors d'une marche dans le graphe. Par exemple, la marche u→v→w utilise les arêtes {u,v} et {v,w} et la transition {{u,v},{ v,w}}. Un graphe à transitions interdites est un triplet (V,E,T) où T est l'ensemble des transitions autorisées. On dit qu'une marche sur un graphe est T-compatible si elle n'utilise que des transitions de T et on dit que le graphe est T-connexe s'il existe une marche T-compatible entre toute paire de sommets de V. Le problème qui nous intéresse dans cet exposé est, étant donné un graphe à transitions interdites G=(V,E,T) T-connexe, de trouver le plus petit sous-ensemble T' de T tel que G est T'-connexe. Nous étudierons tout particulièrement le cas où T contient toutes les paires d'arêtes adjacentes de E.

Vendredi 27 octobre 2017 - Frankl's conjecture for large families - Ilan Karpas (Hebrew University of Jerusalem) .
A family F of subsets of [n] is called union-closed, if for any two sets A and B in F, A ∪ B is also in F. A famous conjecture of Frankl from 1979 states that for any union-closed family F ≠ ∅ of subsets of [n], there is some element i ∈ [n] that occurs in at least half of the members of F.
We show that the conjecture holds if F is a family of subsets of [n], and |F| ≥ (1/2 - c)2^n, for some absolute constant c>0. This improves a result of Eccles from 2013, who proved that the conjecture holds for |F| ≥ (2/3 - 1/104)2^n.
We use methods from boolean analysis to prove the claim, as well as a structural theorem about the upper shadow of union-closed families. We end the talk by discussing some new conjectures regarding union-closed families.

Vendredi 3 novembre - Pas de GT cause vacances.

Vendredi 17 novembre - Pas de GT cause JGA.

Vendredi 24 novembre 2017 - Homomorphisms of sparse signed graphs - Reza Naserasr (IRIF, Paris).
The notion of homomorphism of graphs has recently been extended to homomorphism of signed graphs in a joint work with E. Rollova and E. Sopena. A key interest in this extension, among many, is that it provides a more intuitive and, at the same time, stronger connection with the notion of minor of (signed) graphs.
In this talk I will present some results from a joint work with C. Charpentier and E. Sopena concerning homomorphisms of sparse signed graphs. Two main results to be mentioned:
Theorem. For any graph G of maximum average degree less than 8/3 and any signature Sigma of G, the signed graph (G,Sigma) maps to (K_4,e). Furthermore, 8/3 is the best possible value here.
As a bipartite analogue of Jaeger-Zhang Conjecture, we propose the following
Conjecture. Every signed bipartite planar graph of unbalanced girth at least 4k-2 maps to the unbalanced cycle of length 2k.
In support of this conjecture, we prove that the claim would hold for signed bipartite planar graphs of unbalanced girth at least 8k.

Vendredi 24 novembre 2017 15h - Graph classes defined by excluding Truemper Configurations - Nicolas Trotignon (ÉNS de Lyon, Lyon).
Tremper configurations are simple structures : prisms, thetas, pyramids and wheel. A prism is a graph made of two disjoint triangles that are matched by three disjoint paths. A theta is a graph made of two disjoint vertices that are linked by three disjoint paths. A pyramid is a graph made of a vertex and triangle that are linked by three disjoint paths. A wheel is a chordless cycle together with a vertex disjoint from it, and with at least three neighbors in it. In this abstract we omitted technical requirements on the lengths of the paths and cycles.

Truemper configuration play an important in role in several theorems. For instance, they appear in an old characterisation of graph with no cycle through three prescribed vertices (due to Watkins and Mesner). They appear in a theorem of Truemper about signing edges of a graph in such way that several constraints on the parity of cycles are satisfied. And they play an important role in many recent decomposition theorems in structural graph theory (perfect graphs, even-hole-free graphs, claw-free graphs, bull-free graphs, and some others).

The talk will focus on this last aspect. I will explain why Truemper Configuration are important in decomposition theorems. Then I will present a project about systematically studying the classes of graph where Truemper configuration are excluded.

Joint work with Marko Radovanovic and Kristina Vuskovic.

Vendredi 1er décembre 2017 10h salle de conférence (IMB) - Soutenance de thèse "Geometric Distance Graphs, Lattices and Polytopes" - Philippe Moustrou (LaBRI).

Vendredi 1er décembre 2017 - Largeur de clique : Majorations polynomiales en termes de largeur arborescente. - Bruno Courcelle (LaBRI).
Dans le cas le plus général, la largeur de clique est exponentielle en la largeur arborescente. Mais pour des classes de graphes "peu denses", notamment celles étudiées par Nesetril et Ossona de Mendez, on a des majorations polynomiales et même souvent linéaires (cas de l'expansion bornée). Mon exposé examine ces majorations. Un algorithme unique (le même pour tous les types de graphes) convertit une décomposition arborescente en terme relatif à la largeur de clique. Les décompositions arborescentes sont fournies sous la forme d'un arbre "normal" analogue à un arbre d'exploration en profondeur.

Mardi 5 décembre 2017 11h - Séminaire commun avec MF - La coloration de graphe dans le modèle LOCAL - Partie I - Cyril Gavoille (LaBRI).
L'objectif de cette série d'exposés est de faire découvrir un résultat aussi élégant que surprenant du calcul distribué, à savoir la 3-coloration des n-cycles en temps log*(n). On démontrera l'optimalité de ce résultat ainsi que ces généralisations au cas des graphes arbitraires. Partie I: - Le modèle LOCAL - Le problème de la coloration - Coloration des 1-orientations en 6 couleurs - De 6 à 3 couleurs - Cas des graphes arbitraires

Vendredi 8 décembre 2017 - A29 salle 107 - Short cycle covers of cubic graphs - Robert Lukoťka (Comenius University, Bratislava).
A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph on m edges has a cycle cover of length at most 212/135 m (~ 1.570 m). Moreover, if the graph is cyclically 4-edge-connected we obtain a cover of length at most 47/30 m (~ 1.567 m).

Mardi 12 décembre 2017 11h - Séminaire commun avec MF - La coloration de graphe dans le modèle LOCAL - Partie II - Cyril Gavoille (LaBRI).
Partie II: - Coloration rapide des cycles - Borne inférieure en log* sur la coloration des cycles (preuve de Linial) - Une preuve alternative fondée sur le théorème de Ramsey - Etat de l'art

Mardi 19 décembre 2017 - Pique-nique et problèmes ouverts.

Vendredi 12 janvier 2018 - Pas de GT cause AG LaBRI.

Mardi 16 janvier 2018 10h40 salle 76 - Approximabilty of Hub Allocation Problems - Li-Hsuan Chen (National Cheng Kung University, Taiwan).
Given a metric graph G = (V, E, w), a center c, and an integer p, the Star p-Hub Center problem is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children and the diameter of T is minimized. Those children of c in T are called hubs. A similar problem called the Single Allocation p-Hub Center problem is to find a spanning subgraph H^* of G such that (i) C^* is a clique of size p in H; (ii) V \ C^* forms an independent set in H^*; (iii) each v in V \ C^* is adjacent to exactly one vertex in C^*; and (iv) the diameter D(H^*) is minimized.

The vertices selected in C^* are called hubs and the rest of vertices are called non-hubs. Both Star p-Hub Center problem and Single Allocation p-Hub Center problem are NP-hard and have applications in transportation system, telecommunication system, and post mail system. In this talk, I will give 5/3-approximation algorithms for both problems. Moreover, I will give a proof to show that for any ε > 0, both problems have no (1.5-ε)-approximation algorithms unless P = NP. Suppose that the input graph ε is a ∆ β-metric, for someβ ≥ 1/2, which satisfies the β-triangle inequality, i.e., w(u, v) ≤ β(w(u, x) + w(x, v)) for all vertices u, v, x ∈ V. We can further show that for any ε> 0, to approximate the two hub allocation problems to a ratio g(β) − ε is NP-hard and give r(β)-approximation algorithms where g(β) and r(β) are functions of β.

Mardi 16 janvier 2018 11h20 salle 76 - An efficient fixed-parameter algorithm for the 2-plex bipartition problem - Ling-Ju Hung (National Cheng Kung University, Taiwan).

Given a graph G = (V, E), an s-plex S ⊆ V is a vertex subset such that for v ∈ S the degree of v in G[S] is at least |S| − s. An s-plex bipartition P = (V1, V2) is a bipartition of G = (V, E), V = V1 ] V2, satisfying that both V1 and V2 are s-plexes. Given an instance G = (V, E) and a parameter k, the s-Plex Bipartition problem asks whether there exists an s-plex bipartition of G such that min{|V1|, |V2|} ≤ k. The s-Plex Bipartition problem is NP-complete. However, it is still open whether this problem is fixed-parameter tractable. In this talk, I will present a fixed-parameter algorithm for 2-Plex Bipartition running in time O^*(2.4143k). A graph G = (V, E) is called defective (p, d)-colorable if it admits a vertex coloring with p colors such that each color class in G induces a subgraph of maximum degree at most d. A graph G admits an s-plex bipartition if and only if the complement graph of G, G ̄, admits a defective (2, s−1)-coloring such that one of the two color classes is of size at most k. By applying our fixed-parameter algorithm as a subroutine, one can find a defective (2, 1)-coloring with one of the two colors of minimum cardinality for a given graph in O^*(1.5539n) time where n is the number of vertices in the input graph.

Lundi 22 janvier 2018 - Exposé GO-friendly chez AlgoDist: On the simplification of temporal cliques - Arnaud Casteigts

Vendredi 26 janvier 2018 - Résultats et problèmes de coloration étoilée des arêtes d'un graphe - André Raspaud (LaBRI).
A star edge-coloring of a graph G as a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. This notion is intermediate between acyclic edge-coloring, when every 2-colored subgraph must be only acyclic, and strong edge-coloring, when every 2-colored connected subgraph has at most two vertices. I this talk we will give a short survey of these notions. We will present the recent results and not solved problems.

Vendredi 2 février 2018 - Partitioning a graph into isomorphic subgraphs - Marthe Bonamy (LaBRI).
Given a graph G and a subgraph H of G, we can wonder whether G admits a perfect H-packing, i.e. whether we can partition the vertices of G into (induced) copies of H. A classical example of such a question is whether a graph admits a perfect matching. There does not seem to be any good sufficient conditions for G to admit a perfect H-packing. Here, we investigate when a sufficiently high Cartesian power of G admits a perfect H-packing. We generalize a theorem of Gruslys for hypercubes to powers of even cycles, and disprove a conjecture of Gruslys as well as one by Gruslys, Leader and Tan that considers the edge setting. This type of questions has ramifications far beyond the scope of graph theory.
This is joint work with Natasha Morrison and Alex Scott.

Lundi 12 février 2018 - Exposé GO-friendly chez AlgoDist: Distributed Recoloring: the addition of colors - Mikaël Rabie

Vendredi 2 mars 2018 - Codage optimal des triangulations toriques essentiellement 4-connexes - Nicolas Bonichon (LaBRI).
Transversal structures (also known as regular edge labelings) are combinatorial structures defined over 4-connected plane triangulations with quadrangular outer-face. They have been intensively studied and used for many applications (drawing algorithm, random generation, enumeration...). In this paper we introduce and study a generalization of these objects for the toroidal case. Contrary to what happens in the plane, the set of toroidal transversal structures of a given toroidal triangulation is partitioned into several distributive lattices. We exhibit a subset of toroidal transversal structures, called balanced, and show that it forms a single distributive lattice. Then, using the minimal element of the lattice, we are able to encode optimally essentially 4-connected toroidal triangulations.

Vendredi 9 mars 2018 - Résolution du problème de recherche d’arbre couvrant ayant un minimum de branchements - Massinissa Merabet (ENSIIE, Paris).
Étant donné un graphe G = (V, E) non orienté, un sommet de G est dit sommet de branchement s’il a un degré strictement supérieur à deux. Le problème Minimum Branch Vertices (MBV) consiste à trouver un arbre couvrant de G ayant un minimum de sommets de branchement. Il trouve son intérêt pratique principalement dans le routage Broadcast appliqué aux réseaux optiques. En effet, étant le sous-graphe connexe permettant de couvrir les sommets en utilisant un minimum de liens, l’arbre est une structure classique pour ce type de routage. Dans les réseaux tout-optique, les fonctions de commutation et de routage sont fournies par les brasseurs optiques OXC (optical cross-connect). Seuls certains OXC, onéreux, peuvent diviser une longueur d’onde entrante vers plusieurs ports de sortie grâce à un coupleur optique afin d’offrir un service Broadcast. Cette division génère un affaiblissement du faisceau lumineux ainsi qu’une dégradation du signal. Un sommet de branchement dans l’arbre couvrant correspond à un sommet équipé de coupleur optique dans le réseau. Afin de réduire les coûts et de limiter les pertes, il convient donc de minimiser leur nombre, tout en garantissant la faisabilité du routage. Le problème MBV est NP-difficile et n’est pas approximable en temps polynomial avec un rapport constant. Je propose une méthode de résolution exacte utilisant la program- mation linéaire en nombres entiers, un algorithme polynomial donnant une solution approchée sans garantie, ainsi qu’un noyau exponentiel de taille O(k2^k), où le paramètre k représente le nombre de sommets dont on ne peut décider en temps polynomial s’ils sont sommets de branchement dans une solution optimale. L’existence de ce noyau démontre que ce problème est FPT vis-à-vis de k. Enfin, des expérimentations sur des graphes aléatoires permettront d’évaluer ces différentes approches.

Lundi 26 mars 2018 - Exposé GO-friendly chez AlgoDist: Distributed coloring in sparse graphs with fewer colors - Marthe Bonamy.

Mardi 27 mars 2018 11h - Séminaire commun avec MF - Limitations of treewidth for problems beyond NP - Valia Mitsou (IRIF).
In this seminar, we will take a closer look at the parameterized complexity of ∃∀SAT, the prototypical complete problem of the class $\Sigma^p_2$, the second level of the polynomial hierarchy. We will provide tight fine-grained bounds on the complexity of this problem with respect to the most important structural graph parameters. Specifically we will show that ∃∀SAT cannot be solved in time $2^{2^{o(tw)}}$ under the Exponential Time Hypothesis. More strongly, we establish the same bound with respect to the formula’s primal vertex cover, a much more restrictive measure. Our reduction is a 'textbook' reduction that could be used in order to provide similar lower bounds for problems in the second level of the polynomial hierarchy.

Mercredi 28 au Vendredi 30 mars 2018 - Kick-off meeting du projet ANR Hosigra.

Vendredi 6 avril 2018 - Quelques applications de la méthode polynomiale - Éric Balandraud (IMB).
Après un rappel des énoncés équivalents du Combinatorial Nullstellensatz, je vous propose de développer quelques exemples d'applications de ce joli résultat dans des contextes combinatoires variés (et variables selon la discussion).

Lundi 9 avril 2018 - Exposé GO-friendly chez AlgoDist: (Méta)-noyaux constructifs et linéaires dans les graphes peu denses - Valentin Garnero.

Vendredi 13 avril 2018 - Pas de GT cause vacances.

Vendredi 20 avril 2018 - Pas de GT cause vacances.

Vendredi 4 mai 2018 - Total List Coloring of Planar Graphs - Théo Pierron (LaBRI).
Total coloring is a variant of edge coloring where both vertices and edges are to be colored. A graph is totally k-choosable if for any list assignment of k colors to each vertex and each edge, we can extract a proper total coloring. In this setting, a graph of maximum degree D needs at least D+1 colors. For a planar graph, Borodin proved in 1989 that D+2 colors suffice when D is at least 9. In this talk, we explain how to improve this lower bound to 8 using the discharging method and the Combinatorial Nullstellensatz.

Vendredi 18 mai 2018 - Power domination in triangular grids - Claire Pennarun (LIRMM, Montpellier).
The concept of power domination emerged fron the problem of monitoring electrical systems. Given a graph G and a set S \subseteq V(G), a set M of monitored vertices is built as follows: at first, M contains only the vertices of S and their direct neighbors, and then each time a vertex in M has exactly one neighbor not in M, this neighbor is added to M. The power domination number of a graph G is the minimum size of a set S such that this process ends up with the set M containing every vertex of G. We here give some key ideas to the proofs of the exact power domination number of triangular grids with hexagonal-shaped border, and of triangular grids with triangular-shaped border.

Vendredi 25 mai 2018 - The price of connectivity for domination - Paul Ouvrard (LaBRI).
The price of connectivity for dominating set in a graph G is the ratio between the minimum sizes of a connected dominating set and a dominating set of G. It is always at most three, and Zverovich characterized the class of graphs such that this ratio equals one. In this talk, we give a proof of a conjecture of Camby and Schaudt by characterizing the class of graphs with price of connectivity at most two. This is joint work with Marthe Bonamy, Nicolas Bousquet and Tereza Klimošová.

Vendredi 1 juin 2018 - Vertex partition problem of graphs - Min Chen (Zhejiang Normal University).
Let G = (V, E) be a graph. We say that a vertex partition of G is a (G₁, · · · , G_m)-partition if V(G) can be partitioned into m sets V₁, · · · , V_m such that for each 1<= l <= m, the subgraph G[V_l] belongs to G_l. For simplicity, we denote by I, F, ∆_d and F_d the class of independent sets, the class of forests, the class of graphs with maximum degree d, and the class of forests with maximum degree d.

The famous Four-Color Theorem states that every planar graph has an (I, I, I, I)-partition. By investigating acyclic coloring problems, Borodin showed that every planar graph has an (I, F, F)-partition. At the same time, Borodin and Glebov showed that every planar graph with girth g >= 5 has an (I, F)-partition. Moreover Borodin et al. constructed a planar graph with girth g=6 having no I,∆_d)-partition for any d. Naturally, it seems to be interesting to study (I, ∆_d)-partition (or (I, F_d)-partition) problems for planar graphs with girth g >= 7.

The maximum average degree, mad(G), of a graph G is the maximum of (2*|E(H)|)/|V(H)| over all subgraphs H of G. Borodin and Kostochka in [O. V. Borodin, A. V. Kostochka, Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B 104 (2014) 72-80.] proved that every graph G with mad(G) <= 8/3 admits an (I, ∆₂)-partition and every graph G with mad(G) <= 14/5 admits an (I, ∆₄)-partition. Recently, we obtain a strengthening result by considering potential function to show that for any d >=2, every graph G with mad(G) <= 2 + d/d+1 admits an (I, F_d)-partition.

Vendredi 8 juin 2018 - Exposés de stagiaires M2 - Tobias Castanet et Dimitri Lajou.
14h-14h30: Achromatic number of signed graphs - Dimitri Lajou
We define the achromatic number of a graph as the order of the largest clique reachable by identifying vertices of the graph. In this talk, we will extend this concept to signed graphs (graphs with positive and negative edges where for each vertex v, we can invert the signs of all edges adjacent to v) and see some results on the achromatic number of signed graphs.

14h30-15h: Coloration par liste de graphes signés - Tobias Castanet
Un graphe 2-arête-coloré est un graphe dont chaque arête est associée à un signe, positif ou négatif. Un graphe signé est un graphe 2-arête-coloré pour lequel on autorise une opération supplémentaire, appelée "switch" qui consiste à désigner un sommet, et à inverser le signe de toutes les arêtes incidentes à ce sommet. Deux graphes signés sont équivalents si l’on peut passer de l’un à l’autre par une séquence de "switches". Il s’agit ici d’initier l’étude de la coloration par liste des graphes 2-arête-colorés et des graphes signés. Nos principaux résultats concernent les graphes chemins 2-arête-colorés, ainsi que les graphes thêta 2-arête-colorés et signés.

Vendredi 15 juin 2018 - (Weak) hamiltonicity in graphs - Petru Valicov (LIS, Marseille).
In an attempt to solve the Four Color Problem, Tait conjectured that every planar cubic 3-connected graph is Hamiltonian. Once this statement was disproved, several other related questions of the type "every bipartite (planar) 3-connected cubic graph is Hamiltonian", emerged. On the other hand a conjecture of Neumann-Lara asserts that every planar oriented graph can be vertex-partitioned into two acyclic sets. This can be seen as a directed version of Tait's Hamiltonicity Conjecture. In this talk we explain how all these conjectures together with other similar questions fit in the same framework related to cuts in matchings. We show then a construction of a 3-edge connected oriented graph satisfying the property that for every even subgraph E, the graph obtained by contracting the edges of E is not strongly connected. This disproves a recent conjecture of Hochstättler. At the end we will provide experimental evidence for Neumann-Lara's conjecture and discuss on tools that might be helpful to search for counterexamples. Joint work with Kolja Knauer.

Vendredi 22 juin 2018 - Density of sets avoiding distance 1 in the euclidean plane - Antoine Sedillot (LaBRI).
In the Euclidean space R^n, a subset S is said to avoid distance 1 if |x-y| != 1 for all x,y in S. In terms of graphs, a set avoiding distance 1 is an independent set of the unit-distance graph on R^n. In this talk, we study the supremum of the densities of such sets in the case of the Euclidean plane, we denote it by m_1(R^2). Paul Erdős conjectured that m_1(R^2) < 1/4. Up to now, the best estimation of m_1(R^2) is 0.2293 m <= m_1(R^2) <= 0.2587. We will explain how we managed to lower the upper bound to m_1(R^2) <= 0.2568.

Lundi 25 juin 2018 - Pique-nique de thème.

Mardi 26 juin 2018 - Parking in Z - Alexander Roberts (University of Oxford).
At each point in Z place a car with probability 1/2 and otherwise place a parking spot. The cars then move independently like random walks until they find a free parking spot and stop. We show that the expected journey length of a car by time t is within a log factor of t^{3/4}. Joint with Michał Przykucki and Alex Scott.

Vendredi 29 juin 2018 - Approximating the position of a hidden agent in a graph - Hannah Guggiari (University of Oxford).
A cat and mouse play a pursuit and evasion game on a connected graph G with n vertices. The mouse moves to vertices m_1,m_2,... of G where m_i is in the closed neighbourhood of m_{i-1} for i>1. The cat tests vertices c_1,c_2,... of G without restriction and is told whether the distance between c_i and m_i is at most the distance between c_{i-1} and m_{i-1}. The mouse knows the cat's strategy, but the cat does not know the mouse's strategy. We will show that the cat can determine the position of the mouse up to distance O(sqrt{n}) within finite time and that this bound is tight up to a constant factor. This disproves a conjecture of Dayanikli and Rautenbach. This is joint work with Alexander Roberts and Alex Scott.

Mardi 3 juillet 2018 - Increasing the Matching Preclusion Number from 1 to 2- Moritz Mühlenthaler (TU Dortmund University).

The matching preclusion number of a graph is the minimal number of edges whose removal destroys all perfect matchings. We provide algorithms and hardness results for the task of increasing the matching preclusion number from one to two in bipartite graphs at minimal cost. Our motivation is to make matchings of a graph robust against the failure of a single edge. Our methods rely on a close relationship to the classical strong connectivity augmentation problem. For the unit weight problem we provide a deterministic $\log_2 n$-factor approximation algorithm, as well as polynomial-time algorithms for graphs of bounded treewidth and chordal-bipartite graphs. For general weights we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm.

Mercredi 4 juillet 2018 - Enumerating colourings via clique-width and colour renaming - Michael Raskin (LaBRI).
Graph colourings are studied for many different reasons and from many different points of view. Courcelle's theorem allows to enumerate the graph colourings of bounded-clique-width graphs in linear (in the size of the graph, but not clique-width or number of colours) time.

In the talk I will show how to apply the symmetry between colours to improve the performance of the colouring enumeration with clique-width representation.

Jeudi 5 juillet 2018 15h30 - DP-coloring - Seog-Jin Kim (University of Konkuk).
DP-coloring was introduced by Dvorak and Postle (2015) to study list coloring. DP-coloring of a graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. In this talk, we will give an overview of DP-coloring, and present recent results in DP-coloring.

Vendredi 6 juillet 2018 - AG LaBRI + barbecue.

Mercredi 11 juillet 2018 10h - Maximum Scatter TSP in Doubling Metrics - Tobias Mömke (Universität Bremen).

We study the problem of finding a tour of n points in which every edge is long. More precisely, we wish to find a tour that visits every point exactly once, maximizing the length of the shortest edge in the tour. The problem is known as Maximum Scatter TSP, and was introduced by Arkin et al. (SODA 1997), motivated by applications in manufacturing and medical imaging. Arkin et al. gave a 0.5 -approximation for the metric version of the problem and showed that this is the best possible ratio achievable in polynomial time (assuming P !=NP). Arkin et al. raised the question of whether a better approximation ratio can be obtained in the Euclidean plane.

We answer this question in the affirmative in a more general setting, by giving a (1-epsilon)-approximation algorithm for d-dimensional doubling metrics, with running time \tilde{O}(n^^3 + 2^(O(K log K))), where K <= ( 13/epsilon)^d. As a corollary we obtain (i) an efficient polynomial-time approximation scheme (EPTAS) for all constant dimensions d, (ii) a polynomial-time approximation scheme (PTAS) for dimension d = (log log n)/c, for a sufficiently large constant c, and (iii) a PTAS for constant d and epsilon = Omega(1/log log n). Furthermore, we show the dependence on d in our approximation scheme to be essentially optimal, unless Satisfiability can be solved in subexponential time.

Mardi 17 juillet 2018 10h00 - Structural Parameterization of Geometric Intersection Graphs - Dibyayan Chakraborty (Indian Statistical Institute, Kolkata, India).
Consider a geometric intersection graph class which is NP-Hard to recognise. What can be a "natural" approach to study the structure of such classes? In this presentation, we propose such an approach and talk about the success (and failures) when applied on Rectangle Intersection graphs (it is NP-Hard to recognise such graphs). We shall introduce a parameter called "stab number" of rectangle intersection graphs and study the structure of those with "low stab number". We shall see how this parameter can be used to obtain necessary conditions for a graph to have a rectangle intersection representation.

Mardi 17 juillet 2018 11h00 - A brief overview of oriented coloring and its variants - Sagnik Sen (RamaKrishana Mission Educational and Research Institute, Kolkata, India).
Vertex coloring of a graph $G$ with $n$-colors can be equivalently thought to be a graph homomorphism (edge preserving vertex mapping) of $G$ to the complete graph $K_n$ of order $n$. So, in that sense, the chromatic number $\chi(G)$ of $G$ will be the order of the smallest complete graph to which $G$ admits a homomorphism to. As every graph, which is not a complete graph, admits a homomorphism to a smaller complete graph, we can redefine the chromatic number $\chi(G)$ of $G$ to be the order of the smallest graph to which $G$ admits a homomorphism to. Of course, such a smallest graph must be a complete graph as they are the only graphs with chromatic number equal to their order. Using the notion of graph homomorphism the concept of vertex coloring can be generalized for oriented graphs, that is, directed graphs without cycles of length at most 2.

Using graph homomorphism or otherwise, researchers have defined analogous versions of different other coloring related problems and parameters, namely, cliques, edge coloring, total coloring, fractional coloring, list coloring, complete coloring etc. for oriented graphs and studied their different aspects. In this talk we will give a brief overview on homomorphism and coloring of oriented graphs, present some open questions in this domain and mention some of our results as part of it.