Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint
Data sources: ZENODO
addClaim

A 15/31 Counterexample Family to the Albertson–Berman Conjecture

Authors: Jung, Heejae;

A 15/31 Counterexample Family to the Albertson–Berman Conjecture

Abstract

We disprove the Albertson–Berman conjecture (1979), which asserts that every n-vertex planar graph has an induced forest on at least n/2 vertices. We exhibit an explicit 31-vertex plane triangulation T whose maximum induced forest has 15 vertices. Moreover, for every k >= 2, we construct a simple planar graph M_k on 31k vertices with minimum degree 5 and maximum induced forest of exactly 15k vertices, giving the ratio 15/31 < 1/2. A self-contained Python verifier is included. Correspondence: hdhehia@knou.ac.kr

Powered by OpenAIRE graph
Found an issue? Give us feedback