For a \(3\)-vertex coloring, a face of a triangulation whose vertices receive all three colors is called a vivid face with respect to it. In this paper, we show that for any triangulation \(G\) with \(n\) faces, there exists a coloring of \(G\) with at least \( \frac{1}{2}n\) faces and construct an infinite series of plane triangulations such that any \(3\)-coloring admits at most \(\frac{1}{5}(3n- 2)\) vivid faces.

A projective plane is equivalent to a disk with antipodal points identified. A graph is projective planar if it can be drawn on the projective plane with no crossing edges. A linear time algorithm for projective planar embedding has been described by Mohar. We provide a new approach that takes \(O(n^2)\) time but is much easier to implement. We programmed a variant of this algorithm and used it to computationally verify the known list of all the projective plane obstructions.

One application for this work is graph visualization. Projective plane embeddings can be represented on the plane and can provide aesthetically pleasing pictures of some non-planar graphs. More important is that it is highly likely that many problems that are computationally intractable (for example, NP-complete or #P-complete) have polynomial time algorithms when restricted to graphs of fixed orientable or non-orientable genus. Embedding the graph on the surface is likely to be the first step for these algorithms.

We consider the nonexistence of \(e\)-perfect codes in the Johnson scheme \(J(n, w)\). It is proved that for each \(J(2w + 3p, w)\) for \(p\) prime and \(p \neq 2, 5\), \(J(2w + 5p, w)\) for \(p\) prime and \(p \neq 3\), and \(J(2w + p^2, w)\) for \(p\) prime, it does not contain non-trivial \(e\)-perfect codes.

A graph \(G\) is called \(f\)-factor-covered if every edge of \(G\) is contained in some \(f\)-factor. \(G\) is called \(f\)-factor-deleted if \(G\) – \(e\) contains an \(f\)-factor for every edge \(e\). Babler proved that every \(r\)-regular, \((r – 1)\)-edge-connected graph of even order has a \(1\)-factor. In the present article, we prove that every \(2r\)-regular graph of odd order is both \(2m\)-factor-covered and \(2m\)-factor-deleted for all integers \(m\), \(1 \leq m \leq r – 1\), and every \(r\)-regular, \((r – 1)\)-edge-connected graph of even order is both \(m\)-factor-covered and \(m\)-factor-deleted for all integers \(m\), \(1 \leq m \leq \left\lfloor \frac{r}{2} \right\rfloor\).

The convex hull of a subset \(A\) of \(V(G)\), where \(G\) is a connected graph, is defined as the smallest convex set in \(G\) containing \(A\). The hull number of \(G\) is the cardinality of a smallest set \(A\) whose convex hull is \(V(G)\). In this paper, we give the hull number of the composition of two connected graphs.

The basis number \(b(G)\) of a graph \(G\) is defined to be the least integer \(d\) such that \(G\) has a \(d\)-fold basis for its cycle space. In this paper, we investigate the basis number of the direct product of theta graphs and paths.

Large sets of balanced incomplete block (\(BIB\)) designs and resolvable \(BIB\) designs are discussed. Some recursive constructions of such large sets are given. Some existence results, in particular for practical \(k\), are reviewed.

We consider point-line geometries having three points on every line, having three lines through every point (\(bi\)-\(slim\; geometries\)), and containing triangles. We give some (new) constructions and we prove that every flag-transitive such geometry either belongs to a certain infinite class described by Coxeter a long time ago, or is one of three well-defined sporadic ones, namely, The Möbius-Kantor geometry on \(8\) points, The Desargues geometry on \(10\) points,A unique infinite example related to the tiling of the real Euclidean plane in regular hexagons.We also classify the possible groups.

Let \(G\) be a simple graph such that \(\delta(G) \geq \lfloor\frac{|V(G)|}{2}\rfloor + k\), where \(k\) is a non-negative integer, and let \(f: V(G) \to \mathbb{Z}^+\) be a function having the following properties (i)\(\frac{d_G(x)}{2}-\frac{k+1}{2}\leq f(x)\leq \frac{d_G(x)}{2}+\frac{k+1}{2}\) for every \(x \in V(G)\), (ii)\(\sum\limits_{x\in V(G)}f(x)=|E(G)|\). Then \(G\) has an orientation \(D\) such that \(d^+_D(x) = f(x)\), for every \(x \in V(G)\).

The so-called multi-restricted numbers generalize and extend the role of Stirling numbers and Bessel numbers in various problems of combinatorial enumeration. Multi-restricted numbers of the second kind count set partitions with a given number of parts, none of whose cardinalities may exceed a fixed threshold or “restriction”. The numbers are shown to satisfy a three-term recurrence relation. Both analytic and combinatorial proofs for this relation are presented. Multi-restricted numbers of both the first and second kinds provide connections between the orbit decompositions of subsets of powers of a finite group permutation representation, in which the number of occurrences of elements is restricted. An exponential generating function for the number of orbits on such restricted powers is given in terms of powers of partial sums of the exponential function.