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, to prove lower bounds on f(G). We use this approach to find large cuts in graphs with few triangles and in Kr-free graphs.
Lower bounds for max-cut in h-free graphs via semidefinite programming
Luca Trevisan
2021
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, to prove lower bounds on f(G). We use this approach to find large cuts in graphs with few triangles and in Kr-free graphs.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
1810.10044.pdf
accesso aperto
Tipologia:
Documento in Pre-print (Pre-print document)
Licenza:
PUBBLICO DOMINIO
Dimensione
445.76 kB
Formato
Adobe PDF
|
445.76 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.