Search

For a finite collection of graphs F, the F -TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S = V (G) with | S | = k such that G \ S does not contain any of the graphs in F as a topological minor. We prove that for every such F, F -TM-Deletion is fixed parameter tractable on planar graphs. Our algorithm runs in a 2 O(k 2) · n² time, or, alternatively, in 2 O(k) · n4 time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface. [ABSTRACT FROM AUTHOR]

Hajós conjectured that every graph containing no subdivision of the complete graph K s + 1 is properly s -colorable. This conjecture was disproved by Catlin. Indeed, the maximum chromatic number of such graphs is Ω (s 2 / log ⁡ s). We prove that O (s) colors are enough for a weakening of this conjecture that only requires every monochromatic component to have bounded size (so-called clustered coloring). Our approach leads to more results, many of which only require a much weaker assumption that forbids an 'almost (⩽ 1) -subdivision' (where at most one edge is subdivided more than once). This assumption is best possible, since no bound on the number of colors exists unless we allow at least one edge to be subdivided arbitrarily many times. We prove the following (where s ⩾ 2): 1. Graphs of bounded treewidth and with no almost (⩽ 1) -subdivision of K s + 1 are s -choosable with bounded clustering. 2. For every graph H , graphs with no H -minor and no almost (⩽ 1) -subdivision of K s + 1 are (s + 1) -colorable with bounded clustering. 3. For every graph H of maximum degree at most d , graphs with no H -subdivision and no almost (⩽ 1) -subdivision of K s + 1 are max ⁡ { s + 3 d − 5 , 2 } -colorable with bounded clustering. 4. For every graph H of maximum degree d , graphs with no K s , t subgraph and no H -subdivision are max ⁡ { s + 3 d − 4 , 2 } -colorable with bounded clustering. 5. Graphs with no K s + 1 -subdivision are (4 s − 5) -colorable with bounded clustering. The first result is tight and shows that the clustered analogue of Hajós' conjecture is true for graphs of bounded treewidth. The second result implies an upper bound for the clustered version of Hadwiger's conjecture that is only one color away from the known lower bound, and shows that the number of colors is independent of the forbidden minor. The final result is the first O (s) bound on the clustered chromatic number of graphs with no K s + 1 -subdivision. [ABSTRACT FROM AUTHOR]

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 collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, deciding 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 are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function fF such that F-M-DELETION can be solved in time fF(tw) . nO(1) on n-vertex graphs. We prove that fF(tw) = 2²O(tw.logtw) for every collection F, that fF(tw) = 2O(tw.log tw) if F contains a planar graph, and that fF(tw) = 2O(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic. [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]

The scramble number of a graph provides a lower bound for gonality and an upper bound for treewidth, making it a graph invariant of interest. In this paper we study graphs of scramble number at most two, and give a classification of all such graphs with a finite list of forbidden topological minors. We then prove that there exists no finite list of forbidden topological minors to characterize graphs with scramble number at most k for any fixed k ≥ 3. [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]

We prove that every graph of minimum degree at least r and girth at least 27 contains a subdivision of Kr+1. This implies that the conjecture of Hajós, that every graph of chromatic number at least r contains a subdivision of Kr, is true for graphs of girth at least 27. This conjecture is known to be false in general. [ABSTRACT FROM AUTHOR]

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]