Reconfiguring vertex colourings of 2-trees

Michael Cavers ; Karen Seyffarth

Ars Mathematica Contemporanea, Tome 17 (2019) no. 2, pp. 653-698.

Résumé

Let H be a graph and let k ≥ χ(H) be an integer. The k-colouring graph of H, denoted Gk(H), is the graph whose vertex set consists of all proper k-vertex-colourings (or simply k-colourings) of H using colours {1, 2, …, k}; two vertices of Gk(H) are adjacent if and only if the corresponding k-colourings differ in colour on exactly one vertex of H. If Gk(H) has a Hamilton cycle, then H is said to have a Gray code of k-colourings, and the Gray code number of H is the least integer k0(H) such that Gk(H) has a Gray code of k-colourings for all k ≥ k0(H). Choo and MacGillivray determine the Gray code numbers of trees. We extend this result to 2-trees. A 2-tree is constructed recursively by starting with a complete graph on three vertices and connecting each new vertex to an existing clique on two vertices. We prove that if H is a 2-tree, then k0(H) = 4 unless H is isomorphic to the join of a tree T and a vertex u, where T is a star on at least three vertices, or the bipartition of T has two even parts; in these cases, k0(H) = 5.

Détail

DOI : 10.26493/1855-3974.1813.7ae

Keywords: 2-trees, graph colouring, Gray codes, Hamilton cycles, reconfiguration problems