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" [...]


  Payday Loans In North Carolina. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.