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.

A Latin square \((S, \cdot)\) is said to be \((3, 1, 2)\)-\({conjugate-orthogonal}\) if \(x \cdot y = z \cdot w\), \(x \cdot_{312} y = z \cdot_{312} w\) imply \(x = z\) and \(y = w\), for all \(x, y, z, w \in S\), where \(x_3 \cdot_{312} x_1 = x_2\) if and only if \(x_1 \cdot x_2 = x_3\).Such a Latin square is said to be \({holy}\) \(((3,1,2)\)-HCOLS for short) if it has disjoint and spanning holes corresponding to missing sub-Latin squares.Let \((3,1,2)\)-HCOLS\((h^n)\) denote a \((3,1,2)\)-HCOLS of order \(hn\) with \(n\) holes of equal size \(h\).We show that, for any \(h \geq 1\), a \((3,1,2)\)-HCOLS\((h^n)\) exists if and only if \(n \geq 4\), except \((n,h) = (6,1)\), and except possibly \((n,h) = (10,1)\) and \((4,2t+1)\) for \(t \geq 1\).Let \((3,1,2)\)-ICOILS\((v,k)\) denote an idempotent \((3,1,2)\)-COLS of order \(v\) with a hole of size \(k\).We prove that a \((3,1,2)\)-ICOILS\((v,k)\) exists for all \(v \geq 3k+1\) and \(1 \leq k \leq 5\), except possibly \(k = 4\) and \(v \in \{35, 38\}\).

The main object of this paper is the construction of BIBD’s with \(6 \leq k \leq 11\) and \(\lambda = 1\). These balanced incomplete block designs can be simply constructed from some associated group divisible designs with the number of groups being a prime power, and it is these group divisible designs that are constructed directly. Other related designs are discussed.

We have carried out a large number of computer searches for the base sequences \(BS(n + 1, n)\) as well as for three important subsets known as Turyn sequences, normal sequences, and near-normal sequences. In the Appendix, we give an extensive list of \(BS(n + 1, n)\) for \(n \leq 32\). The existence question for Turyn sequences in \(BS(n + 1, n)\) was resolved previously for all \(n \leq 41\), and we extend this bound to \(n \leq 51\). We also show that the sets \(BS(n + 1, n)\) do not contain any normal sequences if \(n = 27\) or \(n = 28\). To each set \(BS(n + 1, n)\), we associate a finite graph \(\Gamma_{n}\), and determine these graphs completely for \(n \leq 27\). We show that \(BS(m,n) = \emptyset \quad \text{if} \quad m \geq 2n, \; n > 1, \; \text{and} \; m + n \; \text{is odd}\),
and we also investigate the borderline case \(m = 2n – 1\).