Outputs (6)

Hereditary graph classes: when the complexities of coloring and clique cover coincide (2018)
Journal Article
Blanché, A., Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory, 91(3), 267-289. https://doi.org/10.1002/jgt.22431

graph is (H1;H2)-free for a pair of graphs H1;H2 if it contains no induced subgraph isomorphic to H1 or H2. In 2001, Král’, Kratochvíl, Tuza, and Woeginger initiated a study into the complexity of Colouring for (H1;H2)-free graphs. Since then, others... Read More about Hereditary graph classes: when the complexities of coloring and clique cover coincide.

Computing small pivot-minors (2018)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., Jeong, J., Kanté, M. M., Kwon, O., Oum, S., & Paulusma, D. (2018, June). Computing small pivot-minors. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany

A graph G contains a graph H as a pivot-minor if H can be obtained from G by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. However, so far, pivot-minors have only been studied... Read More about Computing small pivot-minors.

On the (Parameterized) Complexity of Recognizing Well-covered ( r , ℓ )-graph (2018)
Journal Article
Alves, S. R., Dabrowski, K. K., Faria, L., Klein, S., Sau, I., & Souza, U. S. (2018). On the (Parameterized) Complexity of Recognizing Well-covered ( r , ℓ )-graph. Theoretical Computer Science, 746, 36-48. https://doi.org/10.1016/j.tcs.2018.06.024

An (r,ℓ)(r,ℓ)-partition of a graph G is a partition of its vertex set into r independent sets and ℓ cliques. A graph is (r,ℓ)(r,ℓ) if it admits an (r,ℓ)(r,ℓ)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph... Read More about On the (Parameterized) Complexity of Recognizing Well-covered ( r , ℓ )-graph.

Independent Feedback Vertex Set for P5-free Graphs (2018)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica, 81(4), 1416-1449. https://doi.org/10.1007/s00453-018-0474-x

The NP-complete problem Feedback Vertex Set is that of deciding whether or not 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... Read More about Independent Feedback Vertex Set for P5-free Graphs.

On colouring (2P2,H)-free and (P5,H)-free graphs (2018)
Journal Article
Dabrowski, K., & Paulusma, D. (2018). On colouring (2P2,H)-free and (P5,H)-free graphs. Information Processing Letters, 134, 35-41. https://doi.org/10.1016/j.ipl.2018.02.003

The Colouring problem asks whether the vertices of a graph can be coloured with at most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour. A graph is (H1,H2)-free if it has no induced subgraph isomorp... Read More about On colouring (2P2,H)-free and (P5,H)-free graphs.

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal (2018)
Presentation / Conference Contribution
Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018, August). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. Presented at 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK

Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if w... Read More about On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.