**Friday, 11:30 - 11:55 h, Room: H 3008**

**Paolo Nobili**

A decomposition algorithm for the weighted stable-set problem in claw-free graphs

**Coauthor: Antonio Sassano**

**Abstract:**

In this paper we describe a new characterization of a *line-graph*

*G(V, E)* in terms of forbidden substructures. Unlike the classical

characterization due to Bermond and Meyer based on forbidden induced

subgraphs, we rely upon the properties of a suitable maximal stable set

*S* of *G*. Following Lozin, we say that two nodes *u* and *v* in *V*

\ S are *similar* if *N(u) ∩ S = N(v) ∩ S*.

Moreover, extending a definition due to Schrijver, we say that a node *s*

∈ S is *clique-splittable* in *G* with respect to *S* if the

nodes in *N(s)* can be partitioned in two cliques *(X*_{s}, Y_{s}) with the

property that each dissimilar pair of nodes *z, y* in *N(s)* is adjacent

if and only if both belong to *X*_{s} or *Y*_{s}. Our main result is that a

claw-free graph *G* is a line graph if and only if each node *s ∈ S*

is clique-splittable and *S* does not define two special structures in

*G*, namely a pair of *cross-linked* nodes or a *free-strip*.

Talk 3 of the invited session Fri.1.H 3008

**"Algorithms in claw-free graphs"** [...]

Cluster 2

**"Combinatorial optimization"** [...]