Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming
C. Carlson, A. Kolla, R. Li, N. Mani, B. Sudakov, and L. Trevisan. (2018)cite arxiv:1810.10044Comment: 21 pages, to be published in LATIN 2020 proceedings, Updated version is rewritten to include additional results along with corrections to original arguments.
Abstract
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.
Description
Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming
cite arxiv:1810.10044Comment: 21 pages, to be published in LATIN 2020 proceedings, Updated version is rewritten to include additional results along with corrections to original arguments
%0 Generic
%1 carlson2018lower
%A Carlson, Charles
%A Kolla, Alexandra
%A Li, Ray
%A Mani, Nitya
%A Sudakov, Benny
%A Trevisan, Luca
%D 2018
%K combinatorics maxcut
%T Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming
%U http://arxiv.org/abs/1810.10044
%X 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.
@misc{carlson2018lower,
abstract = {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.},
added-at = {2022-02-14T08:28:29.000+0100},
author = {Carlson, Charles and Kolla, Alexandra and Li, Ray and Mani, Nitya and Sudakov, Benny and Trevisan, Luca},
biburl = {https://www.bibsonomy.org/bibtex/239609029a4907955177da137f0e540b3/iliyasnoman},
description = {Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming},
interhash = {11672dedf8b7f301f5af65c07e9eff21},
intrahash = {39609029a4907955177da137f0e540b3},
keywords = {combinatorics maxcut},
note = {cite arxiv:1810.10044Comment: 21 pages, to be published in LATIN 2020 proceedings, Updated version is rewritten to include additional results along with corrections to original arguments},
timestamp = {2022-02-14T08:28:29.000+0100},
title = {Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming},
url = {http://arxiv.org/abs/1810.10044},
year = 2018
}