Skip to main content

Research Repository

Advanced Search

All Outputs (66)

Kempe equivalence of colourings of cubic graphs (2015)
Presentation / Conference Contribution
Feghali, C., Johnson, M., & Paulusma, D. (2015). Kempe equivalence of colourings of cubic graphs. . https://doi.org/10.1016/j.endm.2015.06.034

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... Read More about Kempe equivalence of colourings of cubic graphs.

Narrowing the complexity gap for colouring (Cs, Pt)-free graphs (2015)
Journal Article
Huang, S., Johnson, M., & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal, 58(11), 3074-3088. https://doi.org/10.1093/comjnl/bxv039

For a positive integer k and graph G=(V,E), a k-colouring of G is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv∈E. The k-Colouring problem is to decide, for a given G, whether a k-colouring of G exists. The k-Precolouring Extension problem... Read More about Narrowing the complexity gap for colouring (Cs, Pt)-free graphs.

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences (2015)
Journal Article
Feghali, C., Johnson, M., & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4), 340-358. https://doi.org/10.1002/jgt.22000

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ-coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper co... Read More about A Reconfigurations Analogue of Brooks' Theorem and Its Consequences.

Knocking out P_k-free graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking out P_k-free graphs.

The price of connectivity for cycle transversals (2015)
Presentation / Conference Contribution
Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2015). The price of connectivity for cycle transversals. In Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II (395-406). https://doi.org/10.1007/978-3-662-48054-0_33

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 ctF(G) be the minimum size... Read More about The price of connectivity for cycle transversals.

A multi-level hypergraph partitioning algorithm using rough set clustering (2015)
Book Chapter
Lotfifar, F., & Johnson, M. (2015). A multi-level hypergraph partitioning algorithm using rough set clustering. In J. Träff, S. Hunold, & F. Versaci (Eds.), Euro-Par 2015 : parallel processing : 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings (159-170). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_13

The hypergraph partitioning problem has many applications in scientific computing and provides a more accurate inter-processor communication model for distributed systems than the equivalent graph problem. In this paper, we propose a sequential multi... Read More about A multi-level hypergraph partitioning algorithm using rough set clustering.

Finding Shortest Paths Between Graph Colourings (2015)
Journal Article
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2), 295-321. https://doi.org/10.1007/s00453-015-0009-7

The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successiv... Read More about Finding Shortest Paths Between Graph Colourings.

Algorithms for diversity and clustering in social networks through dot product graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & van Leeuwen, E. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks, 41, 48-55. https://doi.org/10.1016/j.socnet.2015.01.001

In this paper, we investigate a graph-theoretical model of social networks. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d -dimensional vector View... Read More about Algorithms for diversity and clustering in social networks through dot product graphs.

Smart grid-aware scheduling in data centres (2015)
Presentation / Conference Contribution
Mäsker, M., Nagel, L., Brinkmann, A., Lotfifar, F., & Johnson, M. (2015). Smart grid-aware scheduling in data centres. In 2015 Sustainable Internet and ICT for Sustainability (SustainIT 2015) : Madrid, Spain, April 14-15, 2015 (1-9). https://doi.org/10.1109/sustainit.2015.7101362

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.

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs (2014)
Journal Article
Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27(1), 132-143. https://doi.org/10.1007/s10878-012-9490-y

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if t... Read More about Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.

Finding paths between 3-colorings (2011)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (2011). Finding paths between 3-colorings. Journal of Graph Theory, 67(1), 69-82. https://doi.org/10.1002/jgt.20514

Given a 3-colorable graph G together with two proper vertex 3-colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are pro... Read More about Finding paths between 3-colorings.

Obtaining online ecological colourings by generalizing first-fit (2010)
Presentation / Conference Contribution
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010). Obtaining online ecological colourings by generalizing first-fit. . https://doi.org/10.1007/978-3-642-13182-0_22

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vert... Read More about Obtaining online ecological colourings by generalizing first-fit.

Mixing 3-colourings in bipartite graphs (2009)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (2009). Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics, 30(7), 1593-1606. https://doi.org/10.1016/j.ejc.2009.03.011

For a 3-colourable graph G, the 3-colour graph of G, denoted C_3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the fol... Read More about Mixing 3-colourings in bipartite graphs.

Upper bounds and algorithms for parallel knock-out numbers (2009)
Journal Article
Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the... Read More about Upper bounds and algorithms for parallel knock-out numbers.

Connectedness of the graph of vertex-colourings (2008)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (2008). Connectedness of the graph of vertex-colourings. Discrete Mathematics, 308(5-6), 913-919. https://doi.org/10.1016/j.disc.2007.07.028

For a positive integer k and a graph G, the k-colour graph of G , Ck(G), is the graph that has the proper k-vertex-colourings of G as its vertex set, and two k -colourings are joined by an edge in Ck(G) if they differ in colour on just one vertex of... Read More about Connectedness of the graph of vertex-colourings.

Transversals of subtree hypergraphs and the source location problem in digraphs (2008)
Journal Article
Heuvel van den, J., & Johnson, M. (2008). Transversals of subtree hypergraphs and the source location problem in digraphs. Networks, 51(2), 113-119. https://doi.org/10.1002/net.20206

A hypergraph H = (V,E) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T. Since the number of edges of a subtree hypergraph can be exponential in n = |V|, one can not always expect to be able to fi... Read More about Transversals of subtree hypergraphs and the source location problem in digraphs.

Mixing 3-colourings in bipartite graphs (2007)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (2007). Mixing 3-colourings in bipartite graphs. Lecture Notes in Computer Science, 166-177. https://doi.org/10.1007/978-3-540-74839-7_17

For a 3-colourable graph G, the 3-colour graph of G, denoted C3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the foll... Read More about Mixing 3-colourings in bipartite graphs.

Finding Paths between Graph Colourings: Computational Complexity and Possible Distances (2007)
Journal Article
Bonsma, P., Cereceda, L., van den Heuvel, J., & Johnson, M. (2007). Finding Paths between Graph Colourings: Computational Complexity and Possible Distances. Electronic Notes in Discrete Mathematics, 29, 463-469. https://doi.org/10.1016/j.endm.2007.07.073

Suppose we are given a graph G together with two proper vertex k-colourings of G, α and β. How easily can we decide whether it is possible to transform α into β by recolouring vertices of G one at a time, making sure we always have a proper k-colouri... Read More about Finding Paths between Graph Colourings: Computational Complexity and Possible Distances.

Amalgamations of factorizations of complete graphs (2007)
Journal Article
Johnson, M. (2007). Amalgamations of factorizations of complete graphs. Journal of Combinatorial Theory, Series B, 97(4), 597-611. https://doi.org/10.1016/j.jctb.2006.09.004

Let t be a positive integer, and let K=(k1,…,kt) and L=(l1,…,lt) be collections of nonnegative integers. A (t,K,L)-factorization of a graph is a decomposition of the graph into factors F1,…,Ft such that Fi is ki-regular and li-edge-connected. In this... Read More about Amalgamations of factorizations of complete graphs.