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
    0 references
    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
    0 references
    bipartite subgraph
    0 references
    Tutte subgraph
    0 references
    cubic planar graph
    0 references
    triangle-free
    0 references
    0 references