**Increasing the Minimum Degree of a Graph by Contractions**
(2011)

Presentation / Conference Contribution

Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2011, September). Increasing the Minimum Degree of a Graph by Contractions. Presented at IPEC 2011: Parameterized and Exact Computation, Saarbrücken, Germany

# All Outputs (17)

On the diameter of reconfiguration graphs for vertex colourings(2011)

Presentation / Conference Contribution

Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2011). On the diameter of reconfiguration graphs for vertex colourings. Electronic Notes in Discrete Mathematics, 38(1), 161-166. https://doi.org/10.1016/j.endm.2011.09.028The reconfiguration graph of the k-colourings of a graph G contains as its vertex set the proper vertex k-colourings of G, and two colourings are joined by an edge in the reconfiguration graph if they differ in colour on just one vertex of G. We prov... Read More about On the diameter of reconfiguration graphs for vertex colourings.

Lift Contractions(2011)

Presentation / Conference Contribution

Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Lift Contractions. Electronic Notes in Discrete Mathematics, 38(1), 407-412. https://doi.org/10.1016/j.endm.2011.09.066We introduce and study a new containment relation in graphs – lift contractions. H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. We show that a graph contains every n-vertex graph as a lift... Read More about Lift Contractions.

On partitioning a graph into two connected subgraphs(2011)

Journal Article

Paulusma, D., & Rooij van, J. (2011). On partitioning a graph into two connected subgraphs. Theoretical Computer Science, 412(48), 6761-6769. https://doi.org/10.1016/j.tcs.2011.09.001Suppose a graph G is given with two vertex-disjoint sets of vertices Z1 and Z2. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z1 and Z2, respectively? This problem is known... Read More about On partitioning a graph into two connected subgraphs.

Parameterizing cut sets in a graph by the number of their components(2011)

Journal Article

Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). Parameterizing cut sets in a graph by the number of their components. Theoretical Computer Science, 412(45), 6340-6350. https://doi.org/10.1016/j.tcs.2011.07.005For a connected graph G=(V,E), a subset U⊆V is a disconnected cut if U disconnects G and the subgraph G[U] induced by U is disconnected as well. A cut U is a k-cut if G[U] contains exactly k(≥1) components. More specifically, a k-cut U is a (k,ℓ)-cut... Read More about Parameterizing cut sets in a graph by the number of their components.

Graph labelings derived from models in distributed computing: a complete complexity classification(2011)

Journal Article

Chalopin, J., & Paulusma, D. (2011). Graph labelings derived from models in distributed computing: a complete complexity classification. Networks, 58(3), 207-231. https://doi.org/10.1002/net.20432

Contracting planar graphs to contractions of triangulations(2011)

Journal Article

Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Contracting planar graphs to contractions of triangulations. Journal of discrete algorithms, 9(3), 299-306. https://doi.org/10.1016/j.jda.2011.03.010For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, ther... Read More about Contracting planar graphs to contractions of triangulations.

On disconnected cuts and separators(2011)

Journal Article

Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). On disconnected cuts and separators. Discrete Applied Mathematics, 159(13), 1345-1351. https://doi.org/10.1016/j.dam.2011.04.027For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V∖U)∪{u} is connec... Read More about On disconnected cuts and separators.

On Finding Paths Passing through Specified Vertices(2011)

Report

Paulusma, D. (2011). On Finding Paths Passing through Specified Vertices. [No known commissioning body]We consider undirected finite graphs that have no loops and no multiple edges. A graph is denoted G = (VG, EG), where VG is the set of vertices and EG is the set of edges. A graph containment problem is to decide whether one graph can be modified int... Read More about On Finding Paths Passing through Specified Vertices.

Computing Role Assignments of Proper Interval Graphs in Polynomial Time(2011)

Presentation / Conference Contribution

Heggernes, P., Hof, V. P., & Paulusma, D. (2011, December). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. Presented at 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, LondonA homomorphism from a graph G to a graph R is locally surjective if its restriction to the neighborhood of each vertex of G is surjective. Such a homomorphism is also called an R-role assignment of G. Role assignments have applications in distributed... Read More about Computing Role Assignments of Proper Interval Graphs in Polynomial Time.

Satisfiability of acyclic and almost acyclic CNF formulas (II)(2011)

Presentation / Conference Contribution

Ordyniak, S., Paulusma, D., & Szeider, S. (2011, December). Satisfiability of acyclic and almost acyclic CNF formulas (II). Presented at 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, Ann Arbor, MIIn the first part of this work (FSTTCS’10) we have shown that the satisfiability of CNF formulas with β-acyclic hypergraphs can be decided in polynomial time. In this paper we continue and extend this work. The decision algorithm for β-acyclic formul... Read More about Satisfiability of acyclic and almost acyclic CNF formulas (II).

Contracting a chordal graph to a split graph or a tree(2011)

Presentation / Conference Contribution

Golovach, P. A., Kaminski, M., & Paulusma, D. (2011, December). Contracting a chordal graph to a split graph or a tree. Presented at 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011, Warsaw, PolandThe problems Contractibility and Induced Minor are to test whether a graph G contains a graph H as a contraction or as an induced minor, respectively. We show that these two problems can be solved in |VG|f(|VH|)VGf(VH) time if G is a chordal input gr... Read More about Contracting a chordal graph to a split graph or a tree.

The computational complexity of Disconnected Cut and 2K2-Partition(2011)

Presentation / Conference Contribution

Martin, B., & Paulusma, D. (2011, December). The computational complexity of Disconnected Cut and 2K2-Partition. Presented at Principles and Practice of Constraint Programming, 17th International Conference, CP 2011, Perugia, ItalyFor a connected graph G = (V,E), a subset U ⊆ V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. Thi... Read More about The computational complexity of Disconnected Cut and 2K2-Partition.

List coloring in the absence of a linear forest(2011)

Presentation / Conference Contribution

Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011, December). List coloring in the absence of a linear forest. Presented at 37th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech RepublicThe k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k -Coloring problem requires in addition that every vertex u must receive a color from some g... Read More about List coloring in the absence of a linear forest.

Computing vertex-surjective homomorphisms to partially reflexive trees(2011)

Presentation / Conference Contribution

Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Computing vertex-surjective homomorphisms to partially reflexive trees. Presented at 6th International Computer Science Symposium in Russia, CSR 2011., St Petersburg, Russia

Coloring graphs without short cycles and long induced paths(2011)

Presentation / Conference Contribution

Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Coloring graphs without short cycles and long induced paths. Presented at Fundamentals of Computation Theory, 18th International Symposium, FCT 2011, Oslo, NorwayThe girth of a graph G is the length of a shortest cycle in G. For any fixed girth g ≥ 4 we determine a lower bound ℓ(g) such that every graph with girth at least g and with no induced path on ℓ(g) vertices is 3-colorable. In contrast, we show the ex... Read More about Coloring graphs without short cycles and long induced paths.

Finding contractions and induced minors in chordal graphs via disjoint paths(2011)

Presentation / Conference Contribution

Belmonte, R., Golovach, P. A., Heggernes, P., Hof van 't, P., Kaminski, M., & Paulusma, D. (2011, December). Finding contractions and induced minors in chordal graphs via disjoint paths. Presented at 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, JapanThe k-Disjoint Paths problem, which takes as input a graph G and k pairs of specified vertices (s i ,t i ), asks whether G contains k mutually vertex-disjoint paths P i such that P i connects s i and t i , for i = 1,…,k. We study a natural variant of... Read More about Finding contractions and induced minors in chordal graphs via disjoint paths.