Lundi 27 août 2018 - Soutenance de thèse de Thomas Bellitto.

Amphithéâtre du LaBRI, à 10h. Titre de la thèse : Walks, Transitions and Geometric Distances in Graphs. Jury : Christine Bachoc (directeur de thèse) - Jørgen Bang-Jensen (rapporteur) - Sylvain Gravier (rapporteur) - Mickael Montassier (examinateur) - Arnaud Pêcher (directeur de thèse) - Éric Sopena (examinateur).

Vendredi 7 septembre 2018 - Proportionally dense subgraph of maximum size: complexity and approximation - Clément Dallard (University of Portsmouth, Royaume-Uni).

We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is NP-hard, more precisely APX-hard, even on split graphs. On the other hand, we present a simple polynomial-time (2 - (2/(Δ+1)))-approximation algorithm for the problem, where Δ is the maximum degree in the graph. We also prove that all Hamiltonian cubic graphs (except two) have a PDS of the maximum possible size which can be found in linear time (if a Hamiltonian cycle is given) and sketch the proof. Finally, we show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs.

Vendredi 14 septembre 2018 - Soutenance de thèse de Mohammed Senhaji.

Amphithéâtre du LaBRI, à 14h. Titre de la thèse : Neighbour-distinguishing decompositions of graphs. Jury : Maria Axenovich et Alexandre Pinlou (rapporteurs) - Aline Parreau, Arnaud Pêcher, Olivier Baudon et Eric Sopena (examinateurs).

Vendredi 21 septembre 2018 - Maximum Independent Set in H-free graphs - Édouard Bonnet (LIP, Lyon).

Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1,3), the computational complexity of MIS is generally open except for a small number of cases. We will explore the parameterized complexity of MIS in H-free graphs. Our distant goal is to establish a dichotomy of the H for which the problem can be solved in time f(k)n^{O(1)} and the ones for which such an algorithm is unlikely to exist (where n is the total number of vertices, k is the size of the solution, and f is any computable function). Recast in the parameterized complexity language, we want to know when the problem is FPT and when it is W[1]-complete. We will present a selection of results and draw a parallel with the situation for the 'classical dichotomy' (P/NP-complete). This is joint work with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant.

Vendredi 28 septembre 2018 - Coloring the squares of planar graphs with no 4-cycle - Théo Pierron (LaBRI).

Coloring the square of a graph consists in assigning colors to its vertices in such a way that any two vertices at distance at most 2 receive different colors. While D+1 colors are needed to properly color the square of any graph of maximum degree D, Wegner proved that there is no hope for a matching upper bound of D+O(1) in general, even for planar graphs. We study the cycle obstructions needed to obtain such a bound for planar graphs. We present here the case where only finitely many cycles lengths are forbidden. In this setting, we prove that removing only cycles of length 4 is necessary and sufficient to obtain the desired bound. For very large D, we also improve a result of Bonamy, Cranston and Postle by showing that D+2 colors are always sufficient for coloring the square of C_4-free planar graphs, which is tight. This is joint work with Ilkyoo Choi and Daniel W. Cranston.

Mercredi 10 octobre 2018 15h - salle 76 - Rapid mixing of Glauber dynamics for colorings below Vigoda’s 11/6 threshold - Michelle Delcourt (University of Waterloo, Canada).

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of $k$-colorings of a graph $G$ on $n$ vertices with maximum degree $\Delta$ is rapidly mixing for $k \geq \Delta+2$. In 1999 Vigoda showed rapid mixing time of a modified version of flip dynamics for $k >11/6 \Delta$, implying polynomial time mixing for Glauber dynamics under the same constraints. This conjecture has attracted a lot of attention in the literature and better results are known for certain classes of graphs. In this talk, we improve Vigoda's bound for general graphs by showing that there exists a constant $\eta>0$ such that the Glauber dynamics mixes in polynomial time for $k \geq (11/6- \eta)\Delta$. Our proof combines path coupling with a new kind of metric we introduce to incorporate a count of the extremal configurations of the chain. This "extremal" metric proves to be much easier to analyze than stopping-time-based metrics, and hence we believe will have fruitful applications for bounding the mixing times of other Markov chains. This is joint work with Guillem Perarnau and Luke Postle.

Vendredi 19 octobre 2018 - On the density of critical graphs without large cliques - Tom Kelly (University of Waterloo, Canada).
A graph is k-critical if it has chromatic number k and every proper subgraph is (k - 1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to list-coloring and generalizations of Reed's Conjecture.

Joint work with Luke Postle.

Vendredi 26 octobre 2018 - Claw-free matroids - Peter Nelson (University of Waterloo, Canada).
Let M be a set of nonzero vectors in a vector space over the two-element field. We say that M is claw-free if there are no vectors x, y, z in M for which x+y, y+z, x+y, x+y+z are not in M. These objects are a matroidal/geometric analogue of claw-free graphs. I will discuss a theorem, obtained recently with Kazuhiro Nomoto, that exactly classifies all claw-free M.

Lundi 5 novembre 2018 à 15h30 - Acyclic Colouring of Graphs on Surfaces - Shayla Redlin (University of Waterloo, Canada).

An acyclic k-colouring of a graph G is a proper k-colouring of G with no bichromatic cycles. In 1979, Borodin proved that planar graphs are acyclically 5-colourable, an analog of the Four Colour Theorem. Kawarabayashi and Mohar proved in 2010 that "locally" planar graphs are acyclically 7-colourable, an analog of Thomassen's result that "locally" planar graphs are 5-colourable. We say that a graph G is critical for (acyclic) k-colouring if G is not (acyclically) k-colourable, but all proper subgraphs of G are. In 1997, Thomassen proved that for every k >= 5 and every surface S, there are only finitely many graphs that embed in S that are critical for k-colouring. Here we prove the analogous result that for all k >= 12 and each surface S, there are finitely many graphs embeddable on S that are critical for acyclic k-colouring. This result implies that there exists a linear time algorithm that, given a surface S and large enough k, decides whether a graph embedded in S is acyclically k-colourable.

Mardi 6 novembre 2018 à 15h - Density and Structure of Homomorphism-Critical Graphs - Evelyne Smith-Roberge (University of Waterloo, Canada).

Let $H$ be a graph. A graph $G$ is $H$-critical if every proper subgraph of $G$ admits a homomorphism to $H$, but $G$ itself does not. In 1981, Jaeger made the following conjecture concerning odd-cycle critical graphs: every planar graph of girth at least $4t$ admits a homomorphism to $C_{2t+1}$ (or equivalently, has a $\tfrac{2t+1}{t}$-circular colouring). The best known result for the $t=3$ case states that every planar graph of girth at least 18 has a homomorphism to $C_7$. We improve upon this result, showing that every planar graph of girth at least 16 admits a homomorphism to $C_7$. This is obtained from a more general result regarding the density of $C_7$-critical graphs. Our main theorem is that if $G$ is a $C_7$-critical graph with $G \not \in \{C_3, C_5\}$, then $e(G) \geq \tfrac{17v(G)-2}{15}$. In this talk, I will go over the history of the progress towards Jaeger's conjecture, and give a general overview of the proof structure of our main theorem. Along the way, I will prove several structural lemmas concerning graphs that are $H$-critical, when $H$ is a vertex-transitive non-bipartite graph.

Vendredi 9 novembre 2018 - Labeling schemes for trees and planar graphs - Paweł Gawrychowski (University of Wrocław, Poland).

Labeling schemes seek to assign a label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. The goal is to minimize the maximum length of a label and (as a secondary goal) the time to evaluate the function. As a prime example, we might want to compute the distance between two nodes of a network using only their labels. We consider this question for two natural classes of networks: trees and planar graphs. For trees on n nodes, we design labels consisting of 1/4log^2(n) bits (up to lower order terms). Interestingly, our solution circumvents a lower bound of 1/2log^2(n) obtained for a natural class of schemes based on the so-called universal graphs. I will discuss how a related notion of minor-universal graphs allows us to significantly improve on the best known bounds for NCA labeling.

For planar graphs, the situation is much more complex. A major open problem is to close the gap between an upper bound of O(n^{1/2}log(n))-bits and a lower bound of O(n^{1/3})-bits for unweighted planar graphs. We show that, for undirected unweighted planar graphs, there is no hope to achieve a higher lower bound using the known techniques. This is done by designing a centralized structure of size ~O(min(k^2,(kn)^{1/2})) that can calculate the distance between any pair of designated k terminal nodes. We show that this size it tight, up to polylogarithmic terms, for such centralized structures. This is complemented by an improved upper bound of O(n^{1/2}) for labeling nodes of an undirected unweighted planar graph for calculating the distances.

Vendredi 7 décembre 2018 - à partir de 11h30 - Pique-nique et exposé de Michał Pilipczuk.

Vendredi 7 décembre à 14h - Progressive algorithms for distance domination in sparse graphs. - Michał Pilipczuk (University of Warsaw, Poland).

In the distance-r dominating set problem we are given a graph G and integers r and k, and the question is whether G can be covered with k balls of radius r. We present a new, generic approach to the problems that gives a simple, linear-time fixed-parameter tractable algorithm (i.e. with running time f(r,k) * n) on a whole spectrum of sparse graph classes; more precisely, on any graph class that is nowhere dense. This topic will serve as an excuse to give an introduction to the theory of structural sparsity, an active research area originating in the work of Nesetril and Ossona de Mendez which provides a variety of combinatorial and algorithmic tools for working with sparse graphs.

Vendredi 21 décembre 2018 - Sequential Metric Dimension (in trees) - Julien Bensmail (Université de Nice).

In the Localization Game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph G. At every step, one vertex v of G can be probed which results in the knowledge of the distance between v and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location. In a joint work with D. Mazauric, F. Mc Inerney, N. Nisse and S. P ́erennes, we addressed the generalization of the Localization Game where k ≥ 1 vertices can be probed at every step, which also stands as a generalization of the notion of metric dimension of graphs. Precisely, given a graph G and two integers k, l ≥ 1, the Localization problem asks whether there exists a strategy to locate a target hidden in a given graph G in at most l steps and probing at most k vertices per step. The Localization problem is, in general, hard to comprehend. However, we settled it in the context of trees; namely:

• On the negative side, the Localization problem is, in general, NP-complete when restricted to trees.

• On the positive side, there is a (+1)-approximation for the problem in trees, i.e., a polynomial strategy to locate the target in at most one more step than the optimal number of steps.

In other words, in trees, the hardness of the Localization problem only arises from the first probing step, which is NP-hard to decide. A consequence is that we can optimally determine the location of the target, assuming the first probing step is provided e.g. by an oracle. The talk will be dedicated to discussing these aspects.

Vendredi 11 janvier 2019 - Hitting minors on bounded treewidth graphs - Julien Baste (Universität Ulm, Allemagne).

For a fixed collection of graphs F, the F-DELETION problem consists in, given a graph G and an integer k, decide whether there exists S, subset of V(G), with |S| <= k such that G-S does not contain any of the graphs in F as a minor. This NP-hard problem is a generalization of some well-known graph problems as VERTEX COVER (F={K_2}), FEEDBACK VERTEX SET (F={K_3}), or VERTEX PLANARIZATION (F={K_5,K_{3,3}}). We are interested in its parameterized complexity when the parameter is the treewidth of G, denoted by tw. Namely, the objective is to determine, for a fixed F, the (asymptotically) smallest function f_F: N -> N such that F-DELETION can be solved in time f_F(tw)*n^{O(1)} on n-vertex graphs. In this talk we will provide the basic definitions of parameterized complexity, motivate the problem, and then, review some of the lower and upper bounds on the function f_F for several instantiations of F. The presented results are joint work with Ignasi Sau and Dimitrios Thilikos and can be found in https://arxiv.org/abs/1704.07284.

Vendredi 25 janvier 2019 - Eternal domination in graphs - Ben Seamone (Dawson College, Canada).

Given a graph, how can one distribute resources to the vertices (nodes) so that one can use these resources to respond to any infinite sequences of demands? This is the fundamental question which the study of eternal domination in graphs attempts to answer. I will give a brief survey of what is known about eternal domination, followed by recent progress on some eternal domination problems. Notably, we refute a conjecture of Klostermeyer and Mynhardt on eternal domination in prisms over graphs, and introduce a fractional version of eternal domination which to our knowledge has not yet been studied. These results were jointly obtained with D. Khatri, A. Krim-Yee, N. Kumar, G. MacGillivray, V. Virgile, and A. Xu.

Vendredi 1 février 2019 - Octal games on graphs - Antoine Dailly (G-SCOP, Grenoble).

Octal games are two-player take-away games played on heaps of counters: the players remove counters from a heap, and may split the heap in two nonempty heaps, under conditions that can be expressed as an octal code. The main question in the study of those games is whether the sequences of their Grundy values (equivalence classes for games, that fully express the winner of the game) on heaps of increasing size are regular. We propose a generalization of those games on graphs: players now remove connected components from a graph, and may disconnect the graph under conditions similar to those of octal games. This definition includes several vertex-deletion games on graphs, such as Arc-Kayles. We focus our study on subtraction games, a subclass of octal games where the players are not allowed to disconnect the graph.

In this talk, I will first give an introduction to the theory of take-away games, before showing how we generalized octal games to play them on graphs, and how we redefined the notion of regularity to study them. I will then give several regularity results for subtraction games on graphs, with a focus on the class of subdivided stars. In particular, we show that all subtraction games on graphs have ultimately periodic sequences of Grundy values. However, we notice that the study of specific families of subtraction games is difficult, even on subdivided stars. Finally, I will show how we used a pseudo-sum of games to study the case of subdivided bistars for the subtraction game CSG(1,2).

The results presented in this talk were jointly obtained with L. Beaudou, P. Coupechoux, S. Gravier, J. Moncel, A. Parreau and É. Sopena.

Vendredi 22 février 2019 - Trees in tournaments - François Dross (I3S, Inria Sophia Antipolis).

A tournament is an orientation of a complete graph. A digraph D is said to be k-unavoidable if it is contained in every tournament of order k. As the transitive tournament of order n is (2^(n-1))-unavoidable, every graph of order n is (2^(n-1))-unavoidable. However, for some particular digraphs one can obtain a better bound.

In this presentation we will focus on orientations of trees. Sumner conjectured that every tree of order n > 1 is (2n-2)-unavoidable, and Havet and Thomassé made the strengthened conjecture that every tree of order n > 1 with k leaves is (n+k-1)-unavoidable. We will see some techniques to approach these conjectures.

Vendredi 8 mars 2019 - Circle Graphs are Polynomially Chi-Bounded - Rose McCarty (University of Waterloo, Canada).

Circle graphs are the intersection graphs of chords on a circle; vertices correspond to chords, and two vertices are adjacent if their chords intersect. A class of graphs is chi-bounded if there is a function f so that every graph in the class with clique number w has chromatic number at most f(w). Gyárfás proved that circle graphs are chi-bounded in the 1980's, and Kostochka proved essentially the best previously known upper bound on f, of order 2^w. We prove a quadratic upper bound. Joint with James Davies.

Lundi 11 mars 2019 (salle 178) - Temporal Cliques Admit Sparse Spanners - Jason Schoeters (LaBRI).

Let G=(V,E) be an undirected graph on n vertices and λ:E →2^N a mapping that assigns to every edge a non-empty set of positive integer labels. These labels can be seen as discrete times when the edge is present. Such a labeled graph {\cal G}=(G,λ) is said to be temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar (STOC 2000) asked whether, given such a temporal graph, a sparse subset of edges can always be found whose labels suffice to preserve temporal connectivity---a temporal spanner. Axiotis and Fotakis (ICALP 2016) answered negatively by exhibiting a family of Θ(n^2)-dense temporal graphs which admit no temporal spanner of density o(n^2). The natural question is then whether sparse temporal spanners can always be found in some classes of dense graphs. In this paper, we answer this question affirmatively, by showing that if the underlying graph G is a complete graph, then one can always find temporal spanners of density O(n log n). The best known result for complete graphs so far was that spanners of density (n choose 2)−⌊n/4⌋=O(n^2) always exist. Our result is the first positive answer as to the existence of o(n^2) sparse spanners in adversarial instances of temporal graphs since the original question by Kempe et al., focusing here on complete graphs. The proofs are constructive and directly adaptable as an algorithm.

Vendredi 15 mars 2019 (Amphi LaBRI) - Soutenance d'HdR - Structural Information in Distributed Computing - David Ilcinkas.

The defense will survey some of my contributions to the field of distributed computing in networks, from the point of view of the information available to the computing entities. I will also discuss some confidence issues in this topic of research.

Vendredi 22 mars 2019 - Local analogues of classic results in Hamiltonian graph theory - Jonas Börje Granholm (Linköping University, Sweden).

Many classic criteria for the existence of Hamiltonian cycles in graphs relate vertex degrees to the number of vertices in the entire graph. Perhaps the most famous such result is the one by Dirac, which states that a graph G is Hamiltonian if every vertex of G is adjacent to at least half of all vertices of G. The classes of graphs covered by such theorems are necessarily limited to dense graphs of small diameter.

Beginning in the 1980’s, Asratian and Khachatryan pioneered a method to overcome this limitation, by instead considering local structures of graphs. They obtained several generalizations of well-known sufficient conditions for Hamiltonicity, for instance the following generalization of Dirac’s theorem: A graph G is Hamiltonian if every vertex u of G is adjacent to at least half of all vertices at distance at most 3 from u. In this talk we will discuss this localization method, and some recent results in the area.

Lundi 25 mars 2019 14h - Low-depth decompositions of sparse graphs - Michał Pilipczuk (University of Warsaw).

Decomposition techniques are widely used in designing algorithms on sparse inputs, like planar graphs or graphs of bounded maximum degree. The idea is to cover the input structure with a relatively small number of well-behaved "pieces", so that the search for a global solution can be reduced to searching for a solution in each of the pieces separately. A classic application of this principle is the Baker's layering technique: for every k, every planar graph can be partitioned into k+1 parts so that any k of them induce a graph of treewidth O(k). During the talk we will describe a stronger type of decompositions, called low-treedepth decompositions or p-centered colorings. Here, the idea is that the well-behaved pieces should have bounded depth rather than width. This kind of decompositions is particularly useful for designing parameterized algorithms on sparse graphs, especially in the regimes of low space complexity and of distributed computing. Finally, we will sketch a proof that planar graphs admit p-centered colorings with O(p^19) colors; this part of the talk will be based on a joint work with Sebastian Siebertz, presented at SODA 2019.

Vendredi 29 mars 2019 - Containment - a Variation of Cops & Robber - Natasha Komarov (St Lawrence University, NY, USA).

We consider "Containment"': a variation of the graph pursuit game of Cops and Robber in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop), and the cops win by "containing" the robber---that is, by occupying all of the edges incident with a vertex v while the robber is at v. We develop several bounds on the minimal number of cops required to contain a robber, in particular relating this number to the well-studied ``cop-number'' in the original Cops and Robber game. We discuss the containability and containment number of some specific families of graphs, including hypercubes and certain Cartesian products. Time permitting, we will conclude with some discussion of current conjectures and other directions for future work.

Vendredi 12 avril 2019 - Strict Containment Relation Based on Bend Number - Uma Kant Sahoo (ISI Kolkata, Inde).

A k-bend path is a simple rectilinear path with at most k 90 degree turns. A graph G has bend number k if k is the minimum number such that G can be represented as an intersection graph of k-bend paths. A graph G has proper bend number k if k is the minimum number such that G can be represented as an intersection graph of k-bend paths such that two k-bend paths intersect at a finite number of points and at each intersection point they cross each other.

Chaplick, Jelínek, Kratochvíl and Vyskocil proved a strict containment relation between class of graphs with bend number p and class of graphs with bend number q, for p < q. Since their separating examples are not chordal, they posed to study the containment of chordal graph classes w.r.t the bend number. In this talk we look into such containment relations.

This is a joint work with Dibyayan Chakraborty, Joydeep Mukherjee and Sandip Das.

Vendredi 19 avril 2019 - Distance Constrained Graph Labeling - Soumen Nandi (Institute of enginerring & Management, Kolkata, Inde,).

In a cellular network, the channel assignment problem (CAP) is the task of assigning channels (frequency, time, code etc.) to the cells (base stations) satisfying the constraints to avoid channel interference. The degree of interference between base stations is related to the distance between them; closer the base stations stronger the interference. So in order to avoid interference, closer base stations should have higher channel difference. The aim is to allocate channels such that span (bandwidth) is minimized. The span is the difference between the least and the highest channels used. A channel assignment problem can be modeled on a graph, whose vertices represent the cells and edges represent possible communications and hence, interferences. Usually, most of these graph theoretic models of a CAP assume communication in both directions (duplex) between two transmitters/receivers and hence the CAP is modeled on a simple undirected graph.

Here, we will discuss a general technique for computing the lower bound of the span for radio k-chromatic number of a general graph G and derive a formula for it. We will also discuss some results to find optimal bounds of the span of different channel assignment problems modeled on undirected graphs.

Vendredi 26 avril 2019 - Star Edge-Coloring - Borut Lužar (Faculty of Information Studies in Novo mesto, Slovénie).

(joint work with M. Mockovčiaková, R. Soták, L. Šebestová & R. Škrekovski)

A star edge-coloring of a graph is a proper edge-coloring with forbidden bichromatic paths and cycles of length 4. The least number of colors that suffice for an edge-coloring of a graph G is called the star chromatic index, denoted χ'st(G). Motivated by the vertex analogue, the notion has been introduced in 2008 by Liu and Deng, who proved the first upper bound on the star chromatic index of any graph with maximum degree at least 7. Currently the best upper bound for general graphs has been established by Dvořák, Mohar, and Šámal in 2013 using their upper bound on the star chromatic index of complete graphs. They showed that for every ε > 0 there exists a constant C such that χ'st(G)<= C.n^(1+ε) for every positive n. They asked if the star chromatic index of complete graphs Kn is linear in terms of n. The answer to this question is still not known. Apart from the above, the same authors also considered subcubic graphs, proved that for any subcubic graph 7 colors suffice for a star edge-coloring, conjectured that the bound can be decreased to 6, and asked about the bounds for the list version of star edge-coloring. All these questions initiated an intense (and still ongoing) research on the topic. In the talk, we will give a survey of known results, present the most interesting proofs and techniques, and propose additional possible directions of research on the topic.

Vendredi 3 mai 2019 - Hamiltonian Properties of Planar Graphs and their Vertex-deleted Subgraphs - Carol Zamfirescu (Ghent University, Belgique).

We discuss the interplay between the hamiltonicity of a graph and its vertex-deleted subgraphs, with a special focus on the planar case. In the first part of the talk we will present an overview of results on planar hypohamiltonian graphs -- a graph is hypohamiltonian if it is non-hamiltonian, yet all of its vertex-deleted subgraphs are hamiltonian. The second part of the presentation will deal with extensions of Tutte's famous theorem stating that every planar 4-connected graph is hamiltonian, and a related theorem of Thomassen. The talk will also explore possible directions for future research and include a series of open problems.

Vendredi 10 mai 2019 - On dominating set of string graphs and its subclasses - Dibyayan Chakraborty (Indian Statistical Institute, Kolkata).

String graphs are intersection graphs of simple curves on the plane. In general, finding a dominating set of string graphs is as difficult as solving a general set cover problem. However, we recently noticed that by introducing a parameter called " unit bend number " we could get constant factor approximation algorithms for the dominating set problem on string graphs with bounded unit bend number. In this seminar, we shall give a brief proof sketch of the above and talk about its uses for getting constant factor approximation algorithms for the dominating set problem on some interesting sub-classes of string graphs.

Joint works with Sandip Das and Joydeep Mukherjee.

Vendredi 17 mai 2019 -Parameterized complexity of modifications problems on edge-coloured and signed graph homomorphisms - Dimitri Lajou (LaBRI).
A t-edge-coloured graph is a multigraph where each edge has a colour in {1, . . . , t}. A homomor- phism of an edge-coloured graph G to another edge-coloured graph H is a mapping from the vertices of G to the vertices of H that preserves all edges and their colours. The H-Colouring problem consists in determining, given an input edge-coloured graph G, whether there exists a homomorphism from G to H. Continuing the existing studies of the complexity of H-Colouring, we address the vertex-deletion and edge-deletion variants of this problem (where one may delete a certain number k of vertices or edges of G before mapping to H). We completely classify the decision complexity of the vertex-deletion variant. We prove that both variants, when parameterized by k, are FPT for all H of order 2 (while for some H of order 3 the problem is not FPT unless P = N P ).

Additionnally, we consider another refinement of H-Colouring based on switching; a signed graph G is a 2-edge-coloured graph that comes with a switching operation. Switching at a vertex v consists in inverting the colours of the edges incident to v. A signed graph G has a signed homomor- phism to a signed graph H, if we can perform some set of switchings at the vertices of G before giving a homomorphism of the resulting signed graph to H. For a fixed signed graph H, the corresponding problem is called Signed H-Colouring. Refining both Signed H-Colouring and H-Colouring (for 2-edge-coloured H), we parameterize the problems by a number of allowed switches, and study the complexity for signed graphs of order 2.

Vendredi 24 mai 2019 - Around Brooks' theorem - Marthe Bonamy (LaBRI).
In this talk, we will discuss various results around Brooks' theorem: a graph has chromatic number at most its maximum degree, unless it is a clique or an odd cycle. We will consider stronger variants and local versions, as well as the structure of the solution space of all corresponding colorings.

Vendredi 7 juin 2019 - On the 4-color theorem for signed graphs - Jonathan Narboni (LaBRI).
There are several ways to generalize graph coloring to signed graphs. Macajova, Raspaud and Skoviera introduced one of them and conjec- tured that in this setting, for signed planar graphs four colours are always enough. We disprove the conjecture.

Vendredi 21 juin 2019 - 12h30 - Pique-nique de thème en 178

Lundi 8 juillet 2019 - 10h - Amphi - Soutenance de thèse de Théo Pierron: "Induction Schemes: From Language Separation to Graph Colorings".

Jury : Marthe Bonamy (Encadrante) - Mireille Bousquet-Mélou (Examinatrice) - Thomas Colcombet (Examinateur) - Zdeněk Dvořák (Rapporteur) - Michał Pilipczuk (Rapporteur) - Jean-Sébastien Sereni (Rapporteur) - Éric Sopena (Directeur) - Marc Zeitoun (Directeur).

Mardi 9 juillet 2019 - 10h - salle 76 - Degrees and numbers of paths and cycles - Zdeněk Dvořák (Charles University, Prague).
We give an upper bound on the number of cycles in a simple graph in terms of its degree sequence, and apply this bound to answer several open questions. This is joint work with J. Noel, S. Norin, and L. Postle.

Mercredi 10 juillet 2019 - 14h - Around the Petersen Colouring Conjecture - Jean-Sébastien Sereni (CNRS, ICube).
A number of old conjectures related to edge-colourings of 3-regular graphs remain vastly open. Among them, the Petersen colouring conjecture is a very strong statement, which implies most of these, such as the Berge-Fulkerson conjecture, and the cycle double cover conjecture. It states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge e, the set of colours assigned to the edges adjacent to e has cardinality 2 or4 but not 3.

I will also discuss a variation of this conjecture using only 4 colours instead of 5, and show that all but at most 4/5|V(G)| edges can be made to satisfy the above condition. Further, the bound is tight, and attained only by the Petersen graph. Various open questions on related topics will be presented too.

The talk is based on a joint work with François Pirot et Riste Škrekovski.

Vendredi 12 juillet 2019 - On (Feynman) graphs, ribbon graphs and tensor graphs - Adrian Tanasa (LaBRI).
In this talk I will define the so-called Feynman graphs, which are a particular class of graphs appearing in quantum field theory. Ribbon graphs (or fat-graphs or graphs on surfaces), which appear as Feynman graphs of the so-called matrix models, will then be defined. I will then introduce tensor graphs, which are a natural generalization of ribbon graphs. These tensor graphs are Feynman graphs of the so-called tensor models. In the last part of the talk I will present several results on tensor graphs, such as the identification of the class of dominant graphs in a particular expansion of these tensor models.