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.\\

Emplois - Stages


GT Graphes et Optimisation


edit SideBar