Graph Theory

The main focus is on structural and algorithmic point of views. The team established expertise includes problems such as finding large cycles in a given graph, graph colorings, covering problems, and extremal graph theory. For example, some team members are particularly interested in Thomassen’s conjecture: Every 4-connected line graph is Hamiltonian. Finding sufficient and computationally tractable conditions for a graph to be Hamiltonian is of significant importance from both theoretical and algorithmic viewpoints as Hamiltonicity is an NP-hard problem.

Generalization of such problems has also been recently considered for edge- or vertex-colored graphs. For example, one may look for properly colored spanning trees in an edge- or a vertex-colored graph. Alternatively, one may look for a dominating set in a vertex colored graph having at least one vertex from each color. Beside their theoretical interest, these extensions have applications in areas including biocomputing and web problems.

Many of the questions we consider can be stated in terms of (integer) linear optimization that is an expertise of new members of the team with research interests focusing on the combinatorial, computational, and geometric aspects of linear optimization. In this regard the aim would be to investigate recent results illustrating the significant interconnection between the most computationally successful algorithms for linear optimization and its generalizations, and the geometric and combinatorial structure of the input. Ideally, the deeper theoretical understanding will ultimately lead to increasingly efficient algorithms. Most of our research collaborations involve French research groups including LaBRI, LIRMM, LIAFA, and LIMOS as well as research groups in Europe, North America, China, Japan, India and South America.

Compact local certification of MSO properties for several tree-like parameters

-- Hugo Demaret (LISN, Galac)

summary: Local certification is interested in assigning labels (called certificates) to the vertices of a graph, in order to certify a certain property about said graph, or the correctness of a data-structure distributed on the graph. For the verification to be local, a vertex may only "see" its neighbourhood. A ...


Complexité du problème de distance d’édition minimum à un line-digraphe

-- Quentin Japhet (LISN, Galac)

summary: La distance d'édition est une mesure classique utilisée pour évaluer la proximité entre un graphe donné et un autre graphe ou une classe de graphes. Cette distance représente le nombre minimum de modifications requises pour transformer le graphe initial en un graphe appartenant à la classe voulue. Une ...

Edge k-q-colorability of graphs

-- Selma Djelloul (LISN, Galac)

summary: Given positive integers k, q, we say that a graph is edge k-q-colorable if its edges can be colored in such a way that the number of colors incident to each vertex is at most q and that the size of a largest color class is at most k ...

The freezing threshold for uniformly random colourings of sparse graphs

-- François Pirot (LISN, Galac)

summary: Given a random Δ-regular graph G, it holds that χ(G) ~ Δ / (2 ln Δ) with high probability. However, for any ε > 0 and k large enough, no (randomised) polynomial-time algorithm returning a proper k-colouring of such a random graph G is known to exist when k < (1−ε ...

See all

Translations: fr