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.

For a fixed positive integer \(k\), two players, \(\textsf {Builder}\) and \(\textsf {Chooser}\), alternate turns playing the following game on a dynamically changing graph that is initially empty. In each round, \(\textsf {Builder}\) introduces a new vertex with edges to all previous vertices and then partitions the entire edge set into two subsets, after which \(\textsf {Chooser}\) deletes one of the two. \(\textsf {Builder}\) attempts to build a clique of size \(k\), while \(\textsf {Chooser}\) attempts to prevent that. We prove tower-type upper and lower bounds on how many rounds \(\textsf {Builder}\) needs to guarantee a \(k\)-clique.

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].

The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar $δ$-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed $δ\geq 0$, we can find balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set $Z$) with any subset of the connected components of $G - Z$ induces again a planar $δ$-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that size of separator is $\mathrm{poly}(δ) \cdot \log n$. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar $δ$-hyperbolic graphs. We prove that Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant $δ$, running in $n\, \mathrm{polylog}(n) \cdot 2^{\mathcal{O}(δ^2)} \cdot \varepsilon^{-\mathcal{O}(δ)}$ time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no $n^{o(δ)}$-time algorithm on planar $δ$-hyperbolic graphs, unless ETH fails.

We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension k as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: every such poset with sufficiently large dimension contains the Kelly example of dimension k as a subposet. Using this result, we obtain a full characterization of the minor-closed graph classes C such that posets with cover graphs in C have bounded dimension: they are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension.

For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes G^{hom}(A) and G^{sim}(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that G^{hom}(A) = G^{hom}(B) if and only if A and B are affine equivalent, and G^{sim}(A) = G^{sim}(B) if and only if A and B are similar.

Abstract A grounded L-graph is the intersection graph of a collection of “L” shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $$\omega $$ ω has chromatic number at most $$17\omega ^4$$ 17 ω 4 . This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $$\chi $$ χ -bounded. We also survey $$\chi $$ χ -boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.

We describe a polynomial-time algorithm which, given a graphGwith treewidtht, approximates the pathwidth ofGto within a ratio of \(O(t\sqrt {\log t})\) . This is the first algorithm to achieve anf(t)-approximation for some functionf. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at leastth+2 has treewidth at leasttor contains a subdivision of a complete binary tree of heighth+1. The boundth+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (withc=2), the following conjecture of Kawarabayashi and Rossman (SODA’18): there exists a universal constantcsuch that every graph with pathwidth Ω(kc) has treewidth at leastkor contains a subdivision of a complete binary tree of heightk. Our main technical algorithm takes a graphGand some (not necessarily optimal) tree decomposition ofGof widtht′ in the input, and it computes in polynomial time an integerh, a certificate thatGhas pathwidth at leasth, and a path decomposition ofGof width at most (t′+1)h+1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of heighth. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC’05) for treewidth.

Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3⋅4^{ω-1}. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo-visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a colouring with the claimed number of colours can be computed in polynomial time.

In 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an O(ω2)-coloring, where ω is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is O(ω log ω)-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time O(log log n)-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of .

We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of . This is the first algorithm to achieve an f(t)-approximation for some function f. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th + 2 has treewidth at least t or contains a subdivision of a complete binary tree of height h + 1. The bound th + 2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c = 2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(kc) has treewidth at least k or contains a subdivision of a complete binary tree of height k. Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t′ in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t′ + 1)h + 1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth.

Abstract Let $${\mathcal {C}}$$ C and $${\mathcal {D}}$$ D be hereditary graph classes. Consider the following problem: given a graph $$G\in {\mathcal {D}}$$ G ∈ D , find a largest, in terms of the number of vertices, induced subgraph of G that belongs to $${\mathcal {C}}$$ C . We prove that it can be solved in $$2^{o(n)}$$ 2 o ( n ) time, where n is the number of vertices of G , if the following conditions are satisfied: the graphs in $${\mathcal {C}}$$ C are sparse, i.e., they have linearly many edges in terms of the number of vertices; the graphs in $${\mathcal {D}}$$ D admit balanced separators of size governed by their density, e.g., $${\mathcal {O}}(\varDelta )$$ O ( Δ ) or $${\mathcal {O}}(\sqrt{m})$$ O ( m ) , where $$\varDelta$$ Δ and m denote the maximum degree and the number of edges, respectively; and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes $${\mathcal {C}}$$ C and $${\mathcal {D}}$$ D : a largest induced forest in a $$P_t$$ P t -free graph can be found in $$2^{\tilde{{\mathcal {O}}}(n^{2/3})}$$ 2 O ~ ( n

We prove that for every integer $$t\geqslant 1$$ , the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is $$\chi $$ -bounded. This is essentially the strongest $$\chi $$ -boundedness result one can get for those kind of graph classes. As a corollary, we prove that for any fixed integers $$k\geqslant 2$$ and $$t\geqslant 1$$ , every k-quasi-planar topological graph on n vertices with any two edges crossing at most t times has $$O(n\log n)$$ edges.

An outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane. We prove that the class of outerstring graphs is $\chi$-bounded, which means that their chromatic number is bounded by a function of their clique number. This generalizes a series of previous results on $\chi$-boundedness of outerstring graphs with various additional restrictions on the shape of curves or the number of times the pairs of curves can cross. The assumption that each curve has an endpoint on the boundary of the half-plane is justified by the known fact that triangle-free intersection graphs of straight-line segments can have arbitrarily large chromatic number.

We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons—whether they are nested, overlapping, or disjoint—and our algorithm thus also decides this relationship.

For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,…,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k≥3, the odd graph K(2k+1,k) has a Hamilton cycle. This and a known conditional result due to Johnson imply that all Kneser graphs of the form K(2k+2a,k) with k≥3 and a≥0 have a Hamilton cycle. We also prove that K(2k+1,k) has at least 22k−6 distinct Hamilton cycles for k≥6. Our proofs are based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words.

Let S be a subset of $$\mathbb {R}^d$$ with finite positive Lebesgue measure. The Beer index of convexity $${\text {b}}(S)$$ of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio $${\text {c}}(S)$$ of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate the relationship between these two natural measures of convexity. We show that every set $$S\subseteq \mathbb {R}^2$$ with simply connected components satisfies $${\text {b}}(S)\leqslant \alpha {\text {c}}(S)$$ for an absolute constant $$\alpha $$ , provided $${\text {b}}(S)$$ is defined. This implies an affirmative answer to the conjecture of Cabello et al. that this estimate holds for simple polygons. We also consider higher-order generalizations of $${\text {b}}(S)$$ . For $$1\leqslant k\leqslant d$$ , the k-index of convexity $${\text {b}}_k(S)$$ of a set $$S\subseteq \mathbb {R}^d$$ is the probability that the convex hull of a $$(k+1)$$ -tuple of points chosen uniformly independently at random from S is contained in S. We show that for every $$d\geqslant 2$$ there is a constant $$\beta (d)>0$$ such that every set $$S\subseteq \mathbb {R}^d$$ satisfies $${\text {b}}_d(S)\leqslant \beta {\text {c}}(S)$$ , provided $${\text {b}}_d(S)$$ exists. We provide an almost matching lower bound by showing that there is a constant $$\gamma (d)>0$$ such that for every $$\varepsilon \in (0,1)$$ there is a set $$S\subseteq \mathbb {R}^d$$ of Lebesgue measure 1 satisfying $${\text {c}}(S)\leqslant \varepsilon $$ and $${\text {b}}_d(S)\geqslant \gamma \frac{\varepsilon }{\log _2{1/\varepsilon }}\geqslant \gamma \frac{{\text {c}}(S)}{\log _2{1/{\text {c}}(S)}}$$ .

We describe an algorithm for computing the separating common tangents of two simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies to the same side of the line. A separating common tangent of two polygons is a tangent of both polygons where the polygons are lying on different sides of the tangent. Each polygon is given as a read-only array of its corners. If a separating common tangent does not exist, the algorithm reports that. Otherwise, two corners defining a separating common tangent are returned. The algorithm is simple and implies an optimal algorithm for deciding if the convex hulls of two polygons are disjoint or not. This was not known to be possible in linear time and constant workspace prior to this paper. An outer common tangent is a tangent of both polygons where the polygons are on the same side of the tangent. In the case where the convex hulls of the polygons are disjoint, we give an algorithm for computing the outer common tangents in linear time using constant workspace.

Let S be a subset of R^d with finite positive Lebesgue measure. The Beer index of convexity b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio c(S) of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate a relationship between these two natural measures of convexity of S. We show that every subset S of the plane with simply connected components satisfies b(S) <= alpha c(S) for an absolute constant alpha, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. asserting that this estimate holds for simple polygons. We also consider higher-order generalizations of b(S). For 1 <= k <= d, the k-index of convexity b_k(S) of a subset S of R^d is the probability that the convex hull of a (k+1)-tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d >= 2 there is a constant beta(d) > 0 such that every subset S of R^d satisfies b_d(S) <= beta c(S), provided b_d(S) exists. We provide an almost matching lower bound by showing that there is a constant gamma(d) > 0 such that for every epsilon from (0,1] there is a subset S of R^d of Lebesgue measure one satisfying c(S) <= epsilon and b_d(S) >= (gamma epsilon)/log_2(1/epsilon) >= (gamma c(S))/log_2(1/c(S)).

Streib and Trotter proved in 2012 that posets with bounded height and with planar cover graphs have bounded dimension. Recently, Joret et al. proved that the dimension is bounded for posets with bounded height whose cover graphs have bounded tree-width. In this paper, it is proved that posets of bounded height whose cover graphs exclude a fixed (topological) minor have bounded dimension. This generalizes both the aforementioned results and verifies a conjecture of Joret et al. The proof relies on the Robertson-Seymour and Grohe-Marx structural decomposition theorems.

Recently, it was proved that triangle-free intersection graphs of $$n$$ line segments in the plane can have chromatic number as large as $$\Theta (\log \log n)$$ . Essentially the same construction produces $$\Theta (\log \log n)$$ -chromatic triangle-free intersection graphs of a variety of other geometric shapes—those belonging to any class of compact arc-connected sets in $$\mathbb {R}^2$$ closed under horizontal scaling, vertical scaling, and translation, except for axis-parallel rectangles. We show that this construction is asymptotically optimal for intersection graphs of boundaries of axis-parallel rectangles, which can be alternatively described as overlap graphs of axis-parallel rectangles. That is, we prove that triangle-free rectangle overlap graphs have chromatic number $$O(\log \log n)$$ , improving on the previous bound of $$O(\log n)$$ . To this end, we exploit a relationship between off-line coloring of rectangle overlap graphs and on-line coloring of interval overlap graphs. Our coloring method decomposes the graph into a bounded number of subgraphs with a tree-like structure that “encodes” strategies of the adversary in the on-line coloring problem. Then, these subgraphs are colored with $$O(\log \log n)$$ colors using a combination of techniques from on-line algorithms (first-fit) and data structure design (heavy-light decomposition).

It is proved that there are triangle-free intersection graphs of line segments in the plane with arbitrarily small ratio between the maximum size of an independent set and the total number of vertices.

An outerstring graph is an intersection graph of curves lying in a halfplane with one endpoint on the boundary of the halfplane. It is proved that the outerstring graphs are χ-bounded, that is, their chromatic number is bounded by a function of their clique number. This generalizes a series of previous results on χ-boundedness of outerstring graphs with various restrictions of the shape of the curves or the number of times the pairs of curves can intersect. This also implies that the intersection graphs of x-monotone curves with bounded clique number have chromatic number O(log n), improving the previous polylogarithmic upper bound. The assumption that each curve has an endpoint on the boundary of the halfplane is justified by the known fact that triangle-free intersection graphs of straight-line segments can have arbitrarily large chromatic number.

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line $$L$$ if the intersection of any member with $$L$$ is a nonempty segment. It is proved that the intersection graphs of simple families of compact arc-connected sets in the plane pierced by a common line have chromatic number bounded by a function of their clique number.

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $$X$$ in $$\mathbb{R }^2$$ that is not an axis-aligned rectangle and for any positive integer $$k$$ produces a family $$\mathcal{F }$$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $$X$$ , such that no three sets in $$\mathcal{F }$$ pairwise intersect and $$\chi (\mathcal{F })>k$$ . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.