More Like this

1. 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
2. Subdivided Claws and the Clique-Stable Set Separation Property

   https://doi.org/10.1007/978-3-030-62497-2  

   Chudnovsky, Maria and (February 2021, MATRIX book series)

   null (Ed.)

   Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c ∈ N such that for every graph G ∈ C there is a collection P of partitions (X, Y ) of the vertex set of G with |P| ≤ |V (G)| c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = ∅, then there is (X, Y ) ∈ P with K ⊆ X and S ⊆ Y . In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. G¨o¨os in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S, K of graphs and show that for every S ∈ S and K ∈ K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property. 

   more » « less
3. Subdivided Claws and the Clique-Stable Set Separation Property

   https://doi.org/10.1007/978-3-030-62497-2_29  

   Chudnovsky, Maria and (February 2021, MATRIX book series)

   Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c∈N such that for every graph G∈C there is a collection P of partitions (X,Y) of the vertex set of G with |P|≤|V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K∩S=∅, then there is (X,Y)∈P with K⊆X and S⊆Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by Göös in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S,K of graphs and show that for every S∈S and K∈K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property. 

   more » « less
4. An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of k

   https://doi.org/10.3390/math11194068  

   Kaudan, Chirag; Taylor, Rachel; Narayan, Darren A. (October 2023, Mathematics)

   For a given a graph G, the zero forcing number of G, Z(G), is the smallest cardinality of any set S of vertices on which repeated applications of the forcing rule results in all vertices being included in S. The forcing rule is as follows: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. The failed zero forcing number of a graph was introduced by Fetcie, Jacob, and Saavedra and was defined as the cardinality of the largest set of vertices which fails to force all vertices in the graph. In 2021, Gomez et al. proved that there were exactly 15 graphs with a failed zero forcing number of two, but their proof was complicated, requiring the analysis of many graph families. We present an “inverse” approach where we start with a set of vertices S and then see which graphs have S as a maximum-sized failed zero forcing set. This results in not only a shorter proof but characterizes which graphs have a particular failed zero forcing set. In our proof, we characterize the graphs which have a failed zero forcing set S where |S|=2, meaning considering all simple graphs of order two as induced subgraphs. This approach also has greater potential for characterizing graphs where F(G)>2 since many general arguments on the structure of graphs are developed in this type of analysis and are applicable for failed zero forcing sets of any size. 

   more » « less
5. Weighted Additive Spanners

   https://doi.org/10.1007/978-3-030-60440-0_32  

   Ahmed, R; Bodwin, G; Darabi, F; Kobourov, S; Spence, R (October 2020, 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG))

   A spanner of a graph G is a subgraph H that approximately preserves shortest path distances in G. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured multiplicatively. In this work, we investigate whether one can similarly extend constructions of spanners with purely additive error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic +2 and +4 unweighted spanners (both all-pairs and pairwise) to +2W and +4W weighted spanners, where W is the maximum edge weight. Specifically, we show that a weighted graph G contains all-pairs (pairwise) +2W and +4W weighted spanners of size O(n3/2) and O(n7/5) (O(np1/3) and O(np2/7)) respectively. For a technical reason, the +6 unweighted spanner becomes a +8W weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that G contains all-pairs (pairwise) +8W weighted spanners of size O(n4/3) (O(np1/4)). 

   more » « less