A graph class is \(\chi\)-bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersection graphs of straight-line segments in the plane are \(\chi\)-bounded, but this was disproved by Pawlik et al. (2014), who showed another way to force large chromatic number in this class\(\unicode{x2014}\)by triangle-free graphs \(B_k\) with \(\chi(B_k) = k\) constructed by Burling (1965). This also disproved the celebrated conjecture of Scott (1997) that classes of graphs excluding induced subdivisions of a fixed graph are \(\chi\)-bounded.

Abstract. For a tree decomposition [Formula: see text] of a graph [Formula: see text], let [Formula: see text] denote the maximum size of an induced matching in [Formula: see text] with the property that some bag of [Formula: see text] contains at least one endpoint of every edge of the matching. The induced matching treewidth of a graph [Formula: see text] is the minimum value of [Formula: see text] over all tree decompositions [Formula: see text] of [Formula: see text]. Classes of graphs with bounded induced matching treewidth admit polynomial-time algorithms for a number of problems, including Independent Set, [Formula: see text]-Coloring, Odd Cycle Transversal, and Feedback Vertex Set. In this paper, we focus on combinatorial properties of such classes. First, we show that graphs with bounded induced matching treewidth that exclude a fixed biclique as an induced subgraph have bounded tree-independence number, which is another well-studied parameter defined in terms of tree decompositions. This sufficient condition about excluding a biclique is also necessary, as bicliques have unbounded tree-independence number. Second, we show that graphs with bounded induced matching treewidth that exclude a fixed clique have bounded chromatic number, that is, classes of graphs with bounded induced matching treewidth are [Formula: see text]-bounded. The two results confirm two conjectures due to Lima et al. [32 nd Annual European Symposium on Algorithms (ESA 2024), LIPIcs 308, pp. 85:1–85:17].

Abstract. The circumference of a graph [Formula: see text] with at least one cycle is the length of a longest cycle in [Formula: see text]. A classic result of Birmelé [ J. Graph Theory, 43 (2003), pp. 24–25] states that the treewidth of [Formula: see text] is at most its circumference minus 1. In case [Formula: see text] is 2-connected, this upper bound also holds for the pathwidth of [Formula: see text]; in fact, even the treedepth of [Formula: see text] is upper bounded by its circumference (Briański et al. [ Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659–664]). In this paper, we study whether similar bounds hold when replacing the circumference of [Formula: see text] by its cocircumference, defined as the largest size of a bond in [Formula: see text], an inclusionwise minimal set of edges [Formula: see text] such that [Formula: see text] has more components than [Formula: see text]. In matroidal terms, the cocircumference of [Formula: see text] is the circumference of the bond matroid of [Formula: see text]. Our first result is the following “dual” version of Birmelé’s theorem: The treewidth of a graph [Formula: see text] is at most its cocircumference. Our second and main result is an upper bound of [Formula: see text] on the pathwidth of a 2-connected graph [Formula: see text] with cocircumference [Formula: see text]. Contrary to circumference, no such bound holds for the treedepth of [Formula: see text]. Our two upper bounds are best possible up to a constant factor.

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix $A$ and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of $A$, and when parameterized by the dual tree-depth and the entry complexity of $A$; both these parameterization imply that $A$ is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the $\ell_1$-norm of the Graver basis is bounded by a function of the maximum $\ell_1$-norm of a circuit of $A$. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix $A$ that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the $\ell_1$-norm of the Graver basis of the constraint matrix, when parameterized by the $\ell_1$-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size k are reconfigurable in an n-vertex interval graph, then there is a reconfiguration sequence of length 𝒪(k⋅ n²). We also provide a construction in which the shortest reconfiguration sequence is of length Ω(k²⋅ n). As a counterpart to these results, we also establish that Independent Set Reconfiguration is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.

We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $\mathcal{C}$ one can find two disjoint vertex subsets $A,B\subseteq V(G)$ such that $|A|\geq (1/2-\varepsilon)\cdot n$ and $|B|=\Omega(n^{1-\varepsilon})$; and either ${dist}(a,b)\leq d$ for all $a\in A$ and $b\in B$, or ${dist}(a,b)>d$ for all $a\in A$ and $b\in B$. We also show some stronger variants of this statement, including a generalization to the setting of first-order interpretations of nowhere dense graph classes.