## Invited Session Mon.3.H 3005

#### Monday, 15:15 - 16:45 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Exact and approximation algorithms on graphs

**Chair: Frédéric Meunier**

**Monday, 15:15 - 15:40 h, Room: H 3005, Talk 1**

**Denis Cornaz**

Strengthening Lovász bound for coloring with a new graph transformation

**Coauthor: Meurdesoif Philippe**

**Abstract:**

Let *α(G)* and *χ(G)* denote the stability number and the clique-partition number of *G*, respectively. Using a new graph transformation, one constructs a new operator *Φ* which associates to any graph parameter *β* such that *α(G) ≤ β(G) ≤ χ(G)* for all graphs *G*, a graph parameter *Φ*_{β} such that *α(G) ≤ Φ*_{β}(G) ≤ χ(G) for all graphs *G*. We prove that *ϑ(G) ≤ Φ*_{ϑ}(G) and that *Φ*_{χf}(G) ≤ χ_{f}(G) for all graphs~*G*, where *ϑ* is Lovász theta function and *χ*_{f} is the fractional clique-partition number. *Φ*_{ϑ}-ϑ is unbounded and numerical experiments show that *Φ*_{ϑ} is a significant better lower bound for *χ* than *ϑ*.

**Monday, 15:45 - 16:10 h, Room: H 3005, Talk 2**

**Frédéric Meunier**

A routing problem raised by self-service bike hiring systems

**Coauthors: Daniel Chemla, Roberto Wolfler Calvo**

**Abstract:**

Operating bike-sharing systems raises many problems. One of the most natural is the repositioning of the bikes with the help of one or many trucks.

We focus in this talk on the case when there is only one truck. We are given a graph whose vertices model stations. The current repartition of the bikes is known. We wish to move these bikes with the truck in order to reach a target repartition, and we want to realize this task at a minimal cost. The concrete motivation corresponds to the situation encountered at the end of the night, when very few bikes are moving.

A part of the talk will be devoted to special polynomial cases and to approximation algorithms. An efficient method able to solve in practice instances of reasonable size will also be presented: this method combines the exact computation of a natural lower bound and a local search exploiting theoretical properties of the problem. Open questions will also be discussed.

**Monday, 16:15 - 16:40 h, Room: H 3005, Talk 3**

**Henning Bruhn**

Clique or hole in claw-free graphs

**Coauthor: Akira Saito**

**Abstract:**

Given a claw-free graph and two non-adjacent vertices *x* and *y* without common neighbours we prove that there exists a hole through *x* and *y* unless the graph contains the obvious obstruction, namely a clique separating *x* from *y*. As applications we derive an algorithm to verify whether there is a hole through two given vertices as well as an algorithm for the *3*-in-a-tree problem in claw-free graphs.