Search

Abstract The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A binary CSP instance can be presented as a labelled graph encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of this graph. One type of restriction is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture classes defined by language restrictions, or the well-known structural property of acyclicity. We extend the notion of pattern and introduce the notion of a topological minor of a binary CSP instance. By forbidding a finite set of patterns from occurring as topological minors we obtain a compact mechanism for expressing novel tractable subproblems of the CSP, including new generalisations of the class of acyclic instances. [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]

Mader conjectured that every C 4 -free graph has a subdivision of a clique of order linear in its average degree. We show that every C 6 -free graph has such a subdivision of a large clique. We also prove the dense case of Mader's conjecture in a stronger sense, i.e., for every c , there is a c ′ such that every C 4 -free graph with average degree c n 1 / 2 has a subdivision of a clique K ℓ with ℓ = ⌊ c ′ n 1 / 2 ⌋ where every edge is subdivided exactly 3 times. [ABSTRACT FROM AUTHOR]

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter |H|. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a "typical" application of the structure theorem, we show that on graphs excluding H as a topological subgraph, Partial Dominating Set (find k vertices whose closed neighborhood has maximum size) can be solved in time f(H,k)· nO(1). More significantly, we show that on graphs excluding H as a topological subgraph, Graph Isomorphism can be solved in time nf(H). This result unifies and generalizes two previously known important polynomial time solvable cases of Graph Isomorphism: boundeddegree graphs [E. M. Luks, J. Comput. System Sci., 25 (1982), pp. 42-65] and H-minor free graphs [I. N. Ponomarenko, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174 (1988), pp. 147-177, 182]. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition. [ABSTRACT FROM AUTHOR]

Abstract: A classical result of Halin states that if a graph G contains n disjoint rays for every , then G contains infinitely many disjoint rays. The question how this generalizes to graphs other than rays leads to the notion of ubiquity: a graph A is ubiquitous with respect to a relation ⩽ between graphs (such as the subgraph relation or the minor relation) if for all implies , where nA denotes the disjoint union of n copies of A (for or ). A connected graph is tree-like if all its blocks are finite. The main results of the present paper establish a link between the concepts of ubiquity and well-quasi-ordering, thus offering the opportunity to apply well-quasi-ordering results (such as the graph minor theorem or Nash-Williamsʼ tree theorem) to ubiquity problems. Several corollaries are derived showing that wide classes of locally finite tree-like graphs are ubiquitous with respect to the minor or topological minor relation. [Copyright &y& Elsevier]

Abstract: Let be the smallest number such that every graph of average degree contains a subdivision of . So far, the best known asymptotic bounds for are . As observed by Łuczak, the lower bound is obtained by considering bipartite random graphs. Since with high probability the connectivity of these random graphs is about the same as their average degree, a connectivity of is necessary to guarantee a subdivided . Our main result shows that for bipartite graphs this gives the correct asymptotics. We also prove that in the non-bipartite case a connectivity of suffices to force a subdivision of . Moreover, we slightly improve the constant in the upper bound for from (which is due to Komlós and Szemerédi) to . [Copyright &y& Elsevier]

We prove that there exists a function f(ℓ) such that the vertex set of every f(ℓ)-connected graph G can be partitioned into sets S and T such that each vertex in S has at least ℓ neighbours in T and both G[S] and G[T] are ℓ-connected. This implies that there exists a function g(ℓ,H) such that every g(ℓ,H)-connected graph contains a subdivision TH of H so that G−V(TH) is ℓ-connected. We also prove an analogue with connectivity replaced by minimum degree. Furthermore, we show that there exists a function h(ℓ) such that the vertex set of every graph G of minimum degree at least h(ℓ) can be partitioned into sets S and T such that both G[S] and G[T] have minimum degree at least ℓ and the bipartite subgraph between S and T has average degree at least ℓ. [Copyright &y& Elsevier]

We prove that every graph of minimum degree at least r and girth at least 186 contains a subdivision of Kr+1 and that for r⩾435 a girth of at least 15 suffices. This implies that the conjecture of Hajo´s that every graph of chromatic number at least r contains a subdivision of Kr (which is false in general) is true for graphs of girth at least 186 (or 15 if r⩾436). More generally, we show that for every graph H of maximum degree Δ(H)⩾2, every graph G of minimum degree at least {Δ(H),3} and girth at least 166log∣H∣/logΔ(H) contains a subdivision of H. This bound on the girth of G is best possible up to the value of the constant and improves a result of Mader, who gave a bound linear in ∣H∣. [Copyright &y& Elsevier]