We propose a definition of generalized Cops and Robbers games where there are two players, the Pursuer and the Evader, who each move via prescribed rules. If the Pursuer can ensure that the game enters into a fixed set of final positions, then the Pursuer wins; otherwise, the Evader wins. A relational characterization of the games where the Pursuer wins is provided. A precise formula is given for the length of the game, along with an algorithm for computing if the Pursuer has a winning strategy whose complexity is a function of the parameters of the game. For games where the position of one player does not affect the available moves of he other, a vertex elimination ordering characterization, analogous to a cop-win ordering, is given for when the Pursuer has a winning strategy.

A k-colouring of a graph G with colours $1,2,\dots ,k$ is canonical with respect to an ordering $\pi =v_1,v_2,\dots ,v_n$ of the vertices of G if adjacent vertices are assigned different colours and, for $1\le c\le k$ , whenever colour c is assigned to a vertex $v_i$ , each colour less than c has been assigned to a vertex that precedes $v_i$ in $\pi$ . The canonical k-colouring graph of G with respect to π is the graph ${\mathrm{Can}}_k^{\pi }\left(G\right)$ with vertex set equal to the set of canonical k-colourings of G with respect to $\pi$ , with two of these being adjacent if and only if they differ in the colour assigned to exactly one vertex. Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs is studied. It is shown that for complete multipartite graphs, and bipartite graphs there exists a vertex ordering $\pi$ such that ${\mathrm{Can}}_k^{\pi }\left(G\right)$ is connected for large enough values of k. It is proved that a canonical colouring graph of a complete multipartite graph usually does not have a Hamilton cycle, and that there exists a vertex ordering $\pi$ such that ${\mathrm{Can}}_k^{\pi }\left(K_{m,n}\right)$ has a Hamilton path for all $k\ge 3$ . The paper concludes with a detailed consideration of ${\mathrm{Can}}_k^{\pi }\left(K_{2,2,\dots ,2}\right)$ . For each $k\ge \chi$ and all vertex orderings $\pi$ , it is proved that ${\mathrm{Can}}_k^{\pi }\left(K_{2,2,\dots ,2}\right)$ is either disconnected or isomorphic to a particular tree.

Maximum boundary independent broadcasts in graphs and trees