Outputs (72)

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.

Erdős–Ko–Rado theorems for a family of trees (2018)
Journal Article
Feghali, C., Johnson, M., & Thomas, D. (2018). Erdős–Ko–Rado theorems for a family of trees. Discrete Applied Mathematics, 236, 464-471. https://doi.org/10.1016/j.dam.2017.10.009

A family of sets is intersecting if any two sets in the family intersect. Given a graph and an integer , let denote the family of independent sets of size of . For a vertex of , let denote the family of independent sets of size that contain . This fa... Read More about Erdős–Ko–Rado theorems for a family of trees.

Surjective H-colouring: New hardness results (2018)
Journal Article
Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring p... Read More about Surjective H-colouring: New hardness results.

Enclosings of decompositions of complete multigraphs in 2-factorizations (2018)
Journal Article
Feghali, C., & Johnson, M. (2018). Enclosings of decompositions of complete multigraphs in 2-factorizations. Journal of Combinatorial Designs, 26(5), 205-218. https://doi.org/10.1002/jcd.21601

Let k, m, n, λ, and μ be positive integers. A decomposition of math formula into edge-disjoint subgraphs math formula is said to be enclosed by a decomposition of math formula into edge-disjoint subgraphs math formula if math formula and, after a sui... Read More about Enclosings of decompositions of complete multigraphs in 2-factorizations.

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.

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.

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.

Surjective H-Colouring: new hardness results (2017)
Presentation / Conference Contribution
Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017, June). Surjective H-Colouring: new hardness results. Presented at Computability in Europe (CiE 2017)., Turku, Finland

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring p... Read More about Surjective H-Colouring: new hardness results.

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.