Groupe

2022-2023

Vendredi 20 janvier à 14h - František Kardoš
Subcubic planar graphs of girth 7 are class I
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that planar graphs of maximum degree 3 and of girth at least 7 are 3-edge-colorable, extending the previous result for girth at least 8 by Kronk, Radlowski, and Franen from 1974.
This is a joint work with Sebastien Bonduelle.
https://doi.org/10.1016/j.disc.2022.113002

Vendredi 13 janvier à 14h - Paul Bastide
Graph reconstruciton with distance oracles
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in English)
How fast can you reconstruct a network using a ping-pong protocol. Distance query reconstruction is a setting where we assume an unknown simple and connected graph, and we try to recover the graph only using queries of distance between pairs of vertices. In this talk we extend a result by Kannan, Mathieu, and Zhou in the probabilistic settings, creating a randomized algorithm able to reconstruct graphs of bounded treelength with a quasi-linear number of queries in expectation. In particular, graphs of bounded treewidth contain various graph classes of interest such as k-chordal graphs, permutation graphs and AT-free graphs. This talk is based on a joint work with Carla Groenland.

Vendredi 9 décembre à 14h - Fábio Botler
Mod k colorings of graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in English)
Given a positive integer k, a mod k coloring of a graph G is a coloring of the edges of G in which each color induces a graph whose non-isolated vertices have degree congruent to 1 (mod k). The mod k coloring problem is to minimize the number of colors used in a mod k coloring of G. In 1997, Scott proved that every graph G admits a mod k coloring with at most 5k^2 log k colors. In this talk we will show that this bound can be reduced to 198k-101.

Vendredi 2 décembre à 14h - Cyril Gavoille
Smaller Universal Graphs for Caterpillars and Graphs of Bounded Path-Width, Part 2
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in French, English slides)
In this talk, I will given a rather simple construction of a graph Un with at most 8n vertices with the property that every n-vertex caterpillar is isomorphic to some induced-subgraph of Un. Previous constructions of so-called induced-universal graph for caterpillars used 256n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. FOCS'15).

Then, I will also present an extension to path-width-p graphs with an induced-universal graph of n.2O(p) vertices. This is complemented with a n.2Ω(p) lower bound. With bounded path-width graphs, our construction considerably enlarge the family of n-vertex graphs having an induced-universal graph of O(n) vertices, which is optimal. Such unexpected property was known only for trees, bounded maximum degree outerplanar graphs and maximum degree-2 graphs.

The extended result is obtained from an algorithmic approach by designing an adjacency labeling scheme for these graphs using log(n) + O(p) bit vertex labels and with a constant time adjacency test.

This is a joint work with Arnaud Labourel.

Vendredi 25 novembre à 14h - Clément Legrand-Duchesne
Recoloring planar graphs with Kempe changes
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Given a coloring of a fixed graph G, a Kempe chain is a maximal bichromatic connected component. A Kempe change is a recoloring operation consisting in swapping the two colors inside a Kempe chain. Meyniel proved in 1978 that any two 5-colorings of a planar graph are equivalent up to a series of O(5^|V(G)|) Kempe changes. We strengthen this result, by proving that any two 5-colorings of a planar graph are equivalent up to a polynomial number of Kempe changes. This is a first step towards bounding polynomially the diameter of the reconfiguration graph of d-degenerate graphs.

Vendredi 28 octobre à 14h - James Davies
Odd distances in colourings of the plane
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd distance from each other. This resolves Rosenfeld's odd distance problem.

Vendredi 21 octobre à 14h - Paul Bastide
Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
Only offline, no online version
in French, English slides

For given positive integers k and n, a family F of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k, but adding any set to F creates an antichain of size k. We use sat*(n, k) to denote the smallest size of such a family. For all k and sufficiently large n, we determine the exact value of sat*(n, k), which confirms several conjectures on antichain saturation. Previously, exact values for sat*(n,k) were only known for k up to 6. We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given m disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one).

Vendredi 14 octobre à 14h - Claire Hilaire
Structure of graphs with bounded induced cycle packing number
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in French, English slides)
A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that sparse (here, not containing large complete bipartite graphs as sub-graphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. This result implies that most of the central NP-complete problems (such as Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Minimum Coloring) can be solved in polynomial time in sparse Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable.

This is a joint work with Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek.

Vendredi 7 octobre à 14h - Cyril Gavoille
Smaller Universal Graphs for Caterpillars and Graphs of Bounded Path-Width
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in French, English slides)
In this talk, I will given a rather simple construction of a graph Un with at most 8n vertices with the property that every n-vertex caterpillar is isomorphic to some induced-subgraph of Un. Previous constructions of so-called induced-universal graph for caterpillars used 256n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. FOCS'15).

Then, I will also present an extension to path-width-p graphs with an induced-universal graph of n.2O(p) vertices. This is complemented with a n.2Ω(p) lower bound. With bounded path-width graphs, our construction considerably enlarge the family of n-vertex graphs having an induced-universal graph of O(n) vertices, which is optimal. Such unexpected property was known only for trees, bounded maximum degree outerplanar graphs and maximum degree-2 graphs.

The extended result is obtained from an algorithmic approach by designing an adjacency labeling scheme for these graphs using log(n) + O(p) bit vertex labels and with a constant time adjacency test.

This is a joint work with Arnaud Labourel.

Vendredi 30 septembre à 13h - Péter Pál Pach
The Alon-Jaeger-Tarsi conjecture via group ring identities
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

The Alon-Jaeger-Tarsi conjecture states that for any finite field F of size at least 4 and any nonsingular matrix A over F there exists a vector x such that neither x nor Ax has a 0 component. In this talk we discuss the proof of this result for primes larger than 61 and further applications of our method about coset covers and additive bases. Joint work with János Nagy and István Tomon.

Vendredi 23 septembre à 14h - Michael Savery
Induced subgraphs of induced subragphs of large chromatic number
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

What structure can be found in a graph G with large chromatic number? One possibility is that G contains a large clique, but if it does not, then can we find an induced subgraph of G which still has fairly large chromatic number but is simpler than G in some way? In this talk we will discuss some limitations of this approach. We will prove that for every graph F with at least one edge there are graphs G of arbitrarily large chromatic number and the same clique number as F such that every induced subgraph of G with chromatic number at least c = c(F) contains an induced copy of F. This generalises recent theorems of Briański, Davies, and Walczak, and of Carbonero, Hompe, Moore, and Spirkl. We will also outline how to show an analogous statement where clique number is replaced by odd girth. This is joint work with António Girão, Freddie Illingworth, Emil Powierski, Alex Scott, Youri Tamitegama, and Jane Tan.

Vendredi 9 septembre à 14h - Jane Tan
Exploring comparable box dimension
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Two boxes in R^d are comparable if one of them is a subset of a translation of the other. The comparable box dimension of a graph G is the minimum d such that G can be represented as a touching graph of comparable axis-aligned boxes in R^d. Having finite comparable box dimension implies a number of nice graph properties, which leads us to consider which graphs have such geometric representations. In this talk, we show that comparable box representations behave well under several common operations on graphs. This leads to a proof that every proper minor-closed class of graphs has finite comparable box dimension. Based on joint work with Zdeněk Dvořák, Daniel Goncalves, Abhiruk Lahiri and Torsten Ueckerdt.

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki