Search

We consider the Erdős-Pósa property for immersions and topological minors in tournaments. We prove that for every simple digraph H, k 2 N, and tournament T, the following statements hold: • If in T one cannot find k arc-disjoint immersion copies of H, then there exists a set of OH(k3) arcs that intersects all immersion copies of H in T. • If in T one cannot find k vertex-disjoint topological minor copies of H, then there exists a set of OH(k log k) vertices that intersects all topological minor copies of H in T. This improves the results of Raymond [DMTCS '18], who proved similar statements under the assumption that H is strongly connected. [ABSTRACT FROM AUTHOR]

A propositional logic sentence in conjunctive normal form that has clauses of length at most two (a 2-CNF) can be associated with a multigraph in which the vertices correspond to the variables and edges to clauses. We show that every 2-CNF that has been reduced under the application of certain tautologies, is equisatisfiable to a 2-CNF whose associated multigraph is, in fact, a simple graph. Our main result is a complete characterization of graphs that can support unsatisfiable 2-CNF sentences. We show that a simple graph can support an unsatisfiable reduced 2-CNF sentence if and only if it contains any one of four specific small graphs as a topological minor. Equivalently, all reduced 2-CNF sentences supported on a given simple graph are satisfiable if and only if all subdivisions of those four graphs are forbidden as subgraphs of the original graph. [ABSTRACT FROM AUTHOR]

For a finite fixed collection of graphs F , the F -M-Deletion problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on the smallest function f F such that F -M-Deletion can be solved in time f F (tw) ⋅ n O (1) on n -vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f F (tw) = 2 Ω (tw) , even if G is planar. Our main result is that if F contains a single connected graph H that is either P 5 or is not a minor of the b a n n e r , then f F (tw) = 2 Ω (tw ⋅ log ⁡ tw). [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F , the F -M-Deletion (resp. F -TM-Deletion) problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G , denoted by tw , and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2 O (tw) ⋅ n O (1) , called single-exponential , when H is either P 3 , P 4 , C 4 , the paw , the chair , and the banner for both { H } -M-Deletion and { H } -TM-Deletion , and when H = K 1 , i , with i ≥ 1 , for { H } -TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of { H } -M-Deletion in terms of H. [ABSTRACT FROM AUTHOR]

A temporal graph G is a pair (G , λ) where G is a graph and λ is a function on the edges of G describing when each edge is active. Temporal connectivity then concerns only paths that respect the flow of time. In this context, it is known that Menger's Theorem does not hold. In a seminal paper, Kempe, Kleinberg and Kumar (STOC'2000) defined a graph to be Mengerian if equality holds for every time-function. They then proved that, if each edge is allowed to be active only once in (G , λ) , then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm. [ABSTRACT FROM AUTHOR]

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]

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]