Search

Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties. In this paper, we study a variant of tree-cut width obtained by changing the threshold for so-called thin nodes in tree-cut decompositions from 2 to 1. We show that this "slim tree-cut width" satisfies all the requirements of an edge-cut based analogue of treewidth, both structural and algorithmic, while being less restrictive than edge-cut width. Our results also include an alternative characterization of slim tree-cut width via an easy-to-use spanning-tree decomposition akin to the one used for edge-cut width, a characterization of slim tree-cut width in terms of forbidden immersions as well as approximation algorithm for computing the parameter. [ABSTRACT FROM AUTHOR]

A graph G contains H as an immersion if there is an injective mapping ϕ : V (H) → V (G) such that for each edge u v ∈ E (H) , there is a path P u v in G joining vertices ϕ (u) and ϕ (v) , and all the paths P u v , u v ∈ E (H) , are pairwise edge-disjoint. An analogue of Hadwiger's conjecture for the clique immersions by Lescure and Meyniel, and independently by Abu-Khzam and Langston, states that every graph G contains K χ (G) as an immersion. We prove that for any constant ε > 0 and integers s , t ≥ 2 , there exists d 0 = d 0 (ε , s , t) such that every K s , t -free graph G with d (G) ≥ d 0 contains a clique immersion of order (1 − ε) d (G). This implies that the above-mentioned conjecture is asymptotically true for graphs without a fixed complete bipartite graph. [ABSTRACT FROM AUTHOR]

A graph G contains another graph H as an immersion if H can be obtained from a subgraph of G by splitting off edges and removing isolated vertices. There is an obvious necessary degree condition for the immersion containment: if G contains H as an immersion, then for every integer k , the number of vertices of degree at least k in G is at least the number of vertices of degree at least k in H. In this paper, we prove that this obvious necessary condition is "nearly" sufficient for graphs with no edge-cut of order 3: for every graph H , every H -immersion free graph with no edge-cut of order 3 can be obtained by an edge-sum of graphs, where each of the summands is obtained from a graph violating the obvious degree condition by adding a bounded number of edges. The condition for having no edge-cut of order 3 is necessary. A simple application of this theorem shows that for every graph H of maximum degree d ≥ 4 , there exists an integer c such that for every positive integer m , there are at most c m unlabeled d -edge-connected H -immersion free m -edge graphs with no isolated vertex, while there are superexponentially many unlabeled (d − 1) -edge-connected H -immersion free m -edge graphs with no isolated vertex. Our structure theorem will be applied in a forthcoming paper about determining the clustered chromatic number of the class of H -immersion free graphs. [ABSTRACT FROM AUTHOR]

A graph G contains another graph H as an immersion if H can be obtained from a subgraph of G by splitting off edges and removing isolated vertices. In this paper, we prove an edge-variant of the Erdős-Pósa property with respect to the immersion containment in 4-edge-connected graphs. More precisely, we prove that for every graph H , there exists a function f such that for every 4-edge-connected graph G , either G contains k pairwise edge-disjoint subgraphs each containing H as an immersion, or there exists a set of at most f (k) edges of G intersecting all such subgraphs. This theorem is best possible in the sense that the 4-edge-connectivity cannot be replaced by the 3-edge-connectivity. [ABSTRACT FROM AUTHOR]

In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain vertex-connectivity condition called leanness. This result had many uses and has been extended to several other decompositions. In this paper, we consider tree-cut decompositions, that have been introduced by Wollan (2015) as a possible edge-version of tree decompositions. We show that every graph admits a tree-cut decomposition of minimum width that additionally satisfies an edge-connectivity condition analogous to Thomas' leanness. [ABSTRACT FROM AUTHOR]

Several min–max relations in graph theory can be expressed in the framework of the Erdős–Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic. [ABSTRACT FROM AUTHOR]

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs ( K5 and K3, 3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for [ABSTRACT FROM AUTHOR]

We consider non-degenerate graph immersions into affine space A n + 1 whose cubic form is parallel with respect to the Levi-Civita connection of the affine metric. There exists a correspondence between such graph immersions and pairs (J , γ) , where J is an n -dimensional real Jordan algebra and γ is a non-degenerate trace form on J. Every graph immersion with parallel cubic form can be extended to an affine complete symmetric space covering the maximal connected component of zero in the set of quasi-regular elements in the algebra J. It is an improper affine hypersphere if and only if the corresponding Jordan algebra is nilpotent. In this case it is an affine complete, Euclidean complete graph immersion, with a polynomial as globally defining function. We classify all such hyperspheres up to dimension 5. As a special case we describe a connection between Cayley hypersurfaces and polynomial quotient algebras. Our algebraic approach can be used to study also other classes of hypersurfaces with parallel cubic form. [ABSTRACT FROM AUTHOR]