In a \((k, d)\)-relaxed coloring game, two players, Alice and Bob, take turns coloring the vertices of a graph \(G\) with colors from a set \(C\) of \(k\) colors. A color \(c\) is legal for an uncolored vertex (at a certain step) means that after coloring \(x\) with color \(i\), the subgraph induced by vertices of color \(i\) has maximum degree at most \(d\). Each player can only color a vertex with a legal color. Alice’s goal is to have all the vertices colored, and Bob’s goal is the opposite: to have an uncolored vertex without legal color. The \(d\)-relaxed game chromatic number of a graph \(G\), denoted by \(\chi^{(d)}_g(G)\) is the least number \(k\) so that when playing the \((k,d)\)-relaxed coloring game on \(G\), Alice has a winning strategy. This paper proves that if \(G\) is an outer planar graph, then \(\chi^{(d)}_g(G) \leq 7 – d\) for \(d = 0, 1, 2, 3, 4\).

A graph \(G\) is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let \(X\) be a 2-stratified graph with one fixed blue vertex \(v\) specified. We say that \(X\) is rooted at \(v\). The \(X\)-domination number of a graph \(G\) is the minimum number of red vertices of \(G\) in a red-blue coloring of the vertices of \(G\) such that every blue vertex \(uv\) of \(G\) belongs to a copy of \(X\) rooted at \(v\). In this paper we investigate the \(X\)-domination number of prisms when \(X\) is a 2-stratified 4-cycle rooted at a blue vertex.

The maximum possible volume of a simple, non-Steiner \((v, 3, 2)\) trade was determined for all \(v\) by Khosrovshahi and Torabi (Ars Combinatoria \(51 (1999), 211-223)\); except that in the case \(v \equiv 5\) (mod 6), \(v \geq 23\), they were only able to provide an upper bound on the volume. In this paper we construct trades with volume equal to that bound for all \(v \equiv 5\) (mod 6), thus completing the problem.

For a positive integer \(n\), let \(G\) be \(K_n\) if \(n\) is odd and \(K_n\) less a one-factor if \(n\) is even. In this paper it is shown that, for non-negative integers \(p\), \(q\) and \(r\), there is a decomposition of \(G\) into \(p\) \(4\)-cycles, \(q\) \(6\)-cycles and \(r\) \(8\)-cycles if \(4p + 6q + 8r = |E(G)|\), \(q = 0\) if \(n < 6\), and \(r = 0\) if \(n < 8\).

This paper introduces a bijection between RNA secondary structures and bicoloured ordered trees.

For a given triangle \(T\), consider the problem of finding a finite set \(S\) in the plane such that every two-coloring of \(S\) results in a monochromatic set congruent to the vertices of \(T\). We show that such a set \(S\) must have at least seven points. Furthermore, we show by an example that the minimum of seven is achieved.

The two games considered are mixtures of Searching and Cops and Robber. The cops have partial information, provided first via selected vertices of a graph, and then via selected edges. This partial information includes the robber’s position, but not the direction in which he is moving. The robber has perfect information. In both cases, we give bounds on the amount of such information required by a single cop to guarantee the capture of the robber on a cop-win graph.

Let \(K_v\) be the complete multigraph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-design of \(K_v\), denoted by \(G\)-GD(\(v\)), is a pair of (\(X\), \(\mathcal{B}\)), where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly one block of \(\mathcal{B}\). In this paper, the discussed graphs are sixteen graphs with six vertices and seven edges. We give a unified method for constructing such \(G\)-designs.

Graceful labellings have both a mathematical beauty in their own right and considerable connections with pure and applied combinatorics (edge-decomposition of graphs, coding systems, communication networks, etc.). In the present paper, we exhibit a graceful labelling for each generalized Petersen graph \(P_{8t,3}\) with \(t \geq 1\). As a consequence, we obtain, for any fixed \(t\), a cyclic edge-decomposition of the complete graph \(K_{48t+1}\) into copies of \(P_{8t,3}\). Due to its extreme versatility, the technique employed looks promising for finding new graceful labellings, not necessarily involving generalized Petersen graphs.