Abstract We consider two variants of orthogonal colouring games on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of $$m\in {\mathbb {N}}$$ m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the partial colourings. In the normal play variant, the first player unable to move loses. In the scoring variant, each player aims to maximise their score, which is the number of coloured vertices in their copy of the graph. We prove that, given an instance with partial colourings, both the normal play and the scoring variant of the game are PSPACE-complete. An involution $$\sigma $$ σ of a graph G is strictly matched if its fixed point set induces a clique and $$v\sigma (v)\in E(G)$$ v σ ( v ) ∈ E ( G ) for any non-fixed point $$v\in V(G)$$ v ∈ V ( G ) . Andres et al. (Theor Comput Sci 795:312–325, 2019) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete.

paint can is an example of a game whose positions are disjunctive sums, and a move in any component reduces that component to a nimber. Conway, in On Numbers and Games, partially analyzed the related game supernim, and called these components “superstars”, mentioning “There does not appear to be a complete theory”. The book contains one result about these games, and, until now, there has been no advance in finding good strategies. Here, we show that, for a human, the use of canonical forms is not a good approach. We present an algorithmic, recursive approach to the general case, based on a fundamental reduction of these positions, as well as on a Nimber Avoidance Theorem. An analysis of the computational time of the algorithm is presented.

For any field ${\bf F}$, the set of all functions $f : V(G) \rightarrow {\bf F}$ whose sum on each maximal independent set is constant forms a vector space over ${\bf F}$. In this paper, we show that the dimension can vary depending on the characteristic of the field. We also investigate the dimensions of these vector spaces and show that while some families, such as chordal graphs, have unbounded dimension, other families, such as nonempty circulant graphs of prime order, have bounded dimension.

Let $\beta (G)$ denote the independence number of a graph G. We introduce $A(G) = \lim_{k \to \infty } \beta (G^k )/| V(G) |^k $, where the categorical graph product is used. This limit, surprisingly, lies in the range $( 0,1/2 ] \cup \{ 1 \}$. We can show that this limit can take any such rational number, but is there any G for which $A(G)$ is irrational? A useful technique for bounding $A(G)$ is to consider special spanning subgraphs. These bounds allow us to efficiently compute $A(G)$ for many G. We give a condition which if true for G shows that $A(G) > \beta (G)/| V(G) |$. This brings up the question; for which G does $A(G) = \beta (G)/| V(G) |$? This happens if G is a Cayley graph of an Abelian group or if G is a connected graph that has an automorphism which has a single orbit.

Abstract In [G. Gunther, Neighbor‐connectivity in regular graphs. Discrete Appl. Math. 11 (1985) 233–243] Gunther introduced the concept of a k neighbor‐connected graph, which has the property that the removal of any k − 1 closed neighborhoods neither disconnects the graph, nor leaves only a complete graph. In this paper we pursue the investigation of minimal graphs that are k‐regular in addition to being k neighbor‐connected. In a private communication, Gunther conjectured that if G is such a graph which contains no cliques of size larger than m, then |V(G)| ≧ k2 + (k + 1 − m) (k − 1) + 1. In the above reference, he proved that this conjecture is valid in the case that m = k and characterized the minimal graphs. In this paper, we begin to investigate the case where m = 2. We give some results connecting the minimal graphs to other combinatorial objects.