Maximum bipartite subgraphs of cubic triangle-free planar graphs (Q1011782)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Maximum bipartite subgraphs of cubic triangle-free planar graphs |
scientific article; zbMATH DE number 5542429
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Maximum bipartite subgraphs of cubic triangle-free planar graphs |
scientific article; zbMATH DE number 5542429 |
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
0.9264702
0 references
0.9264702
0 references
0.9253993
0 references
0.9169204
0 references
0.9159397
0 references
0.9143137
0 references
0 references
0.90329075
0 references