Outputs (52)

Bounding the clique-width of H-free split graphs (2015)
Conference Proceeding
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.

Clique-width of graph classes defined by two forbidden induced subgraphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 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 Chordal Graphs (2015)
Conference Proceeding
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015). Bounding the Clique-Width of H-free Chordal Graphs. In Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II (139-150). https://doi.org/10.1007/978-3-662-48054-0_12

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)
Conference Proceeding
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2015). Editing to a planar graph of given degrees. In Computer science - theory and applications : 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, proceedings (143-156). https://doi.org/10.1007/978-3-319-20297-6_10

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)
Conference Proceeding
Dabrowski, K. K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. In V. T. Paschos, & P. Widmayer (Eds.), Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings (167-181). https://doi.org/10.1007/978-3-319-18173-8_12

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)
Conference Proceeding
Dabrowski, K. K., Huang, S., & Paulusma, D. (2015). Bounding clique-width via perfect graphs. In A. Dediu, E. Formenti, C. Martín-Vide, & B. Truthe (Eds.), Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015 ; proceedings (676-688). https://doi.org/10.1007/978-3-319-15579-1_53

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)
Conference Proceeding
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.