Forbidden Bicliques Bound Tree-Independence in P5-Free Graphs

Tree-independence number asks for a tree decomposition whose bags contain only small independent sets. It is weaker than controlling bag size, yet it still supports structural and algorithmic consequences. The immediate obstruction is induced bicliques: $K_{\ell,\ell}$ itself forces tree-independence number at least $\ell$. The harder question is whether excluding large induced bicliques removes the remaining obstruction inside a natural hereditary graph class.

The authors resolve that question for induced five-vertex paths. They prove that every graph with neither an induced $P_5$ nor an induced $K_{\ell,\ell}$ has tree-independence number at most $4\ell-4$. This confirms the $t=5$ case of a conjecture asking for bounded tree-independence number in all $\{P_t,K_{\ell,\ell}\}$-free graph classes.

Core Contribution

The contribution is a structural theorem rather than an experimental result. For every positive integer $\ell$, the two forbidden-subgraph conditions imply a linear upper bound on the largest independent set occurring in a bag of a suitable tree decomposition. The bound is explicit, $4\ell-4$, rather than an unspecified function of $\ell$.

The proof works by improving a carefully selected decomposition. The authors identify a local configuration that violates a desired normal form, then replace the decomposition with one that is better under a secondary criterion. The induced-$P_5$ restriction is essential: it excludes adjacency patterns that would otherwise make the repair fail. The argument therefore turns a global decomposition parameter into a local forbidden-pattern analysis.

Technical Approach

The construction partitions vertices around a chosen vertex $r$ and two vertices $x,y$ in its neighborhood. It defines a set $M$ and a boundary set $U$ consisting of vertices in $N(r)$ that have neighbors outside $M$. Figure 1 depicts this split. The proof then derives restrictions on how components outside $M$ can connect back through the boundary. When an assumed adjacency is missing, the authors exhibit five vertices that induce a $P_5$; these contradictions force the attachment structure needed for the decomposition surgery.

The repair separates a master copy of the tree for $M$ from copies associated with components outside $M$, then reconnects them through controlled bags. Figure 3 illustrates this master-and-component construction. In the simpler case, the master bags retain their intersection with $M$ and add specified boundary vertices, while component bags combine local vertices with a constrained attachment set. A separate, more involved argument handles the case where the chosen pair $(x,y)$ is a bad pair.

The coefficient four comes from the independent-set accounting in a modified master bag. The proof splits an independent set according to its relationship with $N(r)$ and neighborhoods of $x$ and $y$, bounding the resulting pieces by $2\ell-2$, $\ell-1$, and $\ell-1$. Thus,

Component bags admit a direct bound under the same forbidden-biclique condition, while the bad-pair case requires additional structural claims to preserve the global threshold.

Results and Analysis

There are no datasets, runtime measurements, or empirical comparisons; the evidence is a mathematical proof. The central quantitative result is the universal $4\ell-4$ upper bound, and the proof maintains it through both decomposition cases. That is enough to establish the conjectured boundedness statement for $t=5$.

The theorem identifies induced bicliques as a controlled obstruction in the $P_5$-free setting, but it should be read as a specific advance rather than a full resolution of the wider conjecture. It does not cover arbitrary forbidden path lengths $t$, and the displayed upper bound does not by itself establish the best possible coefficient. Its value is primarily structural: researchers studying decomposition parameters and algorithms on hereditary graph classes can use the theorem as a boundedness guarantee in the $P_5$-free case.