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


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 (Xs, Ys) with the
property that each dissimilar pair of nodes z, y in N(s) is adjacent
if and only if both belong to Xs or Ys. 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" [...]


  Illinois Loans Online should not be obtained by people who do not have the capacity to repay the lenders. Cialis Professional online is capableto release you reliably from the erection problems, its improved formula gives the new properties to the drug.