Search

The problem of when a given digraph contains a subdivision of a fixed digraph F is considered. Bang-Jensen et al. [4] laid out foundations for approaching this problem from the algorithmic point of view. In this article, we give further support to several open conjectures and speculations about algorithmic complexity of finding F-subdivisions. In particular, up to five exceptions, we completely classify for which 4-vertex digraphs F, the F-subdivision problem is polynomial-time solvable and for which it is NP-complete. While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, some of the polynomial-time solvable cases involve relatively complicated algorithms.

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that (k+k)-free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.

In the graph sharing game, two players share a connected graph G with nonnegative weights assigned to the vertices claiming and collecting the vertices of G one by one, while keeping the set of all claimed vertices connected through the whole game. Each player wants to maximize the total weight of the vertices they have gathered by the end of the game, when the whole G has been claimed. It is proved that for any class G of graphs with an odd number of vertices and with forbidden subdivision of a fixed graph (e.g., for the class G of planar graphs with an odd number of vertices), there is a constant cG>0 such that the first player can secure at least the cG proportion of the total weight of G whenever G∈G. Known examples show that such a constant does no longer exist if any of the two conditions on the class G (an odd number of vertices or a forbidden subdivision) is removed. The main ingredient in the proof is a new structural result on weighted graphs with a forbidden subdivision.

We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least~5 in this class is 3-colorable.

A graph is strongly even-cycle decomposable if the edge set of every subdivision with an even number of edges can be partitioned into cycles of even length. We prove that several fundamental composition operations that preserve the property of being Eulerian also yield strongly even-cycle decomposable graphs. As an easy application of our theorems, we give an exact characterization of the set of strongly even-cycle decomposable cographs.

Given graphs G and H with VHi¾?VG, suppose that we have a u,v-path Puv in G for each edge uv in H. There are obvious additional conditions that ensure that G contains H as a rooted subgraph, subdivision, or immersion; we seek conditions that ensure that G contains H as a rooted minor or minor. This naturally leads to studying sets of paths that form an H-immersion, with the additional property that paths that contain the same vertex must have a common endpoint. We say that H is contractible if, whenever G contains such an H-immersion, G must also contain a rooted H-minor. We show, for example, that forests, cycles, K4, and K1, 1, 3 are contractible, but that graphs that are not 6-colorable and graphs that contain certain subdivisions of K2, 3 are not contractible.

We prove that if G is a 5-connected graph embedded on a surface Σ (other than the sphere) with face-width at least 5, then G contains a subdivision of K5. This is a special case of a conjecture of P. Seymour, that every 5-connected nonplanar graph contains a subdivision of K5. Moreover, we prove that if G is 6-connected and embedded with face-width at least 5, then for every v ∈ V(G), G contains a subdivision of K5 whose branch vertices are v and four neighbors of v.

A semi-topological r-wheel, denoted by , is a subdivision of the r-wheel preserving the spokes. This paper describes the r-connected graphs having no -subgraphs. For , these are shown to be only , while the class of 3-connected -free graphs is unexpectedly rich. First, every graph G in has an efficiently recognizable set of “contractible edges” (sometimes empty) such that a contraction minor belongs to if and only if F is a part of this set. So, the subclass of ante-contraction members of plays a key role. Second, the members of have 3-edge cuts. The familiar cactus representation of minimum edge cuts (Dinits et al., in: Issledovaniya po Diskretnoy Optimizatsii, Nauka, Moscow, pp. 290–306, 1976 (Russian); also A. Schrijver, Combinatorial Optimization (Polyhedra and Efficiency), Algorithms and Combinatorics, Vol. 24, Springer, 2003, p. 253) maps onto the class of trees whose internal vertices have even degrees, equal to 6 for any vertex adjacent to a leaf. The description of (quite concise as expressed in appropriate terms) refers to the explicit reconstruction of the reverse image of such a tree. We also derive the upper bound on the number of edges in an arbitrary n-vertex -free graph, , and conjecture that its maximum equals .

Given graphs G and H, we say G is H-linked if for every injective mapping l: V(H)→V(G), we can find a subgraph H′ of G that is a subdivision of H with l(v) being the vertex of H′ corresponding to each vertex v of H. In this article, we prove two results on H-linkage for 4-vertex graphs H. Goddard showed that 4-connected planar triangulations are 4-ordered, or in other words C4-linked. We strengthen this by showing that 4-connected planar triangulations are (K4−e)-linked. X. Yu characterized certain graphs related to P4-linkage. We use his characterization to show that every 7-connected graph is P4-linked, and to construct 6-connected graphs that are not P4-linked. © 2011 Wiley Periodicals, Inc. J Graph Theory, © 2012 Wiley Periodicals, Inc. (Contract grant sponsor: U.S. National Security Agency; Contract grant numbers: H98230-06-1-0051; H98230-09-1-0065 (to M. N. E.); Contract grant sponsor: NSF; Contract grant numbers: DMS-0652306; DMS-0852452 (to G. Y.). The United States Government is authorized to reproduce and distribute reprints notwith-standing any copyright notation herein.)

Let e be a real number such that **image** and t a positive integer. Let n be a sufficiently large positive integer as a function of t and e. We show that every n-vertex graph with at least n1+e edges contains a subdivision of Kt in which each edge of Kt is subdivided less than 10/e times. This refines the main result in [A. Kostochka and Pyber, Combinatorica 8 (1988), 83–86] and resolves an open question raised there. We also pose some questions. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:139-152, 2011 © 2011 Wiley Periodicals, Inc.

Gross and Rosen asked if the genus of a 2-dimensional complex K embeddable in some (orientable) surface is equal to the genus of the graph of appropriate barycentric subdivision of K. We answer the nonorientable genus and the Euler genus versions of Gross and Rosen's question in affirmative. We show that this is not the case for the orientable genus by proving that taking ⌊ log2 g⌋ th barycentric subdivision is not sufficient, where g is the genus of K. On the other hand, (1+⌈log2(g+2)⌉)th subdivision is proved to be sufficient. © 1997 John Wiley & Sons, Inc.

It is proved that every finite digraph of minimum outdegree 3 contains a subdivision of the transitive tournament on 4 vertices. © 1996 John Wiley & Sons, Inc.

We prove a theorem on path systems implying the conjecture of Bollobas that there exists a function f(k, m) (where k and m are natural numbers) satisfying the following: For each graph G of minimum degree at least f(k, m) there exists a graph H of minimum degree at least k such that G contains the graph obtained from H by subdividing each edge m times.

We prove a theorem saying, when taken together with previous results of Bondy, Hemminger, and Thomassen, that every locally finite, infinite tree not containing a subdivision of the dyadic tree (i. e., the regular tree of degree 3) is uniquely determined, up to isomorphism, from its collection of vertex-deleted subgraphs. Furthermore, as another partial result concerning the reconstruction of locally finite trees, we show that the same is true for locally finite trees whose set of vertices of degree s is nonempty and finite (for some positive integer s).

It is proved that every cubic graph with crossing number at least two contains a subdivision of one of eight graphs.