All Outputs (52)

Combinatorics and Algorithms for Augmenting Graphs (2015)
Journal Article
Dabrowski, K. K., Lozin, V. V., de Werra, D., & Zamaraev, V. (2016). Combinatorics and Algorithms for Augmenting Graphs. Graphs and Combinatorics, 32(4), 1339-1352. https://doi.org/10.1007/s00373-015-1660-0

The notion of augmenting graphs generalizes Berge’s idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) prob... Read More about Combinatorics and Algorithms for Augmenting Graphs.

Bounding the clique-width of H-free split graphs (2015)
Presentation / Conference Contribution
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015). Bounding the clique-width of H-free split graphs. . https://doi.org/10.1016/j.endm.2015.06.069

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.

Editing to Eulerian graphs (2015)
Journal Article
Dabrowski, K., Golovach, P., van 't Hof, P., & Paulusma, D. (2016). Editing to Eulerian graphs. Journal of Computer and System Sciences, 82(2), 213-228. https://doi.org/10.1016/j.jcss.2015.10.003

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and dir... Read More about Editing to Eulerian graphs.

Bounding the Clique-Width of H-free Chordal Graphs (2015)
Presentation / Conference Contribution
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015, August). Bounding the Clique-Width of H-free Chordal Graphs. Presented at 40th International Symposium, MFCS 2015, Milan, Italy

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed... Read More about Bounding the Clique-Width of H-free Chordal Graphs.

Classifying the clique-width of H-free bipartite graphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200, 43-51. https://doi.org/10.1016/j.dam.2015.06.030

Let GG be a bipartite graph, and let HH be a bipartite graph with a fixed bipartition (BH,WH)(BH,WH). We consider three different, natural ways of forbidding HH as an induced subgraph in GG. First, GG is HH-free if it does not contain HH as an induce... Read More about Classifying the clique-width of H-free bipartite graphs.

Editing to a planar graph of given degrees (2015)
Presentation / Conference Contribution
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2015, June). Editing to a planar graph of given degrees

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→N and a degree function δ:V→N0, together with three integers kv, ke and C. The question is whether we can... Read More about Editing to a planar graph of given degrees.

Clique-width of graph classes defined by two forbidden induced subgraphs (2015)
Presentation / Conference Contribution
Dabrowski, K. K., & Paulusma, D. (2015, March). Clique-width of graph classes defined by two forbidden induced subgraphs. Presented at 9th International Conference on Algorithms and Complexity (CIAC 2015), Paris, France

If a graph has no induced subgraph isomorphic to any graph in a finite family {H1,…,Hp}, it is said to be (H1,…,Hp)-free. 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 th... Read More about Clique-width of graph classes defined by two forbidden induced subgraphs.

Bounding clique-width via perfect graphs (2015)
Presentation / Conference Contribution
Dabrowski, K. K., Huang, S., & Paulusma, D. (2015, March). Bounding clique-width via perfect graphs. Presented at International Conference on Language and Automata Theory and Applications, Nice, France

Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no subgraph isomorphic to H1 or H2. We continue a recent study into the clique-width of (H1,H2)-free graphs and present three new classes of (H1,H2)-free graphs that have bounded cl... Read More about Bounding clique-width via perfect graphs.

Colouring of graphs with Ramsey-type forbidden subgraphs (2014)
Journal Article
Dabrowski, K., Golovach, P., & Paulusma, D. (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science, 522, 34-43. https://doi.org/10.1016/j.tcs.2013.12.004

A colouring of a graph G=(V,E) is a mapping c:V→{1,2,…} such that c(u)≠c(v) if uv∈E; if |c(V)|⩽k then c is a k -colouring. The Colouring problem is that of testing whether a given graph has a k -colouring for some given integer k . If a graph contain... Read More about Colouring of graphs with Ramsey-type forbidden subgraphs.

Editing to Eulerian Graphs (2014)
Presentation / Conference Contribution
Dabrowski, K. K., Golovach, P. A., Hof, V. P., & Paulusma, D. (2014). Editing to Eulerian Graphs. In V. Raman, & S. P. Suresh (Eds.), 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) (97-108). https://doi.org/10.4230/lipics.fsttcs.2014.97

We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and vertex deletion respectively.... Read More about Editing to Eulerian Graphs.

Classifying the Clique-Width of H-Free Bipartite Graphs (2014)
Presentation / Conference Contribution
Dabrowski, K. K., & Paulusma, D. (2014, December). Classifying the Clique-Width of H-Free Bipartite Graphs. Presented at 20th International Conference, COCOON 2014, Atlanta, GA, USA

Let G be a bipartite graph, and let H be a bipartite graph with a fixed bipartition (B H ,W H ). We consider three different, natural ways of forbidding H as an induced subgraph in G. First, G is H-free if it does not contain H as an induced subgraph... Read More about Classifying the Clique-Width of H-Free Bipartite Graphs.

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs (2013)
Presentation / Conference Contribution
Dabrowski, K. K., Golovach, P. A., & Paulusma, D. (2013, December). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Presented at 39th International Workshop, WG 2013, Lübeck, Germany

A colouring of a graph G = (V;E) is a mapping c : V ! f1; 2; : : :g such that c(u) 6= c(v) if uv 2 E; if jc(V )j k then c is a k-colouring. The Colouring problem is that of testing whether a given graph has a k-colouring for some given integer k. If... Read More about Colouring of Graphs with Ramsey-Type Forbidden Subgraphs.