Given a graph \(G\) and nonnegative integer \(k\), a map \(\pi: V(G) \to \{1, \ldots, k\}\) is a perfect \(k\)-colouring if the subgraph induced by each colour class is perfect. The perfect chromatic number of \(G\) is the least \(k\) for which \(G\) has a perfect \(k\)-colouring; such an invariant is a measure of a graph’s imperfection. We study here the theory of perfect colourings. In particular, the existence of perfect \(k\)-chromatic graphs are shown for all \(k\), and we draw attention to the associated extremal problem. We provide extensions to C. Berge’s Strong Perfect Graph Conjecture, and prove the existence of graphs with only one perfect \(k\)-colouring (up to a permutation of colours). The type of approach taken here can be applied to studying any graph property closed under induced subgraphs.

An \(S_{s,t}\) distar-factorization of \(DK_{m}\) is an edge partitioning of the complete symmetric directed graph \(DK_{m}\) into subdigraphs each of which is isomorphic to the distar \(S_{s,t}\) (the distar \(S_{s,t}\) being obtained from the star \(K_{1,s+t}\) by directing \(s\) of the edges into the centre and \(t\) of the edges out of the centre). We consider the question, “When can the arcs of \(DK_{m}\) be partitioned into arc-disjoint subgraphs each isomorphic to \(S_{s,t}\)?” and give necessary and sufficient conditions for \(S_{s,t}\) distar-factorizations of \(DK_{m}\) in the cases when either \(m\equiv 0\) or \(1 \pmod{s+t}\).

Consider a random walk in a plane in which a particle at any stage moves one unit in any one of the four directions, namely, north, south, east, west with equal probability. The problem of finding the distribution of any characteristic of the above random walk when the particle reaches a fixed point \((a, b)\) after \(d\) steps reduces to the counting of lattice paths in a plane in which the path can move one unit in any of the four directions. In this paper, path counting results related to the boundaries \(y-x = k_1\) and \(y+x = k_2\) such as touchings, crossings, etc., are obtained by using either combinatorial or probabilistic methods. Some extensions to higher dimensions are indicated.

For \(v \geq 4\) we determine the largest number \(f(v)\), such that every simple \(3\)-connected graph on \(v\) vertices has \(f(v)\) edge contractions which result in a smaller \(3\)-connected graph. We also characterize those simple \(3\)-connected graphs on \(v\) vertices which have exactly \(f(v)\) such edge contractions.

Several measures of the vulnerability of a graph have been examined previously. These include connectivity, toughness, binding number, and integrity. In this paper the authors examine the toughness and binding number of cycle permutation graphs (sometimes called generalized prisms). In particular, we determine the binding number for any cycle permutation graph and find upper and lower bounds for the toughness of such graphs. A class of cycle permutation graphs where the lower bound is always achieved and a class of cycle permutation graphs (which are also generalized Petersen graphs) where the lower bound is never achieved are also presented.

Following up on the bipartite analogue of an interval graph developed in a previous work, we investigate several possibilities for a bipartite analogue of the concept of a split graph. We also give bipartite analogues of threshold graphs and of perfect graphs.

The problem of recognizing if a configuration theorem is valid in a given class \(\mathcal{C}\) of incidence structures is equivalent to the problem of deciding, for an arbitrary finite incidence structure \(I\), whether \(I\) is embeddable in some incidence structure in \(\mathcal{C}\).

In a \(\lambda\)-design \(D\), the points \(1, 2, \ldots, n\) are divided into two classes with replications \(r_1\) and \(r_2\), respectively. For any \(1 \leq i, j \leq n\), let \(r_{ij}\) be the number of the blocks containing \(i\) and \(j\). It is proven that \(D\) is type-1 if and only if for any \(i, j\) (\(i \neq j\)) in the same class, \(r_{ij}\) depends only on the class.

Given a graph \(G\) and a positive integer \(k\), a graph \(H\) is a \(k\)-Folkman graph for \(G\) if for any map \(\pi: V(H) \to \{1, \ldots, k\}\), there is an induced subgraph of \(H\) isomorphic to \(G\) on which \(\pi\) is constant. J. Folkman ({SIAM J. Appl. Math.} 18 (1970), pp. 19-24) first showed the existence of such graphs. We provide here a new construction of \(k\)-Folkman graphs for bipartite graphs \(G\) via random hypergraphs. In particular, we show that for any fixed positive integer \(k\), any fixed positive real number \(\epsilon\) and any bipartite graph \(G\), there is a \(k\)-Folkman graph for \(G\) of order \(O(|V(G)|^{3+\epsilon})\) without triangles.