Outputs (10)

Clique-Width for Graph Classes Closed under Complementation (2017)
Conference Proceeding
Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017). Clique-Width for Graph Classes Closed under Complementation. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.73

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We initiate a systematic study i... Read More about Clique-Width for Graph Classes Closed under Complementation.

Independent feedback vertex sets for graphs of bounded diameter (2017)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131, 26-32. https://doi.org/10.1016/j.ipl.2017.11.004

The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a forest. The set A in such a partition is said to be an independent feedback... Read More about Independent feedback vertex sets for graphs of bounded diameter.

Clique-width and well-quasi ordering of triangle-free graph classes (2017)
Conference Proceeding
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017). Clique-width and well-quasi ordering of triangle-free graph classes. In H. L. Bodlaender, & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers (220-233). https://doi.org/10.1007/978-3-319-68705-6_17

Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (WG 2015) gave a negative answer to this question, but their count... Read More about Clique-width and well-quasi ordering of triangle-free graph classes.

Contracting bipartite graphs to paths and cycles (2017)
Journal Article
Dabrowski, K., & Paulusma, D. (2017). Contracting bipartite graphs to paths and cycles. Electronic Notes in Discrete Mathematics, 61, 309-315. https://doi.org/10.1016/j.endm.2017.06.053

Testing if a given graph G contains the k-vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. The situation changes for the problem of checking if a graph can be modified into Pk by using only edge contractions. I... Read More about Contracting bipartite graphs to paths and cycles.

Contracting Bipartite Graphs to Paths and Cycles (2017)
Journal Article
Dabrowski, K., & Paulusma, D. (2017). Contracting Bipartite Graphs to Paths and Cycles. Information Processing Letters, 127, 37-42. https://doi.org/10.1016/j.ipl.2017.06.013

Testing if a given graph G contains the k -vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. However, the situation changes for the problem of checking if a graph can be modified into Pk by using only edge contr... Read More about Contracting Bipartite Graphs to Paths and Cycles.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2017)
Journal Article
Dabrowski, K., Lozin, V., & Paulusma, D. (2018). Well-quasi-ordering versus clique-width: new results on bigenic classes. Order, 35(2), 253-274. https://doi.org/10.1007/s11083-017-9430-7

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

Recognizing Graphs Close to Bipartite Graphs (2017)
Conference Proceeding
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Recognizing Graphs Close to Bipartite Graphs. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.70

We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-de... Read More about Recognizing Graphs Close to Bipartite Graphs.

Colouring Diamond-free Graphs (2017)
Journal Article
Dabrowski, K., Dross, F., & Paulusma, D. (2017). Colouring Diamond-free Graphs. Journal of Computer and System Sciences, 89, 410-431. https://doi.org/10.1016/j.jcss.2017.06.005

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.

Bounding the Clique-Width of H-free Chordal Graphs (2017)
Journal Article
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2017). Bounding the Clique-Width of H-free Chordal Graphs. Journal of Graph Theory, 86(1), 42-77. https://doi.org/10.1002/jgt.22111

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 claime... Read More about Bounding the Clique-Width of H-free Chordal Graphs.

Independent Feedback Vertex Set for P5-free Graphs (2017)
Conference Proceeding
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Independent Feedback Vertex Set for P5-free Graphs. In Y. Okamoto, & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation (ISAAC 2017) ; proceedings (16:1-16:12). https://doi.org/10.4230/lipics.isaac.2017.16

The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k ≥ 0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independen... Read More about Independent Feedback Vertex Set for P5-free Graphs.