Skip to main content

Research Repository

Advanced Search

All Outputs (17)

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

Lift Contractions (2011)
Presentation / Conference Contribution
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. Lift Contractions

We 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 the diameter of reconfiguration graphs for vertex colourings (2011)
Presentation / Conference Contribution
Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. On the diameter of reconfiguration graphs for vertex colourings

The 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.

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.001

Suppose 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.005

For 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.

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.010

For 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.027

For 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.

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, Japan

The 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.

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, Norway

The 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.

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

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 Republic

The 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.

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, Italy

For 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.

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, Poland

The 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.

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, MI

In 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).

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, London

A 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.