All Outputs (19)

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. (2016). Squares of low clique number. Electronic Notes in Discrete Mathematics, 55, 195-198. https://doi.org/10.1016/j.endm.2016.10.048

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). Reducing the clique and chromatic number via edge contractions and vertex deletions. In R. Cerulli, S. Fujishige, & A. R. Mahjoub (Eds.), Combinatorial optimization : 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016. Revised selected papers (38-49). https://doi.org/10.1007/978-3-319-45587-7_4

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.

Finding cactus roots in polynomial time (2016)
Presentation / Conference Contribution
Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016). Finding cactus roots in polynomial time. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (361-372). https://doi.org/10.1007/978-3-319-44543-4_28

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.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016). Well-quasi-ordering versus clique-width: new results on bigenic classes. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (253-265). https://doi.org/10.1007/978-3-319-44543-4_20

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.

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.

Open problems on graph coloring for special graph classes (2016)
Presentation / Conference Contribution
Paulusma, D. (2016). Open problems on graph coloring for special graph classes. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (16-30). https://doi.org/10.1007/978-3-662-53174-7_2

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.

The stable fixtures problem with payments (2016)
Presentation / Conference Contribution
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2016). The stable fixtures problem with payments. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (49-63). https://doi.org/10.1007/978-3-662-53174-7_4

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.

Using contracted solution graphs for solving reconfiguration problems (2016)
Presentation / Conference Contribution
Bonsma, P., & Paulusma, D. (2016). Using contracted solution graphs for solving reconfiguration problems. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22–26, 2016, Kraków, Poland. https://doi.org/10.4230/lipics.mfcs.2016.20

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.

Colouring diamond-free graphs (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., & Paulusma, D. (2016). Colouring diamond-free graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). https://doi.org/10.4230/lipics.swat.2016.16

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.

A linear kernel for finding square roots of almost planar graphs (2016)
Presentation / Conference Contribution
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016). A linear kernel for finding square roots of almost planar graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). https://doi.org/10.4230/lipics.swat.2016.4

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.

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.

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. (2016). Filling the complexity gaps for colouring planar and bounded degree graphs. In Z. Lipták, & W. F. Smyth (Eds.), Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers (100-111). https://doi.org/10.1007/978-3-319-29516-9_9

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.