Skip to main content
MathOverflow

Return to Question

added 54 characters in body
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

The well-known max cut problemmax cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the maximum-cut problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.

The well-known max cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the maximum-cut problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.

The well-known max cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the maximum-cut problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.

removed capitals, added tag
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 285

Known bounds of the Maximum Cutmaximum cut of Planar Graphsplanar graphs

The well-known Max Cutmax cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the Maximummaximum-Cut Problemcut problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.

Known bounds of the Maximum Cut of Planar Graphs

The well-known Max Cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the Maximum-Cut Problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.

Known bounds of the maximum cut of planar graphs

The well-known max cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the maximum-cut problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.

Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

Known bounds of the Maximum Cut of Planar Graphs

The well-known Max Cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the Maximum-Cut Problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.