Skip to main content

Research Repository

Advanced Search

All Outputs (85)

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, December). Obtaining online ecological colourings by generalizing first-fit. Presented at 5th International Computer Science Symposium in Russia (CSR 2010), Kazan, Russia

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. (online). 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.

The computational complexity of the parallel knock-out problem (2006)
Presentation / Conference Contribution
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006, March). The computational complexity of the parallel knock-out problem. Presented at 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.