Outputs (10)

Clique-Width for Graph Classes Closed under Complementation (2017)
Presentation / Conference Contribution
Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017, August). Clique-Width for Graph Classes Closed under Complementation. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark

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)
Presentation / Conference Contribution
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017, June). Clique-width and well-quasi ordering of triangle-free graph classes. Presented at WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, Eindhoven, The Netherlands

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)
Presentation / Conference Contribution
Dabrowski, K., & Paulusma, D. Contracting bipartite graphs to paths and cycles. Presented at Eurocomb 2017: European Conference on Combinatorics, Graph Theory and Applications., Vienna, Austria

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.

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.

Recognizing Graphs Close to Bipartite Graphs (2017)
Presentation / Conference Contribution
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017, August). Recognizing Graphs Close to Bipartite Graphs. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark

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.

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)
Presentation / Conference Contribution
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017, December). Independent Feedback Vertex Set for P5-free Graphs. Presented at ISAAC 2017

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.