The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_{𝓁,𝓁} forces tree-independence number at least 𝓁. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers t and 𝓁, {P_t,K_{𝓁,𝓁}}-free graphs have bounded tree-independence number. We prove this conjecture for t = 5 by showing that every {P₅,K_{𝓁,𝓁}}-free graph has tree-independence number at most 4𝓁. We also obtain related bounds for the weaker parameter of α-degeneracy.

We prove that for any circle graph \(H\) with at least one edge and for any positive integer \(k\), there exists an integer \(t = t(k,H)\) so that every graph \(G\) either has a vertex-minor isomorphic to the disjoint union of \(k\) copies of \(H\), or has a \(t\)-perturbation with no vertex-minor isomorphic to \(H\). Using the same techniques, we also prove that for any planar multigraph \(H\), every binary matroid either has a minor isomorphic to the cycle matroid of \(kH\), or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of \(H\).

For a positive integer k , a {k}-Roman dominating function of a graph G = (V,E) is a function f: V —> {0,1,... ,k} satisfying f(N(v)) ≥ k for each vertex v ε V with f(v) = 0. Every graph G satisfes γ { Rk } (G) ≤ kγ(G) , where γ { Rk } ( G ) denotes the minimum weight of a { k }-Roman dominating function of G and γ(G) is the domination number of G . In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of { k }-Roman trees studied by Wang et al. in 2021 to general graphs. We prove that for every k ≥ 3, the problem of recognizing { k }-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the { k }-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.

An induced packing of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic Erdős-Pósa theorem to induced packings of cycles. More specifically, we show that there exists a function f (k) = O (k log k ) such that for every positive integer k, every graph G contains either an induced packing of k cycles or a set X of at most f (k ) vertices such that the closed neighbourhood of X intersects all cycles in G. Our proof is constructive and yields a polynomial-time algorithm finding either the induced packing of cycles or the set X. Furthermore, we show that for every positive integer d, if a graph G does not contain two cycles at distance more than d, then G contains sets X1, X2 ⊆ V (G ) with |X1| ≤ 12(d + 1) and |X2| ≤ 12 such that, after removing the ball of radius 2d around X1 or the ball of radius 3d around X2, the resulting graphs are forests.