Reconfiguring k-colourings of Complete Bipartite Graphs
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let $H$ be a graph, and $k\geq \chi(H)$ an integer. We say that $H$ has a {\em cyclic Gray code of $k$-colourings} if and only ifit is possible to list all its $k$-colourings in such a way thatconsecutive colourings, including the last and the first, agree on allvertices of $H$ except one. The Gray code number of $H$ is the least integer $k_0(H)$such that $H$ has a cyclic Gray code of its $k$-colouringsfor all $k\geq k_0(H)$. For complete bipartite graphs, we prove that$k_0(K_{\ell,r})=3$ when both $\ell$ and $r$ are odd, and$k_0(K_{\ell,r})=4$ otherwise.
Abstract
Let $H$ be a graph, and $k\geq \chi(H)$ an integer. We say that $H$ has a {\em cyclic Gray code of $k$-colourings} if and only ifit is possible to list all its $k$-colourings in such a way thatconsecutive colourings, including the last and the first, agree on allvertices of $H$ except one. The Gray code number of $H$ is the least integer $k_0(H)$such that $H$ has a cyclic Gray code of its $k$-colouringsfor all $k\geq k_0(H)$. For complete bipartite graphs, we prove that$k_0(K_{\ell,r})=3$ when both $\ell$ and $r$ are odd, and$k_0(K_{\ell,r})=4$ otherwise.
참고문헌 (14)
- S. Bard, "Colour graphs of complete multipartite graphs", MSc Thesis, pp.2014
- J. A. Bondy, "Graph Theory, GTM 224" (2008), Springer
- P. Bonsma, "Finding paths between graph colourings: PSPACEcompleteness and superpolynomial distances", Theoretical Computer Science, 410, pp.5215~5226 (2009)
- L. Cereceda, "Connectedness of the graph of vertex colourings", Discrete Math., 308, pp.913~919 (2008)
- L. Cereceda, "Mixing 3-colourings in bipartite graphs", European J. Combin., 30, pp.1593~1606 (2009)
- L. Cereceda, "Finding Paths Between 3-Colorings", J. Graph Theory, 67, pp.69~82 (2011)
- K. Choo, "Gray code numbers for graphs", Math. Contemp, 4, pp.125~139 (2011)
- M. Dyer, "Randomly coloring sparse random graphs with fewer colors than the maximum degree", Random Structures Algorithms, 29, pp.450~465 (2006)
- S. Finbow, "Hamiltonicity of Bell and Stirling Colour Graphs", ~ (2014)
- R. Haas, "The canonical coloring graph of trees and cycles", Ars Math. Contemp., 5, pp.149~157 (2012)
- T. Ito, "Reconfiguration of list L(2, 1)-labelings in a graph", Theoretical Computer Science, 9702 (2014)[DOI]
- M. Jerrum, "A very simple algorithm for estimating the number of k-colorings of a low-degree graph", Random Structures Algorithms, 7, pp.157~165 (1995)
- B. Lucier, "The Glauber dynamics for colorings of bounded degree trees", SIAM J. Disc. Math, 25, pp.827~853 (2011)
- C. Savage, "Montone Gray codes and the middle levels problem", J. Combin. Theory Ser. A, 70, pp.230~248 (1995)