Résumés des exposés

Yandong Bai: Cycles in directed graphs and properly-colored cycles in edge-colored complete graphs

Abstract: The existence of cycles with different constraints in directed graphs and edge-colored graphs have been extensively studied. In particular, Bermond and Thomassen conjectured in 1981 that every directed graph with minimum outdegree at least 2k-1 contains k vertex-disjoint cycles. I will report some progress on the above conjecture and on properly-colored cycles in edge-colored complete graphs. 

Jørgen Bang-Jensen: [slides]

Abstract: A path, cycle or closed trail in a 2-edge-coloured graph is alternating if it contains no pair of consecutive edges of the same colour.

A 2-edge-coloured graph is supereulerian if it contains a spanning alternating closed trail.

A 2-edge-coloured graph G is M-closed if the presence of two edges uv and uw of the same colour implies that there is an edge in G between v and w.

It is a well-known fact, used already in 1989 by Häggkvist and Manoussakis, that there is a very close correspondence between alternating cycles and trails in 2-edge-coloured bipartite graphs and cycles and trails in directed bipartite graphs. In this talk I will recall this connection and show how to use this together with new ideas to characterize M-closed 2-edge-coloured graphs which have a spanning alternating closed trail.

François Pirot: A colouring problem in optical fiber networks

Abstract: 

Many combinatorial optimisation problems arise from the use of fiber networks.
During this talk, we will focus on a colouring problem whose motivation comes
from the wavelength assignment in filterless optical networks.

Such a network can be modeled with a directed graph D, and is first decomposed into
subnetworks modeled as arc-disjoint directed subgraphs of D whose support are undirected trees.
The network is given with a set of requests, each of which consists in a source node
that needs to send information to a target node in the network. This information
is broadcasted in the whole arborscence rooted in the arc on which the source node
emits, using a specific wavelength. The wavelength assignment problem consists in
using as few different wavelengths as possible in order for all the requests to be
fulfilled simultaneously, with no interference (if the arborescence of a request R1
intersects the directed path from the source node to the target node of a request R2,
then R1 should use a difference wavelength from that of R2 in order to avoid interference).

The wavelength assignment problem is equivalent to the colouring problem on an interference graph.
We will study the structure of interference graphs, and infer approximation schemes for the problem.

Joint work with Hugo Boulier, David Coudert, and Frédéric Havet.

Zsolt Tuza: Hypercycle systems

Abstract: