Updating the complexity status of coloring graphs without a fixed induced linear forest (2012)
Journal Article
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoretical Computer Science, 414(1), 9-19. https://doi.org/10.1016/j.tcs.2011.10.005

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent... Read More about Updating the complexity status of coloring graphs without a fixed induced linear forest.

Computing solutions for matching games (2012)
Journal Article
Biro, P., Kern, W., & Paulusma, D. (2012). Computing solutions for matching games. International Journal of Game Theory, 41(1), 75-90. https://doi.org/10.1007/s00182-011-0273-y

A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting w: E® \mathbb R+w:ER+. The player set is N and the value of a coalition S Í NSN is defined as the maximum weight of a matching in the subgraph induced b... Read More about Computing solutions for matching games.

Containment relations in split graphs (2012)
Journal Article
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Containment relations in split graphs. Discrete Applied Mathematics, 160(1-2), 155-163. https://doi.org/10.1016/j.dam.2011.10.004

A graph containment problem is to decide whether one graph can be modified into some other graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible grap... Read More about Containment relations in split graphs.

Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems (2012)
Journal Article
Bordewich, M., & Semple, C. (2012). Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. Journal of Mathematical Biology, 64(1), 69-85. https://doi.org/10.1007/s00285-011-0405-9

Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species conta... Read More about Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems.