More Like this

1. Induced Subgraphs and Tree Decompositions IV. (Even Hole, Diamond, Pyramid)-Free Graphs

   https://doi.org/10.37236/11623  

   Abrishami, Tara; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (April 2023, The Electronic Journal of Combinatorics)

   A hole in a graph $$G$$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $$K_4$$ by removing an edge. A pyramid is a graph consisting of a vertex $$a$$ called the apex and a triangle $$\{b_1, b_2, b_3\}$$ called the base, and three paths $$P_i$$ from $$a$$ to $$b_i$$ for $$1 \leq i \leq 3$$, all of length at least one, such that for $$i \neq j$$, the only edge between $$P_i \setminus \{a\}$$ and $$P_j \setminus \{a\}$$ is $$b_ib_j$$, and at most one of $$P_1$$, $$P_2$$, and $$P_3$$ has length exactly one. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-free if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. Cameron, da Silva, Huang, and Vušković proved that (even hole, triangle)-free graphs have treewidth at most five, which motivates studying the treewidth of even-hole-free graphs of larger clique number. Sintiari and Trotignon provided a construction of (even hole, pyramid, $$K_4$$)-free graphs of arbitrarily large treewidth. Here, we show that for every $$t$$, (even hole, pyramid, diamond, $$K_t$$)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and three-path-configurations, diamonds, and a fixed complete graph. The proof uses “non-crossing decompositions” methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of “non-crossing decompositions” to prove bounded treewidth in a graph class of unbounded maximum degree. 

   more » « less
2. Induced subgraphs and tree decompositions V. one neighbor in a hole

   https://doi.org/10.1002/jgt.23055  

   Abrishami, Tara; Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie; Vušković, Kristina (November 2023, Journal of Graph Theory)

   Abstract What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the “basic treewidth obstructions”). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called “layered wheels,” contain wheels, where awheelconsists of ahole(i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth. 

   more » « less
3. Induced subgraphs and tree decompositions XIII. Basic obstructions in H-free graphs for finite H

   https://doi.org/10.19086/aic.2024.6  

   Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (November 2024, Advances in Combinatorics)

   Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every t ∈ N, the t-basic obstructions: the graphs Kt+1 and Kt,t, along with the subdivisions of the t-by-t wall and their line graphs. But this list is far from complete. The simplest example of a “non-basic” obstruction is due to Pohoata and Davies (independently). For every n ∈ N, they construct certain graphs of treewidth n and with no 3-basic obstruction as an induced subgraph, which we call n-arrays. Let us say a graph class G is clean if the only obstructions to bounded treewidth in G are in fact the basic ones. It follows that a full description of the induced subgraph obstructions to bounded treewidth is equivalent to a characterization of all families H of graphs for which the class of all H-free graphs is clean (a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H). This remains elusive, but there is an immediate necessary condition: if H-free graphs are clean, then there are only finitely many n ∈ N such that there is an n-array which is H-free. The above necessary condition is not sufficient in general. However, the situation turns out to be different if H is finite: we prove that for every finite set H of graphs, the class of all H-free graphs is clean if and only if there is no H-free n-array except possibly for finitely many values of n. 

   more » « less
4. Complexity of Ck-Coloring in Hereditary Classes of Graphs

   Chudnovsky, M.; Huang, S.; Rzazewski, P.; Spirkl, S.; and Zhong, M. (September 2019, European Symposium on Algorithms)

   For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of Pt-free graphs. We show that for every odd k ≥ 5 the Ck-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P9-free graphs. On the other hand, we prove that the extension version of Ck-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw. 

   more » « less
5. On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

   Cohen-Addad, Vincent; Filtser, Arnold; Klein, Philip N; Le, Hung (October 2020, Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science)

   null (Ed.)

   Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ϵ factor, of total weight at most Oϵ(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion ϵD. Namely, given a minor-free graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidth-Oϵ(log n) graphs such that ∀u,v∈V, Ef∼D[dH(f(u),f(v))]≤dG(u,v)+ϵD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth). 

   more » « less