### Reconfiguring vertex colourings of 2-trees

#### Abstract

Let *H* be a graph and let *k* ≥ χ(*H*) be an integer. The * k-colouring graph of H*, denoted

*G*

_{k}(

*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

*G*

_{k}(

*H*) are adjacent if and only if the corresponding

*k*-colourings differ in colour on exactly one vertex of

*H*. If

*G*

_{k}(

*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

*k*

_{0}(

*H*) such that

*G*

_{k}(

*H*) has a Gray code of

*k*-colourings for all

*k*≥

*k*

_{0}(

*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

*k*

_{0}(

*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,

*k*

_{0}(

*H*) = 5.

#### Keywords

DOI: https://doi.org/10.26493/1855-3974.1813.7ae

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications