Vendredi 13 septembre 2019 -Induced star arboricity and injective edge-coloring of graphs - André Raspaud (LaBRI).
The induced star arboricity (isa(G)) of a graph G is a new parameter introduced in 2019 by Axenovich et al.,

it is defined as the smallest number of induced star-forests covering the edges of G.

An injective edge-coloring c of a graph G is an edge coloring such that if e_1, e_2 and e_3 are three consecutive edges in G (they are consecutive if they form a path or a cycle of length three), then e_1 and e_3 receive different colors. The minimum integer k such that G has an injective k-edge-coloring is called injective chromatic index of G (chi'_{inj}(G)). This parameter was introduced in 2015 by Cardoso et al., motivated by the Packet Radio Network problem.

We will first prove that for any graph G we have isa(G)=chi'_{inj}(G). We will give some new upper bounds for this last parameter and we prove that if G is a subcubic graph with maximum average degree less than 16/7 $(resp. 8/3, 3), then G admits an injective edge-coloring with at most 4 (resp. 6, 7) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs. For this purpose, we do not use the discharging method but rather we use the fundamental structural properties of the subcubic graphs and outerplanar subcubic graphs.

This is a joint work with Baya Ferdjallah and Samia Kerdjoudj.

Vendredi 20 septembre 2019 - Shorter Implicit Representation for Planar Graphs - Cyril Gavoille (LaBRI).
A graph U is an induced-universal graph for a given family of graphs F if every graph of F is isomorphic to an induced-subgraph of U. A challenging question is to construct induced-universal graphs of smallest size, i.e., with the minimum number of vertices. We construct an induced-universal graph of size n^(4/3+o(1)) for the family of all n-vertex planar graphs. This is the first sub-quadratic bound for planar graphs. Our construction generalizes to the family of graphs of Euler genus at most g. The size of the universal graph is the same, up to a lower-order term depending on g.

Our construction is based on a shorter implicit representation of planar graphs. We show how to assign to each label of any planar graph a label of (4/3)*log(n) + O(loglog(n)) bits such that adjacency between any two vertices can be decided by a fixed procedure that examines only their labels.

This is a joint work with Marthe Bonamy and Michal Pilipczuk.

Vendredi 11 octobre 2019 - "A connected version of the graph coloring game" - Éric Sopena (LaBRI).
The graph coloring game is a two-player game in which, given a graph G and a set of k colors, the two players, Alice and Bob, take turns coloring properly an uncolored vertex of G, Alice having the first move. Alice wins the game if and only if all the vertices of G are eventually colored. The game chromatic number of a graph G is then defined as the smallest integer k for which Alice has a winning strategy when playing the graph coloring game on G with k colors. In this talk, we introduce and study a new version of the graph coloring game by requiring that, after each player's turn, the subgraph induced by the set of colored vertices is connected.

Vendredi 25 octobre 2019 - "On directed versions of the 1-2-3 Conjecture and the 1-2 Conjecture" - Mariusz Wozniak (Krakow, Pologne).
Let G = (V, E) be a graph. Given an integer k, a k-coloring (labeling) of G is a function f : E → {1, 2, . . . , k}. The coloring f can be represented by substituting each edge e of G by a multiedge with multiplicity f(e). The degree of x in the respective multigraph equals the sum of labels around a vertex x. The 1-2-3 Conjecture says that for graphs without isolated edges there exists a 3-coloring f such the the corresponding multigraph is locally irregular i.e. for each edge xy of G we have σ(x) = σ(y) where σ(x) = Sum_{x in e} f(e). The 1-2 Conjecture refers to the case when we also color the vertices. During the talk we shall look at the directed versions of these problems. We will discuss the results contained in the papers listed in the references below.

References
[1] E. Barme, J. Bensmail, J. Przyby lo, M. Wo´zniak, On a directed variation of the 1-2-3 and 1-2 Conjectures, Discrete Appl. Math. 217 (2017) 123–131.
[2] O. Baudon, J. Bensmail, E. Sopena, An oriented version of the 1-2-3 Conjecture, Discuss. Math. Graph Theory 35(1) (2015) 141–156.
[3] M. Borowiecki, J. Grytczuk, M. Pil´sniak, Coloring chip configurations on graphs and digraphs, Inform. Process. Lett. 112 (2012) 1–4.
[4] M. Horˇn´ak, J. Przyby lo, M. Wo´zniak, A note on a directed version of the 1-2-3 Conjecture, Discrete Applied Math. 236 (2018), 472-476.

Vendredi 8 novembre 2019 - "10 years of identification problems in graphs: selected topics" - Florent Foucaud (LaBRI).
This talk will address selected topics in the area of identification problems in graphs and other discrete structures. In this type of problems, we wish to select a small set of elements (usually vertices, but sometimes edges, paths, etc) with the goal of distinguishing a set of structures (such as the vertices or the edges of the graph) by means of membership, neighborhood or distances to the elements in the solution set. We will highlight a number of interesting results, problems and conjectures in the area.

Jeudi 21 novembre (salle 76) - "Defective DP-colorings of sparse multigraphs" - Alexandr Kostochka (University of Illinois at Urbana-Champaign).
We introduce and study defective DP-colorings of graphs and multigraphs, concentrating on colorings with two colors. In this setting, for each vertex of a (multi)graph G, the list L(v) = {p(v), r(v)} has two colors, and we say that G is DP-(i, j)-colorable if for every 2-fold cover H(G) of G, one can choose a color ϕ(v) ∈ L(v) for each vertex v so that if ϕ(v) = p(v) (respectively, ϕ(v) = r(v)), then ϕ(v) is adjacent to at most i (respectively, j) other chosen colors.
We prove exact lower bounds on the number of edges in DP-(i, j)-critical n-vertex multigraphs for all pairs (i, j), and in simple DP-(i, j)-critical n-vertex graphs — for (i, j) ∈ { (1, 1),(2, 2) }. For some pairs (i, j), our bounds for defective DP-colorings are better than known bounds for ordinary defective colorings. This is joint work with Yifan Jing, Fuhong Ma, Pongpat Sittitrai and Jingwei Xu.

Vendredi 22 novembre 2019 - "Split-decomposition" pour des graphes orientés et non orientés; majorations de la largeur de clique" (en français) - Bruno Courcelle (LaBRI).
From split decompositions we derive bounds on clique-width, for directed and undirected graphs. We also derive a notion of context-free graph grammar by generalizing the standard notion of substitution of a graph for a vertex, that underlies the theory of modular decomposition.

For handling directed graphs, and expressing split decompositions in terms of graph substitution, we need a more involved notion of substitution. Whereas for undirected graphs, we distinguish « dead » vertices from « live » ones, for directed graphs, we need three types of live vertices, in order to encode three types of connections between two vertices u and v : from u to v (only), from v to u (only) or in both directions.

We prove that the clique-width of a directed graph G is bounded by 8k+1, where k is the maximum clique-width of a component of a graph-labelled tree that defines G.

The full article in Discrete Applied Math : https://www.sciencedirect.com/science/article/abs/pii/S0166218X19303099%25center%25%25center%25

Vendredi 13 décembre 2019 - 9h-9h45 - Graph representation of circular codes - François Pirot (G-SCOP).

The discovery of the DNA structure by Watson and Crick in 1953 spurred a new branch of mathematical biology, which overlaps the theory of block codes, that is, codes consisting of words of a fixed length over some finite alphabet. There are several relevant notions associated to block codes; from most to less restrictive, a block code X can be strong-comma-free (the words of X do not overlap), comma-free (no word from X appears as a proper factor of a word in X2), or k-circular (every word of Xk admits a unique decomposition into words of X when read of a cycle) — if X is k-circular for every k∈N, we say that it is circular. In biology, all these properties imply that it is always possible to retrieve the reading frame in a DNA sequence in order to decompose it into codons (words of length 3).

We describe a graph representation of codes which encapsulates its various properties. By taking advantage of this representation, we are able to give a full characterisation of maximum codes on dinucleotides (words of length 2), of maximal strong-comma-free codes on ℓ-nucleotides (words of any fixed length ℓ), and of maximum comma-free codes on trinucleotides (words of length 3). Finally, we will discuss the optimal value of k(n,ℓ) such that k(n,ℓ)-circularity implies circularity, for all codes on ℓ-nucleotides over an alphabet of cardinality n.

Vendredi 13 décembre 2019 - 9h45-10h30 - Sur les cycles dans les graphes planaires et 1-planaires - François Dross (University of Warsaw, Poland).

Vendredi 13 décembre 2019 - 10h45-11h30 - Composing DP algorithms by treewidth to solve diversity problems - Julien Baste (Universität Ulm, Germany).

Vendredi 13 décembre 2019 - 11h30-12h15 - Counting independent sets in strongly orderable graphs - Marc Heinrich (University of Leeds, United Kingdom).

Vendredi 13 décembre - 12h15-13h30 - Pique-nique de thème.

Vendredi 13 décembre 2019 - 13h30-14h - Pré-audition de François Pirot (G-SCOP).

Vendredi 13 décembre 2019 - 14h15-14h45 - Pré-audition de François Dross (University of Warsaw, Poland).

Vendredi 13 décembre 2019 - 15h-15h30 - Pré-audition de Julien Baste (Universität Ulm, Germany).

Vendredi 13 décembre 2019 - 15h45-16h15 - Pré-audition de Marc Heinrich (University of Leeds, United Kingdom).

Vendredi 10 janvier 2020 - Cyclically covering subspaces - Carla Groenland (University of Oxford, Royaume-Uni).

A subspace of F_2^n is called cyclically covering if every vector in F_2^n has a cyclic shift which is inside the subspace. Let h_2(n) denote the largest possible codimension of a cyclically covering subspace of F_2^n. We show that h_2(p) = 2 for every prime p such that 2 is a primitive root modulo p, which, assuming Artin’s conjecture, answers a question of Peter Cameron from 1991.

In this talk, I will try to explain how we reduce the problem to a problem on finding odd subgraphs in which each vertex has odd outdegree in directed Cayley graphs, how additive combinatorics comes to the rescue and which open problems I would like to see solved.

This is joint work with James Aaronson and Tom Johnston.

Vendredi 17 janvier 2020 - "On minimizing the energy of a graph representation" - Alexandra Wesolek (Simon Fraser University, Canada).
Graph representations are the generalization of graph drawings from the plane to higher dimensions. As for graph drawings in the plane, representations can give insights and intuitions about their represented graphs. We discuss spherical representations, where the vertices lie on a unit sphere such that the origin is their barycenter. For example, a canonical way of representing a complete graph Kn on n vertices is by drawing a regular simplex with its vertices on the n − 1 -dimensional sphere. Such a drawing minimizes the sum of the squared edge lengths over all spherical graph representations of Kn and this sum is called the energy of the graph representation. Previously, this energy has been studied using spectral graph theory, while we explore a new approach using semidenite programming. We determine the minimum energy for vertex-transitive graphs, distance-regular graphs and give asymptotic tight bounds for random regular graphs. This is joint work with Matthew DeVos and Danielle Rogers.

Vendredi 24 janvier 2020 - Induced odd cycle packing number, independent sets, and chromatic number - Jakub Pekárek (Charles University, République tchèque).

The induced odd cycle packing number iocp(G) of a graph G is the maximum integer k such that G contains an induced subgraph consisting of k pairwise vertex-disjoint odd cycles. Motivated by applications to geometric graphs, Bonamy et al. proved that graphs of bounded induced odd cycle packing number, bounded VC dimension, and linear independence number admit a randomized EPTAS for the independence number. We show that the assumption of bounded VC dimension is not necessary. We also present χ-boundedness results for graphs with bounded odd cycle packing number, and use them to design a QPTAS for the independence number only assuming bounded induced odd cycle packing number.

Vendredi 31 janvier 2020 - Packing and covering balls in graphs excluding a minor - Carole Muller (Université Libre de Bruxelles, Belgique).

Given a graph G, the ball centered at vertex v of radius r is the set containing all vertices at distance at most r from v. We prove that for every integer t > 0 there exists a constant c_t such that for every K_t-minor-free graph G, and every set S of balls in G, the minimum size of a set of vertices of G intersecting all the balls of S is at most c_t times the maximum number of vertex-disjoint balls in S. This was conjectured by Chepoi in 2007 in the special case of planar graphs and of balls having the same radius. This is joint work with Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet, and François Pirot.

Vendredi 31 janvier 2020 à 15h - Approximation algorithms for the p-hub center routing problem in parameterized metric graphs - Ling-Ju Hung (National Taipei University of Business, Taiwan).

Let G = (V, E, w) be a ∆β-metric graph with a distance function w(·, ·) on V such that w(v, v) = 0, w(u, v) = w(v, u), and w(u, v) ≤ β · (w(u, x) + w(x, v)) for all u, v, x ∈ V . Given a positive integer p, let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C ⊂ V form a clique of size at most p in H, vertices (non-hubs) in V \C form an independent set in H, and each non-hub v ∈ V \ C is adjacent to exactly one hub in C. Define dH(u, v) = w(u, f(u)) + w(f(u), f(v)) + w(v, f(v)) where f(u) and f(v) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w(u, f(u)) = 0. Let r(H) = P u,v∈V dH(u, v) be the routing cost of H. The Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H of G such that r(H) is minimized. In this talk, we will show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in ∆β-metric graphs for any β > 1/2. We give 2β-approximation algorithms running in time O(n 2 ) for any β > 1/2 where n is the number of vertices in the input graph. Finally, we show that the approximation ratio of our algorithms is at least Ω(β), and we examine the structure of any potential o(β)-approximation algorithm.

Vendredi 7 février 2020 - New optimization variant of combinatorial reconfiguration - Haruka Mizuta (Graduate School of Information Sciences, Tohoku University, Sendai, Japan).

Combinatorial reconfiguration asks for a step-by-step transformation on the solution space formed by feasible solutions of a combinatorial problem. This framework has been applied to many central combinatorial problems, such as Satisfiability, Independent Set, Coloring, and Matching. In most of the known work, we are given two feasible solutions as an input, and wish to determine whether they are reachable on the solution space. Recently, we proposed a new variant of combinatorial reconfiguration. In this variant, we are given only one feasible solution as an input, and wish to find a most desirable solution which is reachable from the given one. In this talk, we start with a brief introduction of combinatorial reconfiguration, and then explain our new variant by applying it to Independent Set and Dominating Set.

Vendredi 14 février 2020 - Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles - Yusuke Kobayashi (Kyoto University, Japan).

The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give a first polynomial-time algorithm for the weighted T-free 2-matching problem under the assumption that T is a set of edge-disjoint triangles. In our algorithm, a key ingredient is to give an extended formulation representing the solution set, that is, we introduce new variables and represent the convex hull of the feasible solutions as a projection of another polytope in a higher dimensional space. Although our extended formulation has exponentially many inequalities, we show that the separation problem can be solved in polynomial time, which leads to a polynomial-time algorithm for the weighted T-free 2-matching problem.

Vendredi 21 février 2020 - Représentation des codes circulaires par des graphes orientés - François Pirot (G-SCOP).
En biologie, les mécanismes de transcription et de traduction permettent la synthèse des protéines via la lecture d’une molécule d’ADN. Ce processus repose sur un code génétique, qui associe à certaines sous-séquences de l’ADN des acides aminés correspondants, lesquels forment la protéine synthétisée. Le code génétique peut avoir plusieurs propriétés combinatoires garantissant le bon déroulement de ce processus ; en particulier un code génétique est circulaire si la traduction est toujours non ambiguë.

Le but de cet exposé sera d’introduire une représentation des codes génétiques à l’aide de digraphes, et de donner le lien entre les propriétés d’un code génétique et certaines propriétés élémentaires du digraphe le représentant, en rapport avec les chemins et cycles orientés qu’il contient.

Vendredi 28 février 2020 - On the "quest" towards a directed variant of the 1-2-3 Conjecture. - Julien Bensmail (Université Côte d'Azur)

The 1-2-3 Conjecture, posed in 2004 by Karoński, Łuczak and Thomason, asks whether the edges of every connected graph different from K2 can be weighted with weights 1,2,3 so that no two adjacent vertices are incident to the same sum of incident weights. Since its introduction, this conjecture has been attracting more and more attention. In particular, several works have been dedicated to verifying the 1-2-3 Conjecture for various classes of graphs, proving modified forms of the conjecture, and investigating some interesting aspects such as algorithmic ones.

In graph theory, one legitimate direction for research regarding an undirected graph problem is to wonder about possible generalisations to digraphs. In the recent years, several attempts have hence been made for bringing the 1-2-3 Conjecture to digraphs. The goal of this talk will be to survey most of these attempts. In particular, we will stress out why things have been rather disappointing so far, and why the "quest" towards a directed 1-2-3 Conjecture might be not over yet.