In this paper, we employ the structures of a permutation graph as exhibited in the Euclidean representation to solve the existence and construction problems of Hamiltonian cycles on permutation graphs. We define and prove the existence of a layered Hamiltonian cycle in a Hamiltonian permutation graph. A linear (in size) time and (in order) space algorithm for construction of a layered Hamiltonian cycle on a permutation graph is presented and its
correctness proven.

Cyclotomy can be used to construct a variety of combinatorial designs, for example, supplementary difference sets, weighing matrices, and \(T\)-matrices. These designs may be obtained by using linear combinations of the incidence matrices of the cyclotomic cosets. However, cyclotomy only works in the prime and prime power cases. We present a generalisation of cyclotomy and introduce generalised cosets. Combinatorial designs can now be obtained by a search through all linear combinations of the incidence matrices of the generalised cosets. We believe that this search method is new. The generalisation works for all cases and is not restricted to prime powers. The paper presents some new combinatorial designs. We give a new construction for \(T\)-matrices of order \(87\) and hence an \({OD}(4 \times 87; 87, 87, 87, 87)\). We also give some \(D\)-optimal designs of order \(n = 2v = 2 \times 145, 2 \times 157, 2 \times 181\).

With the help of computer algorithms, we improve the upper bound on the classical three-color Ramsey number \(R(3,3,4)\), and thus we show that the exact value of this number is \(30\) or \(31\).We also present computer enumeration of all \(3\)-colorings of edges on at least \(14\) vertices without monochromatic triangles.

Conjecture 119 in the file “Written on the Wall”, which contains the output of the computer program “Graffiti” of Fajtlowicz, states: If \(G\) has girth \(5\) then its chromatic number is not more than the maximum frequency of occurrence of a degree in \(G\). Our main result provides an affirmative solution to this conjecture if \(|G| = n\) is sufficiently large. We prove:
Theorem. Let \(k \geq 2\) be a positive integer and let \(G\) be a \(C_{2k}\)-free graph (containing no cycle of length \(2k\)).

1. There exists a constant \(c(k)\), depending only on \(k\),
   such that \(\chi(G) \leq c(k)^{k-1} \sqrt{f(G)}/\log |G|\),
   where \(f(G)\) is the frequency of the mode of the degree sequence of \(G\).
2. There exists a constant \(c(k)\), depending only on \(k\),
   such that \(\chi(G) \leq c(k)|G|^{1/k}/\log |G|\).
3. If girth \((G) \geq 5\) then \(\chi(G) \leq f(G)\) if \(|G| \geq e^{49}\).

In this paper, we derive some inequalities on the existence of two-symbol balanced arrays (B-arrays) of strength five. We then apply these inequalities to obtain an upper bound on the number of constraints for these arrays, and provide an illustrative example.

A graph \(G\) is well-covered if every maximum independent set of vertices of \(G\) has the same cardinality. A graph \(G_1\) is an almost well-covered graph if it is not well-covered, but \(G_1 \setminus \{v\}\) is well-covered, \(\forall v \in V(G_1)\). Similarly, a graph \(H\) is a parity graph if every maximal independent set of vertices of \(H\) has the same parity, and a graph \(H_1\) is an almost parity graph if \(H_1\) is not a parity graph but \(H_1 \setminus \{h\}\) is a parity graph, \(\forall h \in V(H_1)\). Here, we will give a complete characterization of almost parity graphs. We also prove that claw-free parity graphs must be well-covered.

Let \(\mathcal{G}(p)\) denote the class of simple graphs of order \(p\). For a graph \(G\), the complement of \(G\) is denoted by \(\overline{G}\). For a positive integer \(n\), the \(n\)-path-chromatic number \(\chi_n(G)\) is the least number of colours that can be associated to the vertices of \(G\) such that not all the vertices on any path of length \(n\) receive the same colour. The Nordhaus-Gaddum Problem for the \(n\)-path-chromatic number of \(G\) is to find bounds for \(\chi_n(G) + \chi_n(\overline{G})\) and \(\chi_n(G) \cdot \chi_n(\overline{G})\) over the class \(\mathcal{G}(p)\). In this paper, we determine sharp lower bounds for the sum and the product of \(\chi_n(G)\) and \(\chi_n(\overline{G})\). Furthermore, we provide weak upper bounds for \(\chi_2(G) + \chi_2(\overline{G})\) and \(\chi_2(G) \cdot \chi_2(\overline{G})\).

In this paper, we prove that the Equitable \(\Delta\)-Coloring Conjecture holds for planar graphs with maximum degree \(\Delta \geq 13\).

An array \(A[i, j]\), \(1 \leq i \leq n, 1 \leq j \leq n\), has a period \(A[p,p]\) of dimension \(p \times p\) if \(A[i, j] = A[i+p, j+p]\) for \(i, j = 1 \ldots n-p\). The period of \(A_{p,p}\) is the shortest such \(p\).We study two-dimensional pattern matching, and several other related problems, all of which depend on finding the period of an array.In summary, finding the period of an array in parallel using \(p\) processors for general alphabets has the following bounds:
\[
\begin{cases}
\Theta\left(\frac{n^2}{p}\right) & \text{if } p \leq \frac{n^2}{\log \log n}, n>17^3 \quad\quad\quad\quad\quad\quad\quad\quad(1.1) \\
\Theta(\log\log n) & \text{if } \frac{n^2}{\log \log n} < p 17^3 \quad\;\; \quad\quad\quad\quad (1.2) \\
\Theta\left(\log\log_{\frac{2p}{n^2}}{p}\right) & \text{if } n^2 \leq p 17^3 \quad \quad\quad\quad\quad (1.3) \\
\Theta\left(\log\log_{\frac{2p}{n^2}}{p}\right) & \text{if } n^2 \log^2 n \leq p \leq n^4, \text{ $n$ large enough} \quad (1.4)
\end{cases}
\]

In [5] Kløve gave tables of the best bounds known on the size of optimal difference triangle sets. In this note, we give examples of difference triangle sets found by computer search which improve on the upper bounds in [5]. In four cases, these examples are proved to be optimal.