In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $|V(G)|/2$. This long-standing conjecture was recently disproved by several explicit counterexamples, which naturally led to several extremal and structural questions that we answer. We combine mathematical arguments and exhaustive computations to show that the minimum order of a counterexample is $29$. We also construct infinitely many $4$-connected $5$-edge-connected counterexamples (and show that the unique such counterexample of minimum order has order $41$), whereas previously all known counterexamples had vertex-connectivity at most $3$. Furthermore, we construct an infinite family of planar graphs on $n$ vertices whose maximum induced forests have order at most $\frac{25}{52}n$, thereby improving the previous best upper bound. This family also yields infinitely many counterexamples (for every integer $d \geq 7$) to a conjecture of Chappell and Pelsmajer concerning induced forests of maximum degree at most $d$.
For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which had been open since 1979, states that $a(G) \geq \frac{n}{2}$ for every simple planar graph $G$ on $n$ vertices. Although the Albertson-Berman conjecture was recently resolved in the neg...
In 1988, Jaeger conjectured that every bridgeless cubic graph $G$ admits a Petersen coloring; that is, a map $E(G) \to E(P)$ mapping any two adjacent edges of $G$ to two adjacent edges of the Petersen graph $P$. A positive resolution of Jaeger's conjecture would have immediately resolved several other famous and long-s...
J. Goedgebeur, Jorik Jooken, Edita Máčajová et al.· 0 citations
For a graph $G$, let $a(G)$ be the maximum number of vertices in an induced forest. The Albertson-Berman conjecture, posed in 1979, asserts that every $n$-vertex planar graph satisfies $a(G)\ge n/2$. Borodin's bound $a(G)\ge 2n/5$ remains the general lower bound toward this problem. We disprove the conjecture with an e...
Henning and Yeo conjectured an upper bound on the identifying vertex cover number of a graph in terms of its order, size, and maximum degree. A two-parameter family $H_{t,r}$ of connected diameter-two graphs disproves the bound for every maximum degree at least four; after denominators are cleared, its margin is exactl...
Aldous and Fill (2002) conjectured that the maximum relaxation time of a random walk on a connected regular graph with $n$ vertices is bounded above by $(1+o(1))\frac{3n^2}{2\pi^2}$, with asymptotic equality for even $n$. Since the relaxation time of a $d$-regular graph $G$ is $d/\mu(G)$, where $\mu(G)$ denotes its alg...
Albertson's conjecture asserts that every finite simple graph $G$ with $\chi(G) \ge r$ satisfies $\operatorname{cr}(G) \ge \operatorname{cr}(K_r)$. Building on Cranston's verification for $r \le 24$ and his reduction of $r \in \{25,26\}$ to three residual orders, we eliminate those residual cases and then prove the cas...
Sen Cao, San Mehat· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
