Outputs (3)

Mixing 3-colourings in bipartite graphs (2007)
Presentation / Conference Contribution
Cereceda, L., van den Heuvel, J., & Johnson, M. (2007, June). Mixing 3-colourings in bipartite graphs. Presented at International Workshop on Graph-Theoretic Concepts in Computer Science, Dornburg, Germany

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.