Abstract. We prove that every connected [Formula: see text]-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected [Formula: see text]-free graph [Formula: see text] with independence number at least three contains a three-vertex induced path with vertices [Formula: see text] in order, such that every neighbor of [Formula: see text] is also adjacent to one of [Formula: see text].

Abstract. This is a corrigendum for the article “Orthogonal Tree-Decompositions of Graphs” [SIAM J. Discrete Math. 32(2):839–863, 2018].

The long standing Zarankiewicz's conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(Kn,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(Kn,n) of Kn,n is at least 0.987 • Z(n,n) + o(n4). Finally, we show that if a drawing of Kn,n has no K3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z(n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result.

Abstract. Denote by [Formula: see text] the smallest eigenvalue of the signless Laplacian matrix of an [Formula: see text]-vertex graph [Formula: see text]. Brandt conjectured in 1997 that for regular triangle-free graphs [Formula: see text]. We prove a stronger result: If [Formula: see text] is a triangle-free graph, then [Formula: see text]. Brandt’s conjecture is a subproblem of two famous conjectures of Erdős: (1) Sparse-half-conjecture: Every [Formula: see text]-vertex triangle-free graph has a subset of vertices of size [Formula: see text] spanning at most [Formula: see text] edges. (2) Every [Formula: see text]-vertex triangle-free graph can be made bipartite by removing at most [Formula: see text] edges. In our proof we use linear algebraic methods to upper bound [Formula: see text] by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras.

The main problem in the area of graph property testing is to understand which graph properties are testable, which means that with constantly many queries to any input graph G, a tester can decide with good probability whether G satisfies the property, or is far from satisfying the property. Testable properties are well understood in the dense model and in the bounded degree model, but little is known in sparse graph classes when graphs are allowed to have unbounded degree. This is the setting of the sparse model. We prove that for any proper minor-closed class 𝒢, any monotone property (i.e., any property that is closed under taking subgraphs) is testable for graphs from 𝒢 in the sparse model. This extends a result of Czumaj and Sohler (FOCS'19), who proved it for monotone properties with finitely many forbidden subgraphs. Our result implies for instance that for any integers k and t, k-colorability of K_t-minor free graphs is testable in the sparse model. Elek recently proved that monotone properties of bounded degree graphs from minor-closed classes that are closed under disjoint union can be verified by an approximate proof labeling scheme in constant time. We show again that the assumption of bounded degree can be omitted in his result.

For a class C of graphs, we define C-edge-brittleness of a graph G as the minimum ℓ such that the vertex set of G can be partitioned into sets inducing a subgraph in C and there are ℓ edges having ends in distinct parts. We characterize classes of graphs having bounded C-edge-brittleness for a class C of forests or a class C of graphs with no K4∖e topological minors in terms of forbidden obstructions. We also define C-vertex-brittleness of a graph G as the minimum ℓ such that the edge set of G can be partitioned into sets inducing a subgraph in C and there are ℓ vertices incident with edges in distinct parts. We characterize classes of graphs having bounded C-vertex-brittleness for a class C of forests or a class C of outerplanar graphs in terms of forbidden obstructions. We also investigate the relations between the new parameters and the edit distance.

The Hall ratio of a graph $G$ is the maximum value of $v(H) / \alpha(H)$ taken over all non-null subgraphs $H \subseteq G$. For any graph, the Hall ratio is a lower-bound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.

We give a natural sufficient condition for an intersection graph of compact convex sets in $\mathbb{R}^d$ to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.

This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here “linear size” means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(\sqrt{n})$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.

The following is a corrigendum to [ Orthogonal tree decompositions of graphs, SIAM J. Discrete Math., 32 (2018), pp. 839--863].

A result of Plotkin, Rao, and Smith implies that graphs with polynomial expansion have strongly sublinear separators. We prove a converse of this result showing that hereditary classes of graphs with strongly sublinear separators have polynomial expansion. This confirms a conjecture of the first author.

We prove that for any constant k and any epsilon < 1, there exist bimatrix win-lose games for which every epsilon-WSNE requires supports of cardinality greater than k. To do this, we provide a graph-theoretic characterization of win-lose games that possess epsilon-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou and Myers.

Ramsey's theorem says that for every clique $H_1$ and for every graph $H_2$ with no edges, all graphs containing neither of $H_1,H_2$ as induced subgraphs have bounded order. What if, instead, we exclude a graph $H_1$ with a vertex whose deletion gives a clique, and the complement $H_2$ of another such graph? This no longer implies bounded order, but it implies tightly restricted structure that we describe. There are also several related subproblems (what if we exclude a star and the complement of a star? what if we exclude a star and a clique? and so on) and we answer a selection of these.