Maximum bipartite subgraphs of cubic triangle-free planar graphs (Q1011782)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum bipartite subgraphs of cubic triangle-free planar graphs |
scientific article |
Statements
Maximum bipartite subgraphs of cubic triangle-free planar graphs (English)
0 references
9 April 2009
0 references
\textit{C. Thomassen} [J. Graph Theory 53, No.\, 4, 261--269 (2006; Zbl 1109.05039)] used a \textit{W. T. Tutte} cycle technique [Trans. Am. Math. Soc. 82, 99--116 (1956; Zbl 0070.18403)] to show that a 3-connected cubic triangle-free planar graph of order \(p\) contains a bipartite graph with at least \((29p-28)/24\) edges. The present authors extend Thomassen's approach, to improve the lower bound to \((39p-18)/32\). The ratio of the improved bound to the former bound, as \(p\) gets large, is \(117/116\).
0 references
bipartite subgraph
0 references
Tutte subgraph
0 references
cubic planar graph
0 references
triangle-free
0 references