Аннотация
For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The
problem of estimating $f(G)$ as a function of the number of vertices and edges
of $G$ has a long history and was extensively studied in the last fifty years.
In this paper we propose an approach, based on semidefinite programming (SDP),
to prove lower bounds on $f(G)$. We use this approach to find large cuts in
graphs with few triangles and in $K_r$-free graphs.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)