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.

[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 :

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.

Emplois - Stages


GT Graphes et Optimisation


edit SideBar