All Outputs (5)

Kempe equivalence of colourings of cubic graphs (2016)
Journal Article
Feghali, C., Johnson, M., & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics, 59, 1-10. https://doi.org/10.1016/j.ejc.2016.06.008

Given a graph G=(V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by ex... Read More about Kempe equivalence of colourings of cubic graphs.

The price of connectivity for cycle transversals (2016)
Journal Article
Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2016). The price of connectivity for cycle transversals. European Journal of Combinatorics, 58, 203-224. https://doi.org/10.1016/j.ejc.2016.06.003

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and View the MathML source be... Read More about The price of connectivity for cycle transversals.

Smart grid-aware scheduling in data centres (2016)
Journal Article
Mäsker, M., Nagel, L., Brinkmann, A., Lotfifar, F., & Johnson, M. (2016). Smart grid-aware scheduling in data centres. Computer Communications, 96, 73-85. https://doi.org/10.1016/j.comcom.2016.04.021

In several countries the expansion and establishment of renewable energies result in widely scattered and often weather-dependent energy production, decoupled from energy demand. Large, fossil-fuelled power plants are gradually replaced by many small... Read More about Smart grid-aware scheduling in data centres.

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs (2016)
Journal Article
Golovach, P., Johnson, M., Paulusma, D., & Song., J. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory, 84(4), 331-363. https://doi.org/10.1002/jgt.22028

For a positive integer k, a k-coloring of a graph inline image is a mapping inline image such that inline image whenever inline image. The COLORING problem is to decide, for a given G and k, whether a k-coloring of G exists. If k is fixed (i.e., it i... Read More about A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs.

Filling the complexity gaps for colouring planar and bounded degree graphs (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2016). Filling the complexity gaps for colouring planar and bounded degree graphs. In Z. Lipták, & W. F. Smyth (Eds.), Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers (100-111). https://doi.org/10.1007/978-3-319-29516-9_9

We consider a natural restriction of the List Colouring problem, k-Regular List Colouring, which corresponds to the List Colouring problem where every list has size exactly k. We give a complete classification of the complexity of k-Regular List Colo... Read More about Filling the complexity gaps for colouring planar and bounded degree graphs.