All Outputs (20)

Editing to a Planar Graph of Given Degrees (2016)
Journal Article
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2016). Editing to a Planar Graph of Given Degrees. Journal of Computer and System Sciences, 85, 168-182. https://doi.org/10.1016/j.jcss.2016.11.009

We consider the following graph modification problem. Let the input consist of a graph G=(V,E), a weight function w:V∪E→N, a cost function c:V∪E→N0 and a degree function δ:V→N0, together with three integers kv,ke and C . The question is whether we ca... Read More about Editing to a Planar Graph of Given Degrees.

Squares of low clique number (2016)
Presentation / Conference Contribution
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. Squares of low clique number. Presented at 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16), Gargnano, Italy

The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number... Read More about Squares of low clique number.

The price of connectivity for feedback vertex set (2016)
Journal Article
Belmonte, R., van ’t Hof, P., Kamiński, M., & Paulusma, D. (2017). The price of connectivity for feedback vertex set. Discrete Applied Mathematics, 217(Part B), 132-143. https://doi.org/10.1016/j.dam.2016.08.011

Let View the MathML source and View the MathML source denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. The price of connectivity for feedback vertex set (poc-fvs) for a... Read More about The price of connectivity for feedback vertex set.

Reducing the clique and chromatic number via edge contractions and vertex deletions (2016)
Presentation / Conference Contribution
Paulusma, D., Picouleau, C., & Ries, B. (2016, May). Reducing the clique and chromatic number via edge contractions and vertex deletions. Presented at 4th International Symposium on Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the c... Read More about Reducing the clique and chromatic number via edge contractions and vertex deletions.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016, August). Well-quasi-ordering versus clique-width: new results on bigenic classes. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland

Daligault, Rao and Thomassé conjectured that if a hereditary class of graphs is well-quasi-ordered by the induced subgraph relation then it has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this conjecture is not true for infi... Read More about Well-quasi-ordering versus clique-width: new results on bigenic classes.

Finding cactus roots in polynomial time (2016)
Presentation / Conference Contribution
Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016, August). Finding cactus roots in polynomial time. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland

A cactus is a connected graph in which each edge belongs to at most one cycle. A graph H is a cactus root of a graph G if H is a cactus and G can be obtained from H by adding an edge between any two vertices in H that are of distance 2 in H. We show... Read More about Finding cactus roots in polynomial time.

Minimal Disconnected Cuts in Planar Graphs (2016)
Journal Article
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks, 68(4), 250-259. https://doi.org/10.1002/net.21696

The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity was not known for planar grap... Read More about Minimal Disconnected Cuts in Planar Graphs.

The stable fixtures problem with payments (2016)
Presentation / Conference Contribution
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2015, June). The stable fixtures problem with payments. Presented at 41 International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany

We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph G=(N,E)G=(N,E), with an integer vertex capacity function b and an edge weighting w. The set N consists of a number of players that... Read More about The stable fixtures problem with payments.

Open problems on graph coloring for special graph classes (2016)
Presentation / Conference Contribution
Paulusma, D. (2015, June). Open problems on graph coloring for special graph classes. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c:V→{1,2,…}c:V→{1,2,…} such that c(u)≠c(v)c(u)≠c(v) for every edge uv∈Euv∈E. We survey known results... Read More about Open problems on graph coloring for special graph classes.

Using contracted solution graphs for solving reconfiguration problems (2016)
Presentation / Conference Contribution
Bonsma, P., & Paulusma, D. (2016, August). Using contracted solution graphs for solving reconfiguration problems. Presented at 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Krakow, Poland

We introduce a dynamic programming method for solving reconfiguration problems, based on contracted solution graphs, which are obtained from solution graphs by performing an appropriate series of edge contractions that decrease the graph size without... Read More about Using contracted solution graphs for solving reconfiguration problems.

Kempe equivalence of colourings of cubic graphs (2016)
Journal Article
Feghali, C., Johnson, M., & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics, 59, 1-10. https://doi.org/10.1016/j.ejc.2016.06.008

Given a graph G=(V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by ex... Read More about Kempe equivalence of colourings of cubic graphs.

Bounding clique-width via perfect graphs (2016)
Journal Article
Dabrowski, K., Huang, S., & Paulusma, D. (2019). Bounding clique-width via perfect graphs. Journal of Computer and System Sciences, 104, 202-215. https://doi.org/10.1016/j.jcss.2016.06.007

We continue the study into the clique-width of graph classes defined by two forbidden induced graphs. We present three new classes of bounded clique-width and one of unbounded clique-width. The four new graph classes have in common that one of their... Read More about Bounding clique-width via perfect graphs.

The price of connectivity for cycle transversals (2016)
Journal Article
Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2016). The price of connectivity for cycle transversals. European Journal of Combinatorics, 58, 203-224. https://doi.org/10.1016/j.ejc.2016.06.003

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and View the MathML source be... Read More about The price of connectivity for cycle transversals.

A linear kernel for finding square roots of almost planar graphs (2016)
Presentation / Conference Contribution
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016, June). A linear kernel for finding square roots of almost planar graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. W... Read More about A linear kernel for finding square roots of almost planar graphs.

Colouring diamond-free graphs (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., & Paulusma, D. (2016, June). Colouring diamond-free graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof i... Read More about Colouring diamond-free graphs.

Induced disjoint paths in circular-arc graphs in linear time (2016)
Journal Article
Golovach, P., Paulusma, D., & van Leeuwen, E. (2016). Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science, 640, 70-83. https://doi.org/10.1016/j.tcs.2016.06.003

The Induced Disjoint Paths problem is to test whether an graph G on n vertices with k distinct pairs of vertices (si,ti) contains paths P1,…,Pk such that Pi connects si and ti for i=1,…,k, and Pi and Pj have neither common vertices nor adjacent verti... Read More about Induced disjoint paths in circular-arc graphs in linear time.

Clique-width of graph classes defined by two forbidden induced subgraphs (2016)
Journal Article
Dabrowski, K. K., & Paulusma, D. (2016). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 59(5), 650-666. https://doi.org/10.1093/comjnl/bxv096

The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs H1 and H2. Prior to our... Read More about Clique-width of graph classes defined by two forbidden induced subgraphs.

Bounding the clique-width of H-free split graphs (2016)
Journal Article
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2016). Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics, 211, 30-39. https://doi.org/10.1016/j.dam.2016.04.003

A graph is H-free if it has no induced subgraph isomorphic to H. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of H-free split graphs whose clique-width is bounded. Our main res... Read More about Bounding the clique-width of H-free split graphs.

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs (2016)
Journal Article
Golovach, P., Johnson, M., Paulusma, D., & Song., J. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory, 84(4), 331-363. https://doi.org/10.1002/jgt.22028

For a positive integer k, a k-coloring of a graph inline image is a mapping inline image such that inline image whenever inline image. The COLORING problem is to decide, for a given G and k, whether a k-coloring of G exists. If k is fixed (i.e., it i... Read More about A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs.

Filling the complexity gaps for colouring planar and bounded degree graphs (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2015, October). Filling the complexity gaps for colouring planar and bounded degree graphs. Presented at 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Verona, Italy

We consider a natural restriction of the List Colouring problem, k-Regular List Colouring, which corresponds to the List Colouring problem where every list has size exactly k. We give a complete classification of the complexity of k-Regular List Colo... Read More about Filling the complexity gaps for colouring planar and bounded degree graphs.