A Better Bound on the Largest Induced Forests in Triangle-Free Planar Graph

Hung Le, Hung Le 0001Graphs Comb 2018 · DOI

TL;DR

This paper improves the known lower bound for the size of the largest induced forest in triangle-free planar graphs. The authors achieve a new bound of $\frac{5}{9}n$, which is a significant improvement over previous results and is conjectured to be the tightest possible.

What Problem Does This Paper Address?

The problem concerns finding the largest possible subgraph that is a forest (a graph with no cycles) and is induced. An induced subgraph means that if two vertices are connected in the original graph, and both are chosen for the subgraph, then the edge between them must also be included. Specifically, the paper focuses on triangle-free planar graphs, which are graphs that can be drawn on a plane without edges crossing and do not contain any triangles (cycles of length 3).

Finding the largest induced forest is related to finding large independent sets (sets of vertices where no two are connected by an edge), which has implications in areas like graph coloring. While there are known bounds for general planar graphs and bipartite planar graphs, the triangle-free planar case has seen slower progress. Previous bounds were around $\frac{4}{9}n$ and $\frac{5}{9}n$ (with additive constants), and this paper aims to tighten this bound.

Methods

The authors employ a sophisticated technique based on discharging and linear programming.

  1. Discharging: This method involves assigning "charges" to graph elements (vertices, edges, faces) and then moving these charges around according to specific rules. The goal is to redistribute charges such that certain properties can be proven. In this context, it's used to establish inequalities of the form $\phi(G) \geq an(G) - bm(G) - cp(G) - dq(G)$, where $\phi(G)$ is the order of the largest induced forest, $n(G)$ is the number of vertices, $m(G)$ is the number of edges, and $p(G)$ and $q(G)$ relate to the presence of specific subgraphs (Q3 and T6 components, respectively).
  2. Linear Programming (LP): The discharging rules and the properties of the graphs under consideration lead to a set of linear constraints. The problem of finding the best constants $a, b, c, d$ that maximize the bound $\phi(G)$ is formulated as a linear program. The authors systematically add constraints to this LP by considering various forbidden subgraphs (like Q3 and T6 components) and their properties. If a graph contains such a forbidden subgraph, it leads to a contradiction with the assumed bound, thus proving that the minimal counterexample cannot contain these structures.
  3. Structural Properties: The proof relies heavily on analyzing the structural properties of triangle-free planar graphs, particularly concerning faces, cycles, and the degrees of vertices. Lemmas are used to establish how induced forests can be extended when certain subgraphs are removed.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The $\frac{5}{9}n$ Bound: The paper establishes a new lower bound of $\frac{5}{9}n$ for the size of the largest induced forest in triangle-free planar graphs. This is a significant improvement and is conjectured to be tight.
  • LP as a Proof Tool: The systematic use of linear programming to encode structural constraints and derive contradictions is a powerful technique. By adding constraints corresponding to forbidden subgraphs, the authors effectively prune the space of possible counterexamples.
  • Focus on Specific Subgraphs (Q3 and T6): The analysis hinges on the properties of Q3 (planar cube) and T6 (K3,3 minus an edge) subgraphs. Understanding how to extend induced forests when these components are present or absent is crucial.
  • Discharging for Bounds: The discharging method, combined with LP, provides a robust framework for proving bounds on graph parameters.

Key Results

The main result is Theorem 1.1: Every triangle-free planar graph of $n$ vertices contains an induced forest of order at least $\frac{5}{9}n$. This improves upon previous bounds and is believed to be the best possible. The proof relies on Theorem 1.2, which establishes the bound using a linear program with specific constraints derived from structural properties of the graphs.

Limitations and Future Work

  • Tightness of the Bound: While the authors present $\frac{5}{9}n$ as the new bound and conjecture it to be tight, they do not explicitly construct a graph that achieves this bound. The paper mentions that the example by Akiyama and Watanabe for bipartite planar graphs might serve as a triangle-free example, suggesting the bound is likely tight.
  • Generalization: The authors suggest that their approach might be extendable to improve bounds for other graph classes, such as graphs with girth 5 or subcubic graphs.
  • Resolving Conjectures: The ultimate goal mentioned is to resolve the Akiyama and Watanabe conjecture on induced forests in planar graphs, and the authors hope their method can be extended to achieve this.

Summary updated

BibTeX
@article{le2018better,
  author = {Hung Le and Hung Le},
  title = {{A Better Bound on the Largest Induced Forests in Triangle-Free Planar Graph}},
  journal = {Graphs Comb},
  year = {2018},
  doi = {10.1007/s00373-018-1944-2},
}
Figure