Maximum bipartite subgraphs of cubic triangle-free planar graphs (Q1011782): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2007.12.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1972250365 / rank | |||
Normal rank |
Revision as of 22:52, 19 March 2024
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